Error bounds for polynomial optimization over the hypercube using Putinar type representations

DOI10.1007/S11590-014-0797-8MaRDI QIDQ2355314zbMATH OpenOpenAlexFDO

Authors Victor Magron

Publication date 22 July 2015

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.6145

zbMATH Keywords

multivariate Bernstein approximationpositive polynomialPositivstellensatzpreorderingquadratic modulesemidefinite programmingsums of squares relaxations

Mathematics Subject Classification ID

Semialgebraic sets and related spaces (14P10) Semidefinite programming (90C22) Nonlinear programming (90C30)

Abstract: Consider the optimization problem $p_{min,Q}:=mi{n}_{mathbfxinQ}p(mathbfx)$, where $p$ is a degree $m$ multivariate polynomial and $Q:=[0,1{]}^n$ is the hypercube. We provide explicit degree and error bounds for the sums of squares approximations of $p_{min,Q}$ corresponding to the Positivstellensatz of Putinar. Our approach uses Bernstein multivariate approximation of polynomials, following the methodology of De Klerk and Laurent to provide error bounds for Schm"udgen type positivity certificates over the hypercube. We give new bounds for Putinar type representations by relating the quadratic module and the preordering associated with the polynomials $g_i:=x_i(1-x_i),:i=1,dots,n$, describing the hypercube $Q$.

Recommendations

• Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube
• Sums of squares on the hypercube
• scientific article; zbMATH DE number 7305739
• Sum-of-squares hierarchies for binary polynomial optimization
• Sum-of-squares hierarchies for binary polynomial optimization

Cites work

• Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube
• Global optimization with polynomials and the problem of moments
• scientific article; zbMATH DE number 527343 (Why is no real title available?)
• scientific article; zbMATH DE number 3193809 (Why is no real title available?)
• On the complexity of Putinar's Positivstellensatz
• On the complexity of Schmüdgen's Positivstellensatz
• Representing polynomials by positive linear functions on compact convex polyhedra
• Semidefinite programming relaxations for semialgebraic problems
• Sums of squares, moment matrices and optimization over polynomials
• The K-moment problem for compact semi-algebraic sets

Cited in

(8)

• A few more extensions of Putinar's Positivstellensatz to non-compact sets
• A version of Putinar's Positivstellensatz for cylinders
• An effective version of Schmüdgen's Positivstellensatz for the hypercube
• Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube
• Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube
• scientific article; zbMATH DE number 7305739 (Why is no real title available?)
• Error Estimates in the Optimization of Degree Two Polynomials on a Discrete Hypercube
• Degree Bounds for Putinar’s Positivstellensatz on the Hypercube

This page was built for publication: Error bounds for polynomial optimization over the hypercube using Putinar type representations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2355314)