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: muramatu@me.sophia.ac.jp


 [DVI]  [PS]  [IP PAGE]  [SEARCH AGAIN]