On Polyhedral and Second-Order-Cone Decompositions of Semidefinite Optimization Problems

However, it is notoriously di fficult to solve in practice, because IPMs memory requirements scale at a demanding rate. Indeed, state-of-the-art SDO solvers such as MOSEK cannot solve constrained instances of Problem (1) with n 250 variables on a standard laptop, and it is optimization folklore that there is a gap between SDOs theoretical and practical tractability. Motivated by the demanding memory requirements of IPMs, a stream of literature studies inexact methods for SDOs, which replace the semidefinite constraint with weaker yet less computationally demanding constraints. This approach was first investigated by Kim and Kojima [13], who observed that relaxing a positive semidefinite constraint to the weaker constraint that all 2 2 minors of a matrix are positive semidefinite yields a second order cone (SOC)-representable outer approximation of the positive semidefinite (PSD) cone. In a related line of work, Krishnan and Mitchell [15] propose applying Kelley [12]'s cutting plane method to generate