Extension of primal-dual interior point algorithms to symmetric cones

S. H. Schmieta, F. Alizadeh

Research output: Contribution to journalArticle

243 Scopus citations

Abstract

In this paper we show that the so-called commutative class of primal-dual interior point algorithms which were designed by Monteiro and Zhang for semidefinite programming extends word-for-word to optimization problems over all symmetric cones. The machinery of Euclidean Jordan algebras is used to carry out this extension. Unlike some non-commutative algorithms such as the XS+SX method, this class of extensions does not use concepts outside of the Euclidean Jordan algebras. In particular no assumption is made about representability of the underlying Jordan algebra. As a special case, we prove polynomial iteration complexities for variants of the short-, semi-long-, and long-step path-following algorithms using the Nesterov-Todd, XS, or SX directions.

Original languageEnglish (US)
Pages (from-to)409-438
Number of pages30
JournalMathematical Programming
Volume96
Issue number3
DOIs
StatePublished - Jun 2003

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Extension of primal-dual interior point algorithms to symmetric cones'. Together they form a unique fingerprint.

Cite this