Font Size: a A A

Studies On The Active Set Identification And Multidimensional Filter Techniques For Solving Optimization Problems

Posted on:2010-05-09Degree:DoctorType:Dissertation
Country:ChinaCandidate:L SunFull Text:PDF
GTID:1100360302466677Subject:Applied Mathematics
Abstract/Summary:PDF Full Text Request
This thesis aims to study the active set method and multidimensional filter trust region method fbr solving unconstrained and bound constrained minimization problems. It consists of six parts.In the first chacpter,we introduce the development and recent situations of the active set strategy for solving bound constrained optimization and the filter techniques which is the hot topic in the field of optimization.The type of existing methods is discussed and summarized,which drops the problems need to be further sloved and the main results of our paper.In Chapter 2,an active set quasi-Newton method is analyzed in this paper.The active set strategy which belongs to the approximate active set identification allows the quick change in the working set,it's suitable fbr solving large scale problems.As the special structure of the KKT system of the bound constrained optimization,the multipliers can be determined directly by the gradient.We prove that the algorithm is globally convergent under mild assumptions.Numerical results demonstrate that the active set strategy which based on the multiplier functions need more running time as it contains the additional computation of n×n linear system.In Chapter 3,we propose an accurate active set Newton method for sloving bound constrained optimization.The algorithm is based on an accurate identification technique of the active set proposed by Facchinei,Fischer and Kanzow in 1998.Different form the works that have been done in[2,3,6],the active variables use the steepest descent directions move into the interior or toward the boundary of the feasible region. Under standard assumptions,the new algorithm is globally convergent.In particular, the convergence rate is superlinear without requiring the strict complementarity assumption. Numerical tests demonstrate the efficiency and performance of the present strategy and its comparison with some existing active set strategies. In Chapter 4,based on the work that has been done in the previous chapter, we combine the accurate active set identification function and the projected search together.Both of these two strategies permit fast change in the working set.A limited memory method is employed to update the variables outside of the working set,while active variables are updated by simple rules.Numerical results and comparison with existing active set strategies are reported.In Chapter 5,based on a multidimensional filter technique which was proposed by Gould etc.in 2005,we used the generalized Cauchy point directly when the model of the subproblem is nonconvex.This modification avoids judging the convexity of the trust region subproblem in the algorithm.The new algorithm is more suitable for coding.Numerical results show that the present algorithm is efficient and reliable.The last chapter,we present a modified filter trust region method for bound constrained problems.Different from the works that have been done by Gould et al., we employ the multidimensional filter technique into the quasi-Newton trust region method.The determination of the trial step relies on solving a lower dimensional trust region subproblem as the generalized Cauchy point has been used to predict the active set.Global convergence is promoted through the use of the filter and the convergence theory holds for convex constrained problems.Numerical results demonstrate the efficiency of the modified algorithm.
Keywords/Search Tags:Limited memory quasi-Newton method, Gradient projection method, Multidimensional filter, Active set, Global convergence, Superlinear convergence
PDF Full Text Request
Related items