Error Bounds for Some Semidefinite Programming Approaches to Polynomial Minimization on the Hypercube

DOI10.1137/100790835zbMath1229.90279OpenAlexW2112356323MaRDI QIDQ3083323

Etienne de Klerk, Monique Laurent

Publication date: 21 March 2011

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/100790835

zbMATH Keywords

semidefinite programmingPositivstellensatzpositive polynomialsum of squares of polynomialsmultivariate Bernstein approximationbound constrained optimization of polynomials

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Nonconvex programming, global optimization (90C26) Derivative-free methods and methods using generalized derivatives (90C56)

Related Items (24)

Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel ⋮ A few more extensions of Putinar's Positivstellensatz to non-compact sets ⋮ Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications ⋮ Error bounds for monomial convexification in polynomial optimization ⋮ Rank of Handelman hierarchy for Max-Cut ⋮ Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube ⋮ Construction of Multivariate Polynomial Approximation Kernels via Semidefinite Programming ⋮ Degree Bounds for Putinar’s Positivstellensatz on the Hypercube ⋮ An effective version of Schmüdgen's Positivstellensatz for the hypercube ⋮ A version of Putinar's Positivstellensatz for cylinders ⋮ A Survey of Semidefinite Programming Approaches to the Generalized Problem of Moments and Their Error Analysis ⋮ Handelman's hierarchy for the maximum stable set problem ⋮ A refined error analysis for fixed-degree polynomial optimization over the simplex ⋮ LP Formulations for Polynomial Optimization Problems ⋮ A note on total degree polynomial optimization by Chebyshev grids ⋮ Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization ⋮ An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming ⋮ Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets ⋮ Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization ⋮ On Łojasiewicz inequalities and the effective Putinar's Positivstellensatz ⋮ Inhomogeneous polynomial optimization over a convex set: An approximation approach ⋮ An Error Analysis for Polynomial Optimization over the Simplex Based on the Multivariate Hypergeometric Distribution ⋮ An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex ⋮ Error bounds for polynomial optimization over the hypercube using Putinar type representations

Uses Software

• GloptiPoly

This page was built for publication: Error Bounds for Some Semidefinite Programming Approaches to Polynomial Minimization on the Hypercube