The Research Of Algorithms For Semidefinite Programming

Semidefinite programming is an extension of linear programming. In recent years, the theory and algorithm for semidefinite programming have developed greatly, and its most important applications are found in combinatorial optimization, system engineering and electrical engineering. Semidefinite programming is a new and important research field in mathematical programming.In the paper, we firstly summarize the theory, algorithm, and recent research of semidefinite programming, then, introduce our some work in algorithm. We conclude them as follows:1. Applying inexact computation into infeasible interior-point algorithom, we propose a primal-dual inexact infeasible interior point algorithm for semidefiniteprogramming problems (SDP). The algorithm uses the search directions that are computed with only moderate accuracy, and in the iterate,it does not require feasibility to be maintained.Furthermore, its convergent bound is analyzed, it is showed that thealgorithm can find an ε-approximate solution for an SDP in O(n2 ln(1/ε)) iterations.2. Some definitions correlative with matrix valued functions are introduced, and we analysis some important properties of such functions by using the isometry between vector spaces and matrix spaces. We detailedly analysis the strongly semismoothness of some common matrix valued function which plays an important role in the development and convergent analysis of some algorithms for semidefinite programming problems.3. Based on the equivalently transforming the optimality conditions of the semidefinite programming as an equivalent nonlinear system of equations, which does not contain any explicit inequality constraints like X(?)0,Z(?)0 or X(?)0,Z(?)0 ,a smoothing Newton algorithm for semidefinite programming is proposed by applying smoothing Newton method to this nonlinear system of equations .And we analysis its convergence.The algorithm is showed to be quadratically convergent under suitable assumptions.