Sum of squares basis pursuit with linear and second order cone programming
Authors:
- 1 January 2017
- book chapter
- Published by American Mathematical Society (AMS)
- Vol. 685, 27-53
Abstract
We devise a scheme for solving an iterative sequence of linear programs (LPs) or second order cone programs (SOCPs) to approximate the optimal value of any semidefinite program (SDP) or sum of squares (SOS) program. The first LP and SOCP-based bounds in the sequence come from the recent work of Ahmadi and Majumdar on diagonally dominant sum of squares (DSOS) and scaled diagonally dominant sum of squares (SDSOS) polynomials. We then iteratively improve on these bounds by pursuing better bases in which more relevant SOS polynomials admit a DSOS or SDSOS representation. Different interpretations of the procedure from primal and dual perspectives are given. While the approach is applicable to SDP relaxations of general polynomial programs, we apply it to two problems of discrete optimization: the maximum independent set problem and the partition problem. We further show that some completely trivial instances of the partition problem lead to strictly positive polynomials on the boundary of the sum of squares cone and hence make the SOS relaxation fail.Keywords
This publication has 20 references indexed in Scilit:
- Sums of Squares, Moment Matrices and Optimization Over Polynomials2008
- Semidefinite bounds for the stability number of a graph via sums of squares of polynomialsMathematical Programming, 2006
- Algorithmic Graph Theory and Its Applications2005
- Positive Polynomials in Control2005
- Semidefinite programming relaxations for semialgebraic problemsMathematical Programming, 2003
- Second-order cone programmingMathematical Programming, 2003
- Squared Functional Systems and Optimization Problems2000
- An effective version of Pólya's theorem on positive definite formsJournal of Pure and Applied Algebra, 1996
- Uniform denominators in Hilbert's seventeenth problemMathematische Zeitschrift, 1995
- Ueber die Darstellung definiter Formen als Summe von FormenquadratenMathematische Annalen, 1888