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