DIMACS TR: 97-37

Affine Scaling Algorithms Fail for Semidefinite Programming

Authors: Masakazu Muramatsu and Robert J. Vanderbei


In this paper, we give an example of a semidefinite programming problem in which primal-dual affine-scaling algorithms using the XZ, MT, and AHO directions fail. We prove that each of these algorithm can generate a sequence converging to a non-optimal solution, and that, for the AHO direction, even its associated continuous trajectory can converge to a non-optimal point. In contrast with these directions, we show that the primal-dual affine-scaling algorithm using the NT direction for the same semidefinite programming problem always generates a sequence converging to the optimal solution. Both primal and dual problems have interior feasible solutions, unique optimal solutions which satisfy strict complementarity, and are nondegenerate everywhere.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-37.ps.gz
DIMACS Home Page