SQP-type Methods And Their Rate Of Convergence For Nonlinear Semidefinite Programming

Due to its important role in the fields of optimal control,structural optimization,eigenvalue optimization,etc.,the study of nonlinear semidefinite programming(NSDP)has received great attention.As an extension of sequential quadratic programming(SQP)in nonlinear programming on the semidefinite matrix cone,sequential quadratic semidefinite programming(SSDP)is an effective method for solving NSDP problems.Based on the classic SSDP method,we propose and study several SQP-type algorithm and analyze their global convergence and rate of convergence.The effectiveness of each algorithm is verified by some numerical experiments.In the first chapter,we introduce the background and development status of NSDP.Some commonly used symbols are introduced.The research of SSDP methods are summarized.In Chapter 2,we first review the basic knowledge of NSDP,such as the KKT system of constrained optimization problems,constraint qualifications,optimality conditions,etc.,and make an analogy with nonlinear programming.The conditions of existence,boundedness and uniqueness for Lagrangian multipliers are given.Our main work is in Chapter 3,Chapter 4,Chapter 5 and Chapter 6.The specific content is summarized as follows.In Chapter 3,we first review the local SSDP algorithm in NSDP,and then give the conclusions of the rate of convergence under different assumptions in the existing literature.Considering that most problems do not require dual solutions,we point out that when the primal-dual sequence satisfies the conditions of quadratic convergence,the primal sequence has a superlinear rate of convergence.In addition,we use Schur’s complement theorem to construct an equivalent and reduced problem,and give a new local reduced SSDP algorithm.The rate of quadratic/superlinear convergence of the primal-dual sequence generated by the reduced algorithm are analyzed.Under the condition of the quadratic convergence of the primal-dual sequence,the rate of superlinear convergence of the primal sequence is proved.We give an equivalent condition for the rate of superlinear convergence of the primal sequence,which is generated by the reduced algorithm.Under the constraint nondegeneracy condition,the second-order sufficient condition and the strict complementarity condition,an equivalent condition for the rate of superlinear convergence of the primal sequence generated by the classic SSDP algorithm is given.A simple example is adopted to observe the convergence rate of the algorithm,numerically.In Chapter 4,a reduced SSDP algorithm for NSDP problems with linear matrix inequality constraints is present.By introducing an l1 exact penalty function as the merit function,global convergence of the reduced algorithm is proved under the Armijo line search strategy.Under the assumptions in Chapter 3,the primal sequence generated by the new algorithm converges superlinearly.In addition,when the form of the reduced problem changes,the penalty parameter can be decreased appropriately.Since the matrix constraint of the original problem is split into a lower order by Schur’s complement theorem,the scale of the reduced problem is decreased.The effectiveness of the algorithm is described,by testing some common NSDP problems,in terms of convergence rate,operation time,and number of iterations.In Chapter 5,we present a two-phase SSDP algorithm with bi-object strategy.In the first phase,the new algorithm determines,by minimizing the measure of linearization constraint violation,whether the quadratic semidefinite programming subproblem is consistent.Then,a quadratic semidefinite programming subproblem with some certain constraint qualification is considered in the second phase.The subproblem,whose Lagrangian multiplier exists,is easy to solve.By controlling the size of the penalty parameter,the algorithm generates search directions to make a trade-off between improving the measure of constraint violation and reducing the value of objective function.The acceptance criterion,which is a penalty-free one,has bi-object strategy.It is judged whether the algorithm needs to reduce the value of objective function or improve the measure of constraint violation.Global convergence is analyzed without a feasibility restoration phase.The sequence of the penalty parameter,the value of objective function and the measure of constraint violation are all updated non-monotonely.Under the constraint nondegeneracy condition,the second-order suficient condition and the strict complementarity condition,the search direction is a superlinear convergent one.At the end of this chapter,some degenerate examples and common NSDP problems are used to illustrate the effectiveness of the algorithm.In Chapter 6,we first give the basic framework of a two-phase penalty-free SSDP algorithm,which does not need any penalty parameter whether it is to solve the search direction or to judge the acceptance criterion,and that is different from the two-phase algorithm in Chapter 5.The acceptance criterion also has a bi-object strategy.Under the basic framework,we give two modifications to speed up the rate of convergence.One is to transform the original problem,by selecting the non-active part of the constraint matrix during each iteration,into an approximation reduced one,which generates search direction with a superlinear rate of convergence.The other modification is introducing the concept of multiplier function and replacing the objective function by the Lagrangian function in the acceptance criteria to overcome the Maratos effect.Under the constraint nondegeneracy condition,the second-order sufficient condition and the strict complementarity condition,the primal sequence generated by the new algorithm converges superlinearly.At the end of this chapter,some examples with the Maratos effect are given.Common NSDP problems are shown to verify the effect of the new algorithm.