Polynomial primal-dual cone affine scaling for semidefinite programming

Arjan B. Berkelaar, Jos F. Sturm, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

Semidefinite programming concerns the problem of optimizing a linear function over a section of the cone of semidefinite matrices. In the cone affine scaling approach, we replace the cone of semidefinite matrices by a certain inscribed cone, in such a way that the resulting optimization problem is analytically solvable. The now easily obtained solution to this modified problem serves as an approximate solution to the semidefinite programming problem. The inscribed cones that we use are affine transformations of second order cones, hence the name 'cone affine scaling'. Compared to other primal-dual affine scaling algorithms for semidefinite programming (see de Klerk, Roos and Terlaky (1997)), our algorithm enjoys the lowest computational complexity.

Original languageEnglish (US)
Pages (from-to)317-333
Number of pages17
JournalApplied Numerical Mathematics
Volume29
Issue number3
DOIs
StatePublished - Mar 1999

Keywords

  • Affine scaling
  • Primal-dual interior point methods
  • Semidefinite programming

Fingerprint

Dive into the research topics of 'Polynomial primal-dual cone affine scaling for semidefinite programming'. Together they form a unique fingerprint.

Cite this