##
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