Research On Infeasible Interior Point Method For Semidefinite Programming

Semidefinite programming is a new mathematical programming branch which is developed over the past 20 years.With the development of semidefinite programming,in real life,many problems from different fields can be modeled as a semidefinite programming problem to be solved,such as:economics,finance,engineering,management and so on.Owing to that its constraints are non-linear and convex,semidefinite programming is a non-smooth convex optimization problem.It is widely accepted that interior point algorithms are very effective algorithms for solving the semidefinite programming problem.Due to their low theoretical complexity and nice numerical effect,they have attracted many researchers to focus on and thus become a research hot in the field of mathematical programming quickly.According to whether the starting point is feasible or not,the interior point algorithms are classified into feasible interior point algorithm and infeasible interior point algorithm.According to the size of the algorithms'iterative neighborhood,the interior point algorithm can be classified into wide neighborhood interior point algorithm and narrow neighborhood interior point algorithm.It is well known that the wide neighborhood algorithm has good experimental effect but the theoretical complexity is relatively high,while the narrow neighborhood algorithm has a low theoretical complexity but the experimental results are relatively poor.In this paper,we mainly study the infeasible interior point algorithm for semidefinite programming.The purpose of this paper is to reduce the contradiction between wide neighborhood algorithm and narrow neighborhood algorithm,the main work is summarized as follows:On the one hand,for M type predictor corrector interior point algorithm,a feasible interior point algorithm for semidefinite programming,which is proposed by Feng Zengzhe and Fang Liang,is extended to the infeasible situation,and the iterative neighborhood of the algorithm is modified.Theoretically,we have proved that the iterative point sequence is convergent in the new wide neighborhood,and the iterative complexity of the algorithm is obtained as (?)(r Tr(X ~0S~0)/e)when the direction is taken as the Nesterrov-Todd(NT)direction,where r is the dimension of the problem,(X~0,S~0)is the starting point of the iteration.The results coincide with the best theoretical complexity in the current of the infeasible interior point algorithms for semidefinite programming.On the other hand,for MTY type predictor corrector interior point algorithm,Sungwoo Park proposed a constraint-reduced predictor corrector interior point algorithm for semidefinite programming.Based on this framework,a modified algorithm is proposed,in which the F norm of the matrix in the neighborhood is replaced by the 2 norm of the matrix.We also present some numerical results,which include that the number of iterations,the iterative time and the computational results after the termination of the algorithm.The results show that the proposed algorithm is more effective than the original algorithm.