Perturbed sums-of-squares theorem for polynomial optimization and its applications
From MaRDI portal
Publication:2811486
Abstract: We consider a property of positive polynomials on a compact set with a small perturbation. When applied to a Polynomial Optimization Problem (POP), the property implies that the optimal value of the corresponding SemiDefinite Programming (SDP) relaxation with sufficiently large relaxation order is bounded from below by and from above by , where is the optimal value of the POP. We propose new SDP relaxations for POP based on modifications of existing sums-of-squares representation theorems. An advantage of our SDP relaxations is that in many cases they are of considerably smaller dimension than those originally proposed by Lasserre. We present some applications and the results of our computational experiments.
Recommendations
- A Sum of Squares Approximation of Nonnegative Polynomials
- An extension of sums of squares relaxations to polynomial optimization problems over symmetric cones
- EQUALITY BASED CONTRACTION OF SEMIDEFINITE PROGRAMMING RELAXATIONS IN POLYNOMIAL OPTIMIZATION
- An exact Jacobian SDP relaxation for polynomial optimization
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
Cites work
- scientific article; zbMATH DE number 715155 (Why is no real title available?)
- A Sum of Squares Approximation of Nonnegative Polynomials
- A facial reduction algorithm for finding sparse SOS representations
- A note on the representation of positive polynomials with structured sparsity
- An extension of sums of squares relaxations to polynomial optimization problems over symmetric cones
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
- Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
- Generalized Lagrangian Duals and Sums of Squares Relaxations of Sparse Polynomial Optimization Problems
- Global minimization of a multivariate polynomial using matrix methods
- Global optimization with polynomials and the problem of moments
- How to generate weakly infeasible semidefinite programs via Lasserre's relaxations for polynomial optimization
- Lower bounds for polynomials using geometric programming
- Lower bounds on the global minimum of a polynomial
- Regularization methods for SDP relaxations in large-scale polynomial optimization
- Regularizing the abstract convex program
- SOS approximations of nonnegative polynomials via simple high degree perturbations
- Semidefinite Approximations for Global Unconstrained Polynomial Optimization
- Semidefinite programming relaxations for semialgebraic problems
- Solving semidefinite-quadratic-linear programs using SDPT3
- Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials
- Sparsity in sums of squares of polynomials
- Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Cited in
(8)- A comprehensive analysis of polyhedral lift-and-project methods
- Approximation bound analysis based on the tight constraints polynomial optimization problems of Lasserre relaxation
- Univariate polynomial optimization with sum-of-squares interpolants
- An exact Jacobian SDP relaxation for polynomial optimization
- Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel
- A New Look at Nonnegativity on Closed Sets and Polynomial Optimization
- An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex
- Sums of squares polynomial program reformulations for adjustable robust linear optimization problems with separable polynomial decision rules
This page was built for publication: Perturbed sums-of-squares theorem for polynomial optimization and its applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2811486)
