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

Abstract

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.

arXiv commentSubmitted minor revision to Operations Research Letters; removed footnotes and corrected some minor typos in previous version

References in corpus (6)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• JuMP: A Modeling Language for Mathematical Optimization
• Strong SOCP Relaxations for the Optimal Power Flow Problem
• A direct formulation for sparse PCA using semidefinite programming
• Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
• A unified approach to mixed-integer optimization problems with logical constraints

Cited by in corpus (5)

• A Scalable Algorithm For Sparse Portfolio Selection
• Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints
• Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality
• Instance-specific linear relaxations of semidefinite optimization problems
• Evaluating approximations of the semidefinite cone with trace normalized distance