Degree Bounds for Putinar’s Positivstellensatz on the Hypercube

DOI10.1137/23M1555430arXiv2302.12558OpenAlexW4391110207MaRDI QIDQ6202884FDOQ6202884

Authors: Lorenzo Baldi, Lucas Slot 

Publication date: 27 February 2024

Published in: SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

Abstract: The Positivstellens"atze of Putinar and Schm"udgen show that any polynomial $f$ positive on a compact semialgebraic set can be represented using sums of squares. Recently, there has been large interest in proving effective versions of these results, namely to show bounds on the required degree of the sums of squares in such representations. These effective Positivstellens"atze have direct implications for the convergence rate of the celebrated moment-SOS hierarchy in polynomial optimization. In this paper, we restrict to the fundamental case of the hypercube $mathrm{B}^n=[-1,1{]}^n$. We show an upper degree bound for Putinar-type representations on $mathrm{B}^n$ of the order $O(f_{max}/f_{min})$, where $f_{max}$, $f_{min}$ are the maximum and minimum of $f$ on $mathrm{B}^n$, respectively. Previously, specialized results of this kind were available only for Schm"udgen-type representations and not for Putinar-type ones. Complementing this upper degree bound, we show a lower degree bound in $Omega(sqrt[8]f_{max}/f_{min})$. This is the first lower bound for Putinar-type representations on a semialgebraic set with nonempty interior described by a standard set of inequalities.

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

zbMATH Keywords

degree boundssums of squaresPositivstellensatzmoment-SOS hierarchy

Mathematics Subject Classification ID

Semialgebraic sets and related spaces (14P10) Real algebra (13J30) Polynomial optimization (90C23)

Cites Work

• Global optimization with polynomials and the problem of moments
• Title not available (Why is that?)
• The \(K\)-moment problem for compact semi-algebraic sets
• A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
• Sums of squares, moment matrices and optimization over polynomials
• Title not available (Why is that?)
• On the complexity of Putinar's Positivstellensatz
• Sums of squares on real algebraic curves
• Anneaux preordonnes
• Positive polynomials and sums of squares
• Exposed faces of semidefinitely representable sets
• Positive polynomials and projections of spectrahedra
• Distinguished representations of non-negative polynomials
• Complexity estimates for the Schmüdgen Positivstellensatz
• On the complexity of Schmüdgen's Positivstellensatz
• Sums of squares on real algebraic surfaces
• Positivity, sums of squares and the multi-dimensional moment problem
• Non-existence of degree bounds for weighted sums of squares representations
• The moment problem for non-compact semialgebraic sets
• Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube
• Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications
• Bounds for the derivatives of polynomials on centrally symmetric convex bodies
• A proof of Markov's theorem for polynomials on Banach spaces
• Semidefinite Representation for Convex Hulls of Real Algebraic Curves
• An effective version of Schmüdgen's Positivstellensatz for the hypercube
• On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy
• Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel
• The sum-of-squares hierarchy on the sphere and applications in quantum information theory
• Error bounds for polynomial optimization over the hypercube using Putinar type representations
• On the effective Putinar's Positivstellensatz and moment approximation
• Exponential Convergence of Sum-of-Squares Hierarchies for Trigonometric Polynomials

Cited In (1)

• On Łojasiewicz inequalities and the effective Putinar's Positivstellensatz

This page was built for publication: Degree Bounds for Putinar’s Positivstellensatz on the Hypercube

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