Sum of squares basis pursuit with linear and second order cone programming
From MaRDI portal
Publication:2979646
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.
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
Cites work
- scientific article; zbMATH DE number 1984325 (Why is no real title available?)
- scientific article; zbMATH DE number 3002670 (Why is no real title available?)
- scientific article; zbMATH DE number 1489808 (Why is no real title available?)
- scientific article; zbMATH DE number 1490041 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- Algorithmic graph theory and its applications
- An effective version of Pólya's theorem on positive definite forms
- Applications of second-order cone programming
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Cones of diagonally dominant matrices
- Global optimization with polynomials and the problem of moments
- On the Shannon capacity of a graph
- On the computational complexity of membership problems for the completely positive cone and its dual
- Optimization over structured subsets of positive semidefinite matrices via column generation
- Positive polynomials in control.
- Reducibility among combinatorial problems
- Second-order cone programming
- Semidefinite Programming
- Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
- Semidefinite programming relaxations for semialgebraic problems
- Sums of squares, moment matrices and optimization over polynomials
- Uniform denominators in Hilbert's seventeenth problem
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
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)
