Degree Bounds for Positivstellensätze of general semialgebraic sets
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917513890103296 |
|---|---|
| author | Heijmans-Kuryatnikova, Olga Vera, Juan C. Zuluaga, Luis F. |
| author_facet | Heijmans-Kuryatnikova, Olga Vera, Juan C. Zuluaga, Luis F. |
| contents | Let $p_{\min}$ denote the minimum of a polynomial $p$ over a (general) compact semialgebraic set $S \subseteq \mathbb{R}^n$. A standard way to approximate $p_{\min}$ is via hierarchies built from Positivstellensätze, which certify nonnegativity of polynomials on $S$ using sums of squares or other classes of globally nonnegative polynomials. As the degree of the certificate grows, the values generated by these hierarchies converge asymptotically to $p_{\min}$. A natural question is, then, to determine explicit bounds on the certificate's degree needed to obtain a prescribed $\varepsilon$-approximation to $p_{\min}$, or equivalently certify the positivity of $f:=p - p_{\min} + \varepsilon$ on $S$. We improve the current best degree bounds for Putinar's and Schmüdgen's SOS-Positivstellensatz over $S$. Also, we obtain degree bounds for Krivine--Stengle's and the recently introduced extended-Handelman's $\mathbb{R}_+$-Positivstellensätze over $S$; providing the first explicit degree bounds for linear optimization-based hierarchies over general compact semialgebraic sets. Our approach is based on a lift-and-project construction in which we add new variables to construct an algebraic representation of the distance to the set $S$ using Łojasiewicz's inequality. This lets us lift the problem of certifying the positivity of $f$ on the (complex) set $S$ to the problem of certifying the positivity of a related polynomial $F$ on a higher-dimensional hypercube. By projecting out the added variables, non-negativity certificates for $F$ on the hypercube become non-negativity certificates for $f$ on $S$. Our approach offers a unified methodology to obtain degree bounds for several Positivstellensatz-based hierarchies over general compact sets, narrowing the gap between results for the hypercube (or other simple sets) and more general semialgebraic sets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_15821 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Degree Bounds for Positivstellensätze of general semialgebraic sets Heijmans-Kuryatnikova, Olga Vera, Juan C. Zuluaga, Luis F. Optimization and Control 90C23 Let $p_{\min}$ denote the minimum of a polynomial $p$ over a (general) compact semialgebraic set $S \subseteq \mathbb{R}^n$. A standard way to approximate $p_{\min}$ is via hierarchies built from Positivstellensätze, which certify nonnegativity of polynomials on $S$ using sums of squares or other classes of globally nonnegative polynomials. As the degree of the certificate grows, the values generated by these hierarchies converge asymptotically to $p_{\min}$. A natural question is, then, to determine explicit bounds on the certificate's degree needed to obtain a prescribed $\varepsilon$-approximation to $p_{\min}$, or equivalently certify the positivity of $f:=p - p_{\min} + \varepsilon$ on $S$. We improve the current best degree bounds for Putinar's and Schmüdgen's SOS-Positivstellensatz over $S$. Also, we obtain degree bounds for Krivine--Stengle's and the recently introduced extended-Handelman's $\mathbb{R}_+$-Positivstellensätze over $S$; providing the first explicit degree bounds for linear optimization-based hierarchies over general compact semialgebraic sets. Our approach is based on a lift-and-project construction in which we add new variables to construct an algebraic representation of the distance to the set $S$ using Łojasiewicz's inequality. This lets us lift the problem of certifying the positivity of $f$ on the (complex) set $S$ to the problem of certifying the positivity of a related polynomial $F$ on a higher-dimensional hypercube. By projecting out the added variables, non-negativity certificates for $F$ on the hypercube become non-negativity certificates for $f$ on $S$. Our approach offers a unified methodology to obtain degree bounds for several Positivstellensatz-based hierarchies over general compact sets, narrowing the gap between results for the hypercube (or other simple sets) and more general semialgebraic sets. |
| title | Degree Bounds for Positivstellensätze of general semialgebraic sets |
| topic | Optimization and Control 90C23 |
| url | https://arxiv.org/abs/2605.15821 |