Study Of Several Algorithms For Semidefinite Programming Problems

In this paper, we study several algorithms for Semidefinite Programming. We mainly study infeasible algorithm and cutting plane approach for linear Semidefinite Programming, sequential linearization method and Augmented Lagrangian method for Nonlinear Semidefinite Programming. The whole paper contains five chapters. This thesis is arranged as follows.In the first chapter, we summarily introduce the development and algorithms of Semidefinite Programming. In the second chapter, we present a primal-dual inexact infeasible interior-point polynomial algorithm for Semidefinite Programming problems which is based on Nestrov-Todd search direction. The algorithm allows the utilization of inexact search directions that are calculated from the defining linear system with only moderate accuracy of primal and dual residues. This algorithm does not require feasibility to be maintained even if the initial iterate or the point maintained after an iteration happened to be a feasible solution of the problems. Under a mild assumption, we show that the algorithm canfind an -approximate solution of an SDP in O(n21n(1/)) iterations. Thebound of our algorithm is the same as that of the exact infeasible interior-point algorithms proposed by Y. Zhang. In the third chapter, we present a cutting plane approach based on a semi-infinite formulation. The advantage of the method is that we can maintain much deeper cut at each iteration, so we can cut off more infeasible points, and it has been shown that the generalized method offers polynomial complexity. In the fourth chapter, we present a sequential linearization method forNonlinear Semidefinite Programming. The approach employs exact l1 -penalty function and a trust-region-type globalization technique. At eachiteration, the method solves a quadratic semidefinite programming subproblem which can be reformulated into a linear semidefinite programming or a SDP with a second order cone constraint. A subproblem of this kind can be solved quite efficiently by using some recent software for semidefinite and second-order cone programs. The method is shown to be globally convergent under certain assumptions. In the fifth chapter, we introduce an Augmented Lagrangian method for solving convex Nonlinear Semidefinite Programming (NLSDP) problems. The Augmented Lagrangian function defined in this paper guarantees good behavior of the Newton method when minimizing the augmented Lagrangian function. The efficiency of this approach is based on a special choice of the penalty function for matrix inequalities. The basic algorithm combines ideas of the exterior penalty and interior barrier methods with the Augmented Lagrangian method. The algorithm can also solve second-order conic programming (SOCP) problems, as well as problems with a mixture of SDP, SOCP and NLP constraints and it is particularly suitable for solving large sparse problems.