Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones

S. H. Schmieta, F. Alizadeh

Research output: Contribution to journalArticlepeer-review

91 Scopus citations

Abstract

We present a general framework whereby analysis of interior-point algorithms for semidefinite programming can be extended verbatim to optimization problems over all classes of symmetric cones derivable from associative algebras. In particular, such analyses are extendible to the cone of positive semidefinite Hermitian matrices with complex and quaternion entries, and to the Lorentz cone. We prove the case of the Lorentz cone by using the embedding of its associated Jordan algebra in the Clifford algebra. As an example of such extensions we take Monterio's polynomial-time complexity analysis of the family of similarly scaled directions-introduced by Monteiro and Zhang (1998)-and generalize it to cone-LP over all representable symmetric cones.

Original languageEnglish (US)
Pages (from-to)543-564
Number of pages22
JournalMathematics of Operations Research
Volume26
Issue number3
DOIs
StatePublished - Aug 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

  • Euclidean Jordan algebras
  • Interior point methods
  • Semidefinite programming
  • Symmetric cones

Fingerprint Dive into the research topics of 'Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones'. Together they form a unique fingerprint.

Cite this