A new proof for the existence of degree bounds for Putinar's positivstellensatz

DOI10.1090/CONM/697/14053MaRDI QIDQ4635365zbMATH OpenOpenAlexFDO

Authors Tom-Lukas Kriel

Publication date 16 April 2018

Published in Ordered Algebraic Structures and Related Topics (Search for Journal in Brave)

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

zbMATH Keywords

degree boundsquadratic modulePutinar's positivstellensatz

Mathematics Subject Classification ID

Semialgebraic sets and related spaces (14P10) Sums of squares and representations by other particular quadratic forms (11E25)

Abstract: Putinar's Positivstellensatz is a central theorem in real algebraic geometry. It states the following: If you have a set $S=xin{R}^n|g_1(x)geq0,\mathrm{...},g_m(x)geq0$ described by some real polynomials $g_i$, then every real polynomial $f$ that is positive on $S$ can be written as a sum of squares weighted by the $g_i$ and $1$. Consider such an identity $f=su{m}_{i=1}^m{g}_i{s}_i+s_0$. For the applications in polynomial optimization, especially semidefinite programming, the following is important: There exists a bound $N$ for the degrees of the $s_i$ which depends only on the $g_i$, $n$, the degree of $f$, an upper bound for $||f||$ and a lower bound for $minf(S)$. Two proofs from Prestel and He{ss} resp. Schweighofer and Nie ([Pr], [He] resp. [Sw], [NS]) for the existence of these degree bounds are known (also for the matrix version of Putinar's Positivstellensatz by Helton and Nie [HN]). Prestel uses valuation and model theory for his approach while Schweighofer gives a constructive solution by using a theorem of P'{o}lya. In this paper we will give a new elementary, short but non-constructive proof.

Recommendations

• On the complexity of Putinar's Positivstellensatz
• On the complexity of Schmüdgen's Positivstellensatz
• scientific article; zbMATH DE number 1824112
• Constructive proofs of some positivstellensätze for compact semialgebraic subsets of \(\mathbb R^{d }\)
• On the complexity of Putinar-Vasilescu's Positivstellensatz

Cites work

• scientific article; zbMATH DE number 1824112 (Why is no real title available?)
• scientific article; zbMATH DE number 527343 (Why is no real title available?)
• Approximation algorithms and semidefinite programming.
• Convex sets with semidefinite representation
• Exposed faces of semidefinitely representable sets
• Matrix sum-of-squares relaxations for robust semi-definite programs
• On the complexity of Putinar's Positivstellensatz
• On the complexity of Schmüdgen's Positivstellensatz
• Positive polynomials and sums of squares
• Semidefinite representation of convex sets
• Sums of squares, moment matrices and optimization over polynomials
• The K-moment problem for compact semi-algebraic sets

Cited in

(12)

• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• On the exactness of Lasserre relaxations for compact convex basic closed semialgebraic sets
• scientific article; zbMATH DE number 4068934 (Why is no real title available?)
• On the complexity of Putinar's Positivstellensatz
• A version of Putinar's Positivstellensatz for cylinders
• On the complexity of Schmüdgen's Positivstellensatz
• Degree Bounds for Putinar’s Positivstellensatz on the Hypercube
• On Łojasiewicz inequalities and the effective Putinar's Positivstellensatz
• On the Generation of Positivstellensatz Witnesses in Degenerate Cases
• On the effective Putinar's Positivstellensatz and moment approximation
• A Positivstellensatz for projective real varieties
• On the complexity of Putinar-Vasilescu's Positivstellensatz

This page was built for publication: A new proof for the existence of degree bounds for Putinar's positivstellensatz

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