Perturbed sums-of-squares theorem for polynomial optimization and its applications
From MaRDI portal
Publication:2811486
DOI10.1080/10556788.2015.1052969zbMATH Open1381.90065arXiv1304.0065OpenAlexW1852756082MaRDI QIDQ2811486FDOQ2811486
Authors: Masakazu Muramatsu, Hayato Waki, Levent Tunçel 
Publication date: 10 June 2016
Published in: Optimization Methods \& Software (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1304.0065
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
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Solving semidefinite-quadratic-linear programs using SDPT3
- Title not available (Why is that?)
- Global optimization with polynomials and the problem of moments
- Semidefinite programming relaxations for semialgebraic problems
- Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
- Lower bounds for polynomials using geometric programming
- Lower bounds on the global minimum of a polynomial
- Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
- Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization
- Regularizing the abstract convex program
- An extension of sums of squares relaxations to polynomial optimization problems over symmetric cones
- Sparsity in sums of squares of polynomials
- A note on the representation of positive polynomials with structured sparsity
- Generalized Lagrangian Duals and Sums of Squares Relaxations of Sparse Polynomial Optimization Problems
- A facial reduction algorithm for finding sparse SOS representations
- Global minimization of a multivariate polynomial using matrix methods
- Regularization methods for SDP relaxations in large-scale polynomial optimization
- Semidefinite Approximations for Global Unconstrained Polynomial Optimization
- A Sum of Squares Approximation of Nonnegative Polynomials
- SOS approximations of nonnegative polynomials via simple high degree perturbations
- How to generate weakly infeasible semidefinite programs via Lasserre's relaxations for polynomial optimization
Cited In (7)
- An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex
- Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel
- An exact Jacobian SDP relaxation for polynomial optimization
- Sums of squares polynomial program reformulations for adjustable robust linear optimization problems with separable polynomial decision rules
- A New Look at Nonnegativity on Closed Sets and Polynomial Optimization
- A comprehensive analysis of polyhedral lift-and-project methods
- Univariate polynomial optimization with sum-of-squares interpolants
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)
