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.


 [DVI]  [POSTSCRIPT]  [IP PAGE]  [SEARCH AGAIN]