Studies On The QP-Free Algorithms For Constrained Optimization

Sequential system of linear equations algorithm has arosen increasing attention since it was first proposed in1988, and is a hot topic in academia recently."Now it has been one of the most effective algorithms available for the constrained optimization problems. In QP-free algorithm, the search direction can be obtained without solving any quadratic programming subproblems, also its convergence holds under some assumptions. Hence, it is meaningful to study the QP-free algorithm. In this paper, combined with accurate identification of active set, a new QP-free algorithm with working set is proposed, which is also extended to the minmax problems. The main contents and results are listed as follow.Different methods for the constrained optimization problems and the development process of sequential system of linear equations method are introduced in Chapter one, and the research focuses on the QP-free method which is combined with working set. Furthermore, the" working set" based on the identification of active set is introduced in this chapter. Finally, the thesis work was outlined briefly.An improved sequential system of linear equations algorithm with new working set is presented in Chapter two. Started with an arbitrary initial point, by mens of the generalized projection technique and pivoting operation, the new multiplier function is given at first. And the identification function is defined based on the KKT condition. Then the new working set Ik is introduced combined with the the maximum function, in which the initial point is infeasible. Inspired by the ideas of [76], a new sequential system of linear equations algorithm with arbitrary initial point is given and the concrete step is stated concretely. At each iteration, only three systems of linear equations with the same coefficient matrix need to be solved to obtain the search direction, and then the updated direction is computed to avoid the Maratos effect. Moreover, a new line search technique is adopted by the the maximum function, by which the iteration point can get into feasible set more quickly. Based on the linear independence constraint qualification (LICQ), the algorithm is proved to be well defined. Under some mild conditions that the iteration sequence is bounded and the approximate Hessian matrix Hk is uniformly positive definite, the algorithm is proved to be globally convergent. Moreover, based on LICQ and the second-order sufficiency conditions, the original advantage for the new working set can be proved to hold, that is. all the inactive constraints at KKT point x’ will be neglected when the number of iterations are large enough. Then on this basis, the iteration point can get into the feasible set after finite iterations. Furthermore, the strong and superlinear convergence can be obtained without the strict complementarity. Even the quadratic convergence can hold under some stronger assumptions. Many numerical experiments are tested at last, including the large-scale numerical example. Moreover, the algorithm is compared with the same method in term of iteration number and computation. The experimental data is in good accordance with the analysis of the algorithm.The working set technique in the algorithm is extended to the constrained minmax problems in Chapter three. The QP-free algorithm with working set technique valid for smooth nonlinear programming cannot be used directly for the nonsmooth constrained minimax problems. Firstly by introducing an additional variable, the minimax problem can be reformulated as the smooth constrained optimization. Morever, the new working set for the constrained minmax problem is defined, respectively for the feasible and arbitrary initial point. To study the advantage of new working set, the relationship between the MFCQ/LICQ for minmax problem and smooth optimization is presented. Based on this, the new working set is proved to keep the original advantage under the Mangasarian-Fromovitz constraint qualification and the second-order sufficiency conditions, that is when the iteration number is large enough, all the inactive constraints at stationary point x*will be neglected. Therefore, the QP-free algorithm with new working set technique is viable for the constrained minimax problems.In Chapter four, the author sums up the research efforts in the thesis and gives prospects of the further research in the fields.