On Polyhedral and Second-Order Cone Decompositions of Semidefinite Optimization Problems
This work addresses optimization challenges in machine learning and data analysis, particularly for high-dimensional problems like sparse PCA, but it is incremental as it builds on existing cutting-plane methods with specific initializations.
The authors tackled semidefinite optimization problems by developing a cutting-plane method with proven convergence, showing it performs better when initialized with a second-order-cone approximation rather than a linear one. They achieved bound gaps of 0.5-6.5% for sparse PCA with thousands of covariates and solved nuclear norm problems over 500x500 matrices.
We study a cutting-plane method for semidefinite optimization problems (SDOs), and supply a proof of the method's convergence, under a boundedness assumption. By relating the method's rate of convergence to an initial outer approximation's diameter, we argue that the method performs well when initialized with a second-order-cone approximation, instead of a linear approximation. We invoke the method to provide bound gaps of 0.5-6.5% for sparse PCA problems with $1000$s of covariates, and solve nuclear norm problems over 500x500 matrices.