Degree Bounds for Putinar’s Positivstellensatz on the Hypercube

DOI10.1137/23M1555430OpenAlexW4391110207MaRDI 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

Recommendations

• On the effective Putinar's Positivstellensatz and moment approximation
• Error bounds for polynomial optimization over the hypercube using Putinar type representations
• On the complexity of Putinar-Vasilescu's Positivstellensatz
• On the complexity of Putinar's Positivstellensatz
• A new proof for the existence of degree bounds for Putinar's positivstellensatz

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

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

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)