A new proof for the existence of degree bounds for Putinar’s Positivstellensatz

DOI10.1090/CONM/697/14053zbMATH Open1426.11025arXiv1603.06853OpenAlexW2309521632MaRDI QIDQ4635365FDOQ4635365

Tom-Lukas Kriel

Publication date: 16 April 2018

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

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.

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)

Cites Work

• The \(K\)-moment problem for compact semi-algebraic sets
• Matrix sum-of-squares relaxations for robust semi-definite programs
• On the complexity of Putinar's Positivstellensatz
• Exposed Faces of Semidefinitely Representable Sets
• On the complexity of Schmüdgen's Positivstellensatz
• Approximation Algorithms and Semidefinite Programming
• Semidefinite representation of convex sets
• Convex sets with semidefinite representation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (6)

• Title not available (Why is that?)
• A version of Putinar's Positivstellensatz for cylinders
• On the Exactness of Lasserre Relaxations for Compact Convex Basic Closed Semialgebraic Sets
• On the Generation of Positivstellensatz Witnesses in Degenerate Cases
• A Positivstellensatz for projective real varieties
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity

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)