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.
![[DVI]](../../InteriorPoint/gif/DVI.gif)
![[POSTSCRIPT]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)