A General Framework for Establishing Polynomial Convergence of Long-Step Methods for Semidefinite Programming

Samuel Burer and Renato D.C. Monteiro

This paper considers feasible long-step primal-dual path-following methods for semidefinite programming based on Newton directions associated with central path equations of the form $\Phi(P X P^T, P^{-T} S P^{-1}) - \nu I = 0$, where the map $\Phi$ and the nonsingular matrix $P$ satisfy several key properties. An iteration-complexity bound for the long-step method is derived in terms of an upper bound on a certain scaled norm of the second derivative of $\Phi$. As a consequence of our general framework, we derive polynomial iteration-complexity bounds for long-step algorithms based on the following four maps: $\Phi(X,S) = (XS + SX)/2$, $\Phi(X,S) = X^{1/2} S X^{1/2}$, $\Phi(X,S) = L_x^T S L_x$, and $\Phi(X,S) = W^{1/2} X S W^{-1/2}$, where $L_x$ is the lower Cholesky factor of $X$ and $W$ is the unique symmetric matrix satisfying $S = WXW$.

School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332 August 1999

Contact: burer@math.gatech.edu