Primal-Dual Path Following Algorithms for Semidefinite Programming

R. D. C. Monteiro

This paper deals with a class of primal-dual interior-point algorithms for semidefinite programming (SDP) which was recently introduced by Kojima, Shindoh and Hara \cite{KoShHa94-1}. These authors proposed a family of primal-dual search directions that generalizes the one used in algorithms for linear programming based on the scaling matrix $X^{1/2}S^{-1/2}$. They study three primal-dual algorithms based on this family of search directions: a short-step path following method, a feasible potential-reduction method and an infeasible potential-reduction method. However, they were not able to provide an algorithm which generalizes the long-step path-following algorithm introduced by Kojima, Mizuno and Yoshise \cite{KojMY89-1}. In this paper, we characterize two search directions within their family as being (unique) solutions of systems of linear equations in symmetric variables. Based on this characterization, we present: 1) a simplified polynomial convergence proof for their short-step path following algorithm and, 2) for the first time, a polynomially convergent long-step path following algorithm for SDP which requires an extra $\sqrt{n}$ factor in its iteration-complexity order as compared to its linear programming counterpart, where $n$ is the number of rows (or columns) of the matrices involved.