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

DOI10.1016/J.ORL.2019.12.003MaRDI QIDQ6326722arXivWikidataFDO

Authors Dimitris Bertsimas, Ryan Cory-Wright

Publication date 7 October 2019

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.ORL.2019.12.003

Mathematics Subject Classification ID

Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

arXiv classification

cs.LGmath.OCstat.ML

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.

This page was built for publication: On Polyhedral and Second-Order Cone Decompositions of Semidefinite Optimization Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6326722)