-

 

 

 




Optimization Online





 

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

Dimitris Bertsimas (dbertsim***at***mit.edu)
Ryan Cory-Wright (ryancw***at***mit.edu)

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 1000s of covariates, and solve nuclear norm problems over 500 ◊ 500 matrices.

Keywords: Semidefinite optimization, Cutting planes, Nuclear norm, Sparse Principal Component Analaysis

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Applications -- Science and Engineering (Statistics )

Category 3: Linear, Cone and Semidefinite Programming (Other )

Citation: @techreport{bertsimas2019polyhedral, title={On Polyhedral and Second-Order-Cone Decompositions of Semidefinite Optimization Problems}, author={Bertsimas, Dimitris and Cory-Wright, Ryan}, institution={Massachusetts Institute of Technology}, year={2019} }

Download: [PDF]

Entry Submitted: 09/30/2019
Entry Accepted: 09/30/2019
Entry Last Modified: 12/02/2019

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society