Researches On Strongly Sub-feasible Methods And Sequential Quadratically Constrained Quadratic Programming Algorithms

Optimization plays more and more important roles in many areas,such as engineering design,production management,transportation,government decisionmaking. So more faster and efficient optimization algorithms are urgently demanded. Sequential quadratic programming(SQP) algorithms are among the most efficient algorithms for solving nonlinear constrained optimization.As an important kind of SQP algorithms,feasible SQP algorithms have many important applications in practice,such as engineering design and real-time control,since they can generate feasible iterations.However,a major disadvantage of feasible SQP is that a feasible starting point is required in advance,while computing such a point is generally a nontrivial work.Recently,in order to overcome this shortcoming,Prof.Jian has proposed a strongly sub-feasible direction method,and then successfully applied it to feasible SQP algorithms.This method allows arbitrary starting points,and guarantees that the feasibility of constraints is monotonously increasing.Furthermore, once a certain iterate gets into the feasible set,the corresponding algorithm will become feasible direction algorithm.However,there are still some problems in strongly sub-feasible direction method that needed to be resolved:ensuring theoretically the iterates getting into the feasible set after a finite number of iterations, removing some strong assumptions,reducing the computational cost and so on.During the past several decades,the researches of SQP methods have been greatly improved,but when the problems we solved are highly nonlinear,SQP methods usually show slow convergence,even fail.For this,in recent years,a so-called sequential quadratically constrained quadratic programming(SQCQP) method has been proposed. Compared with SQP methods,at each iteration SQCQP methods only need to solve a quadratically constrained quadratic programming(QCQP) subproblem, and without any correctional directions the Maratos effect will not occur and there- fore the superlinear convergence can obtained.QCQP subproblem is a quadratic approximation of the original problem,so it is a better approximation than the quadratic programming(QP) subproblem solved in SQP methods,and therefore the expected numerical performance of SQCQP will be better than SQP.Combining the ideas of strongly sub-feasible direction methods,SQP methods and SQCQP methods,this dissertation firstly proposed a strongly sub-feasible SQP algorithm and a strongly sub-feasible SQCQP algorithm.Secondly,with the motivation of overcoming the shortcomings of the existing SQCQP algorithms,two new SQCQP algorithms are proposed.The dissertation is divided into six chapters as follows.Chapter 1 mainly introduces the ideas of strongly sub-feasible direction methods and feasible SQP methods,recent developments of SQCQP methods,and the solution method of QCQP subproblem.Combining the ideas of strongly sub-feasible direction methods and feasible SQP methods,chapter 2 presents a new strongly sub-feasible SQP algorithm.By constructing new correctional directions and new Armijio-type curve search,the new algorithm overcomes several shortcomings of the traditional strongly sub-feasible SQP algorithm.At first,the algorithm theoretically ensures that the iterates get into the feasible set after a finite number of iterations,and then automatically becomes feasible SQP algorithm,as a result,a strong assumption(the order of the maximal constraint violation function is higher than the solution of the QP subproblem) is removed.Secondly,the strict complementarity condition is removed. At last,two correctional directions are generated by explicit formulas that contain the same inverse matrix,so the computational cost is reduced.The algorithm is proved to be globally and superlinearly convergent.Some preliminary numerical results show that the proposed algorithm is stable and efficient.Combining the ideas of strongly sub-feasible direction methods and feasible normrelaxed SQCQP methods,chapter 3 presents a strongly sub-feasible norm-relaxed SQCQP algorithm.By constructing new QCQP subproblem and new line search, the algorithm can start from arbitrary initial point,and ensure that the iterates get into the feasible set after a finite number of iterations.Only one convex QCQP subproblem needs to be solved at each iteration,and without any other correctional directions,the global,superlinear and quasi-quadratic convergence properties are obtained.Preliminary numerical results show that the proposed SQCQP algorithm is superior to a related SQP algorithm for the test problems.Chapter 4 presents a new penalty function type SQCQP algorithm,in which a simple nonmonotone penalty parameter updating technique is introduced.This technique only uses the KKT multiplier corresponding to the bounded constraint of the QCQP subproblem,since the multipliers corresponding to the quadratic con-straints are usually hard to be obtained when QCQP is cast and then solved as an second-order cone programming.This technique allows penalty parameters to be decreasing, which prevents the penalty parameters from increasing too fast and therefore prevents the penalty function and QCQP subproblem from being ill-conditioned. In addition,by using the working set technique,we remove the constraints of the QCQP subproblem that are locally irrelevant,so the computational cost is greatly reduced.Without assuming the convexity of the objective or constraints,the algorithm is globally,superlinearly and quadratically convergent.Preliminary numerical results show that the algorithm is superior to the tested SQP algorithms for the test problems.Combining the augmented Lagrange function line search technique and the idea of SQCQP methods,chapter 5 presents an augmented Lagrange function SQCQP algorithm, in which a new consistent convex QCQP subproblem is proposed.The active set strategy used in this subproblem can avoid calculating the unnecessary gradients and(approximate) Hessian matrices.The step size is generated by Armijio-type line search,and the penalty parameters can be reduced.Under suitable assumptions, the algorithm is proved to be globally,superlinearly,and quadratically convergent. Compared with previous SQCQP algorithms,the proposed algorithm can be easily extended to general problems with inequality and equality constraints,and to nonmonotone line search.Chapter 6 summarizes the main contributions of this dissertation,and raises some problems needed to be further studied.Finally,we should point out that sufficient and full numerical experiments were done for two SQCQP algorithms proposed in this dissertation,whereas except for a local convergent one(in which the QCQP subproblem is treated and solved as a general nonlinear programming),the previous SQCQP algorithms have not reported numerical experiments,mainly due to the difficulty of solving the QCQP subproblem.