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

Schmieta, S. H.; Alizadeh, F.

Math. Program. 96, No. 3 (A), 409-438 (2003).

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).

MSC:

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

Keywords:

semidefinite programming; Euclidean-Jordan algebras; path-following algorithms

Citations:

Zbl 0919.90109; Zbl 1073.90572