Extension of primal-dual interior point algorithms to symmetric cones. (English) Zbl 1023.90083

Summary: In this paper we show that the so-called commutative class of primal-dual interior point algorithms which were designed by R. D. C. Monteiro and Y. Zhang [Math. Program. 81A, 281-299 (1998; Zbl 0919.90109)] 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. See also the authors’ companion paper in Math. Oper. Res. 26, 543-564 (2001; Zbl 1073.90572).


90C51 Interior-point methods
90C22 Semidefinite programming
17C55 Finite-dimensional structures of Jordan algebras
Full Text: DOI