Optimization over structured subsets of positive semidefinite matrices via column generation

Amir Ali Ahmadi, Sanjeeb Dash, Georgina Hall

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

We develop algorithms to construct inner approximations of 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 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.

Original languageEnglish (US)
Pages (from-to)129-151
Number of pages23
JournalDiscrete Optimization
Volume24
DOIs
StatePublished - May 1 2017

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics

Keywords

  • Copositive programming
  • Linear programming
  • Polynomial optimization
  • Second order cone programming
  • Semidefinite programming

Fingerprint

Dive into the research topics of 'Optimization over structured subsets of positive semidefinite matrices via column generation'. Together they form a unique fingerprint.

Cite this