The Primal-dual Interior-point Algorithms For Semidefinite Optimization

The semidefinite optimization problem is an extension of the linear optimization problem,and it is an class of conic optimization problems that minimizes or maximizes a linear objective function of the matrix variable over the intersection of an affine space and the cone of the positive semidefinite matrices.It has been applied in different fields,such as combinatorial optimization problems,system and control theory and eigenvalue optimization problems.At the same time,interior-point methods for solving linear optimization problems were successfully extended to solve semidefinite optimization problems.Therefore,the semidefinite optimization problem has been one of the most active research areas in mathematical programming problems.The construction of interior-point methods can be various according to different classification norms.Based on whether the initial point is feasible or not,interior-point methods can be classified into feasible methods and infeasible methods.Based on the processing problems,interior-point methods can be classified into primal,dual,and primal-dual interior-point methods.The paper considers the primal-dual feasible interior-point methods for semidefinite optimization.The main work is summarized as follows:Firstly,the full Nesterov-Todd step interior-point algorithm is concerned.We present a full Nesterov-Todd step primal-dual feasible interior-point algorithm for semidefinite optimization.The search directions of the algorithm is determined based on algebraic equivalent transformation to obtain a new central path equations.The algorithm takes only full Nesterov-Todd step in each iteration.Under certain conditions,the convergence of the algorithm is proved and the iteration complexity result coincides with the best-known iteration bound for semidefinite optimization.The numerical results illustrate that the algorithm is effective.Secondly,we study the wide neighborhood prediction-correct interior-point algorithm.We propose a new primal-dual second-order corrector interior-point algorithm for semidefinite optimization.The algorithm is based on Darvay-Takács neighborhood of the central path.In the new algorithm,the search directions are determined by the Darvay-Takác’s direction and a second-order corrector direction in each iteration.The iteration complexity bound for the Nesterov-Todd scaling direction,which has the same complexity results as the small neighborhood algorithm for semidefinite optimization.Finally,numerical experiments show that the proposed algorithm is promising.