##
A Unified Analysis for a Class of Path-Following Primal-Dual
Interior-Point Algorithms for Semidefinite Programming

###
Renato Monteiro and Yin Zhang

We present a unified analysis for a class of long-step primal-dual
path-following algorithms for semidefinite programming whose search
directions are obtained through linearization of the symmetrized
equation of the central path
$H_P(XS) \equiv [PXSP^{-1} + (PXSP^{-1})^T]/2 = \mu I$,
introduced by Zhang. At an iterate $(X,S)$, our permissible class of
scaling matrices $P$ consists of all nonsingular matrices $P$ such
that $PXSP^{-1}$ is symmetric. This class of matrices includes the
three well-known choices, namely: $P = S^{1/2}$ and $P = X^{-1/2}$
proposed by Monteiro, and the matrix $P$ corresponding to the
Nesterov-Todd direction. We show that within the class of algorithms
studied in this paper, the method based on the Nesterov-Todd direction
has the lowest possible iteration-complexity bound that can provably
be derived from our analysis. More specifically, its
iteration-complexity bound is of the same order as that of the
corresponding long-step primal-dual path-following algorithm for
linear programming introduced by Kojima, Mizuno and Yoshise.
Contact: yzhang@math.umbc.edu

work in progress.