Primal-dual Interior Point Algorithm For Semidefinite Programming

Semidefinite Programming(SDP) is a generalization of Linear Programming(LP), at the same time,SDP problem is also a kind of important mathematical programming problems. It has various application in diverse areas, such as communication, engineering design, combinatorial optimization etc, therefore,it is very necessary for SDP’ research. This paper focuses on arc search interior point algorithm and the center parameter is not fixed for interior point algorithm in SDP. In this paper, we also analysis that they are polynomial complexity.then the numerical experiments are compared.Based on primal-dual interior point algorithm in SDP’application, this paper mainly completes following work.Firstly, we make brief introduction to research background and progress of SDP,as well as basic theory and main Algorithms of solving SDP problems, then, examples of several convertible SDP problems are listed, finally,this paper’s main work and content is arrangement.Secondly, interior point algorithm based on arc search exists good complexity in terms of LP theory, and it shows that the ellipse arc search interior point algorithm is better than the one dimensional linear search. Reference[1] proposes arc search interior point algorithm for LP, which is put forward to SDP in this paper, It searches optimizers by correct step of the MTY predictor correction algorithm and which improve centricity and optimality by two-step iteration and use the ellipse approximation center path, meanwhile, at the initial point feasible, We prove the iteration complexity of the algorithm is the best for SDP at present.Finally, for interior-point algorithm in SDP, it is well-known that the selection of the center parameter is crucial for proving complexity of theory and for efficiency of practice, Therefore, we extend effective interior point algorithm for LP in reference[2] to SDP. In the paper, we propose an effective feasible interior point algorithm for SDP. Based on wide neighborhood, it is related to polynomial for center parameter and search step size, thus, in each iteration, the center parameter could change with step size and find the optimal.Based on NT direction, we prove that this algorithm is very effective in theory and practice. then the numerical experiments are compared.