Sum of squares basis pursuit with linear and second order cone programming
From MaRDI portal
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
- 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
- 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?)
- On the computational complexity of membership problems for the completely positive cone and its dual
- On the Shannon capacity of a graph
- Optimization over structured subsets of positive semidefinite matrices via column generation
- Positive polynomials in control.
- Reducibility among combinatorial problems
- Second-order cone programming
- Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
- Semidefinite Programming
- Semidefinite programming relaxations for semialgebraic problems
- Sums of squares, moment matrices and optimization over polynomials
- Uniform denominators in Hilbert's seventeenth problem
Cited in
(19)- Decomposed structured subsets for semidefinite and sum-of-squares optimization
- Multistage distributionally robust mixed-integer programming with decision-dependent moment-based ambiguity sets
- Maximum feasible subsystems of distance geometry constraints
- Outer approximation with conic certificates for mixed-integer convex problems
- Generating valid linear inequalities for nonlinear programs via sums of squares
- Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices
- On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones
- Diagonally dominant programming in distance geometry
- Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit
- Sum-of-squares optimization without semidefinite programming
- Bounding extreme events in nonlinear dynamics using convex optimization
- Bounding extrema over global attractors using polynomial optimisation
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
- An overview and comparison of spectral bundle methods for primal and dual semidefinite programs
- The duality of SONC: advances in circuit-based certificates
- A predictor-corrector algorithm for semidefinite programming that uses the factor width cone
- Instance-specific linear relaxations of semidefinite optimization problems
- Polynomial optimization for nonlinear dynamics: theory, algorithms and applications. Abstracts from the workshop held July 28 -- August 2, 2024
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)
