A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming LCP

Florian Potra and Ronquin Sheng

We propose a primal-dual infeasible-interior-point path-following algorithm for solving semidefinite programming (SDP) problems. If the problem has a solution, then the algorithm is globally convergent. If the starting point is feasible or close to being feasible, the algorithms finds an optimal solution in at most $O(\sqrt{n}L)$ iterations. If the starting point is large enough then the algorithm terminates in at most $O(nL)$ steps either by finding a solution or by determining that the primal-dual problem has no solution of norm less than a given number. Moreover, we propose a sufficient condition for the superlinear convergence of the algorithm. In addition, we give two special cases of SDP for which the algorithm is quadratically convergent.

Reports on Computational Mathematics, No.78, Department of Mathematics, The University of Iowa, October 1995.