Primal-dual affine-scaling algorithm fails for semidefinite programming
M. Muramatsu and R. J. Vanderbei
In this paper, we give an example of a semidefinite programming problem
in which primal-dual affine-scaling algorithms using
the HRVW/KSH/M, 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 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.
Technical Report SOR 97-05, April 1997 (Revised June 1997)
Princeton University, NJ 08544.
Contact: [email protected]