DIMACS TR: 97-37
Affine Scaling Algorithms Fail for Semidefinite Programming
Authors: Masakazu Muramatsu and Robert J. Vanderbei
ABSTRACT
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