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: [email protected]