Optimization Online


Optimization over Structured Subsets of Positive Semidefinite Matrices via Column Generation

Amir Ali Ahmadi (a_a_a***at***princeton.edu)
Sanjeeb Dash (sanjeebd***at***us.ibm.com)
Georgina Hall (gh4***at***princeton.edu)

Abstract: We develop algorithms for inner approximating the cone of positive semidefinite matrices via linear programming and second order cone programming. Starting with an initial linear algebraic approximation suggested recently by Ahmadi and Majumdar, we describe an iterative process through which our approximation is improved at every step. This is done using ideas from column generation in large-scale linear and integer programming. We then apply these techniques to approximate the sum of squares cone in a nonconvex polynomial optimization setting, and the copositive cone for a discrete optimization problem.


Category 1: Linear, Cone and Semidefinite Programming

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Nonlinear Optimization


Download: [PDF]

Entry Submitted: 12/16/2015
Entry Accepted: 12/16/2015
Entry Last Modified: 03/11/2016

Modify/Update this entry

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


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