A Long-Step Path Following Algorithm for Semidefinite Programming Problems
Kurt M. Anstreicher and Marcia Fampa
We consider a primal long-step path following algorithm for
semidefinite programming. Our main result is that Roos and Vial's
elegant analysis of quadratic convergence, for the linear programming case,
extends in a very natural way to semidefinite programming.
For problems with a semidefiniteness constraint on an $m\times m$ matrix
we obtain algorithms with complexities of $O(m\ln(t))$
or $O(\sqrt{m}\ln(t))$ iterations to reduce the initial primal--dual gap
by a factor of $t$, depending on how the barrier parameter is reduced.
This paper was originally announced on 1/12/1996, and substantially revised on
1/29/1996.
University of Iowa, January 1996.
Contact: KAnstrei@scout-po.biz.uiowa.edu
![[DVI]](../../InteriorPoint/gif/DVI.gif)
![[POSTSCRIPT]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)