The Study On Trust Region Methods For Semidefinite Programming

Semidefinite programming is an extension of linear programming.In semidefinite programming one maximizes (minimizes) a linear objective function subject to the constraint that an affine combination of symmetric matrices is positive semidefinite. Such the constraint is nonlinear and nonsmoooth,but convex,so semidefinite programming has been one of the most active research areas in mathematical programming because its theory and algorithms have been developed greatly and its numerous applications have been found in control theory,electrical engineering and combinatorial optimization.This article firstly summarizes the product and development of semidefinite programming in particularly.It introduces the initial product process of semidefinite programming and the algorithm research development of semidefinite programming in academia in recent decades.Then this paper gives the basic conception, the primal-dual problem,the main algorithms of semidefinite programming.Finally,it introduces the practical applications of semidefinite programming.The core of this paper gives the trust region algorithm for semidefinite programming.Firstly,we obtain the optimal conditions of semidefinite programming and its dual problem by means of complemental relax conditions,that is KKT conditions.So we transform the solutions of semdefinite programming into the solutions of nonlinear differentiable equations.Then we also transform the nonlinear differential equations into a nonlinear differentiable equations by using extensive Fischer-Burmeister's smooth functions.Then the nonlinear differentiable equations is converted to a unconstrained optimal problem.Finally,we define an effective function by means of least-square principle. So the solutions of the original semdefinite programming is transformed into the unconstrained optimal minimax problem.Finally,this thesis works out the approximate solutions of the unconstrained optimal minimax problem by means of trust region algorithm,that is the results of original semdefinite programming.It also analyses the efficiency and qualitative relevance of the algorithm. At last, the global convergence analysis of the trust region algorithm is proved.The experiment indicates that this method is effective.