Sum of squares basis pursuit with linear and second order cone programming
From MaRDI portal
Publication:2979646
DOI10.1090/CONM/685/13712zbMATH Open1393.90081arXiv1510.01597OpenAlexW2272603263MaRDI QIDQ2979646FDOQ2979646
Authors: Amir Ali Ahmadi, Georgina Hall 
Publication date: 25 April 2017
Published in: Algebraic and Geometric Methods in Discrete Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1510.01597
Recommendations
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- Sum-of-squares optimization without semidefinite programming
- Smaller SDP for SOS decomposition
- Alternative SDP and SOCP approximations for polynomial optimization
- Moments and sums of squares for polynomial optimization and related problems
maximum independent set problempartition problemdiagonally dominant sum of squaresprimal and dual perspectives
Linear programming (90C05) Large-scale problems in mathematical programming (90C06) Semidefinite programming (90C22)
Cites Work
- Title not available (Why is that?)
- Semidefinite Programming
- Reducibility among combinatorial problems
- Global optimization with polynomials and the problem of moments
- On the Shannon capacity of a graph
- Applications of second-order cone programming
- Second-order cone programming
- Semidefinite programming relaxations for semialgebraic problems
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Uniform denominators in Hilbert's seventeenth problem
- An effective version of Pólya's theorem on positive definite forms
- Sums of squares, moment matrices and optimization over polynomials
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the computational complexity of membership problems for the completely positive cone and its dual
- Title not available (Why is that?)
- Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
- Positive polynomials in control.
- Title not available (Why is that?)
- Cones of diagonally dominant matrices
- Algorithmic graph theory and its applications
- Optimization over structured subsets of positive semidefinite matrices via column generation
Cited In (14)
- Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit
- Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
- Bounding extrema over global attractors using polynomial optimisation
- Diagonally dominant programming in distance geometry
- Maximum feasible subsystems of distance geometry constraints
- Sum-of-squares optimization without semidefinite programming
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- Bounding extreme events in nonlinear dynamics using convex optimization
- Multistage distributionally robust mixed-integer programming with decision-dependent moment-based ambiguity sets
- On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones
- Decomposed structured subsets for semidefinite and sum-of-squares optimization
- Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices
- Outer approximation with conic certificates for mixed-integer convex problems
- Generating valid linear inequalities for nonlinear programs via sums of squares
Uses Software
This page was built for publication: Sum of squares basis pursuit with linear and second order cone programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2979646)
