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.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received: April 2000 / Accepted: May 2002 Published online: March 28, 2003
RID="⋆"
ID="⋆" Part of this research was conducted when the first author was a postdoctoral associate at Center for Computational Optimization at Columbia University.
RID="⋆⋆"
ID="⋆⋆" Research supported in part by the U.S. National Science Foundation grant CCR-9901991 and Office of Naval Research contract number N00014-96-1-0704.
Rights and permissions
About this article
Cite this article
Schmieta, S., Alizadeh, F. Extension of primal-dual interior point algorithms to symmetric cones. Math. Program., Ser. A 96, 409–438 (2003). https://doi.org/10.1007/s10107-003-0380-z
Issue Date:
DOI: https://doi.org/10.1007/s10107-003-0380-z