On Hazan's algorithm for symmetric programming problems (Q2342137): Difference between revisions

The author generalizes Hazan's algorithm for semidefinite programming to symmetric programming problems with a bounded feasible domain, a class of problems which includes semidefinite programming, second-order cone programming, and linear programming problems. In his analysis the author works in a Jordan-algebraic framework where he makes use of the one-to-one correspondence between the class of symmetric cones and a class of Euclidean Jordan algebras. He shows that the major property of Hazan's algorithm that it finds a low-rank approximation of an optimal solution can be preserved in the more general setting of symmetric programming problems and that, conversely, this setting is natural in regard to the preservation of this property. In particular, he describes in detail how the decomposition of a symmetric cone into a direct sum of its irreducible components can be utilized to reduce the computational complexity of the algorithm.