Polynomial convergence of a new family of primal-dual algorithms for semidefinite programming

This paper establishes the polynomial convergence of a new class of primal-dual interior-point path-following feasible algorithms for semidefinite programming (SDP) whose search directions are obtained by applying Newton's method to the symmetric central path equation (PXPT)(1/2)(P-T SP-1)(PXPT)(1/2) - mu I = 0, where P is a nonsingular matrix. Specifically, we show that the short-step path-following algorithm based on the Frobenius norm neighborhood and the semilong-step path-following algorithm based on the operator 2-norm neighborhood have O(root nL) and O(nL) iteration-complexity bounds, respectively. When P = I, this yields the first polynomially convergent semilong-step algorithm based on a pure Newton direction. Restricting the scaling matrix P at each iteration to a certain subset of nonsingular matrices, we are able to establish an O(n(3/2) L) iteration complexity for the long-step path-following method. The resulting subclass of search directions contains both the Nesterov-Todd direction and the Helmberg-Rendl-Vanderbei-Wolkowicz/Kojima-Shindoh-Hara/Monteiro direction.