Primal-dual affine-scaling algorithms fail for semidefinite programming

Masakazu Muramatsu, Robert J. Vanderbei

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

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 algorithms 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 and unique optimal solutions which satisfy strict complementarity, and are nondegenerate everywhere.

Original languageEnglish (US)
Pages (from-to)149-175
Number of pages27
JournalMathematics of Operations Research
Volume24
Issue number1
DOIs
StatePublished - Jan 1 1999

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Primal-dual affine-scaling algorithms fail for semidefinite programming'. Together they form a unique fingerprint.

  • Cite this