On the complexity of Putinar's Positivstellensatz (Q870344)

Let \(g_1,\dots,g_m \in \mathbb R[X_1,\ldots, X_n]\), the ring of real polynomials in the indeterminates \(X_1,\ldots,X_n\). Let \(S = \{x\in \mathbb R^n:g_1(x)\geq 0,\ldots,g_m(x)\geq 0\}\) be the basic closed semialgebraic set defined by \(g_1,\ldots,g_m\). Denote by \(M\) the set of all \(\sum_{i=0}^m\sigma_ig_i\), where \(g_0:=1\) and each \(\sigma_i\) is a sum of squares of polynomials in \(\mathbb R[X_1,\ldots, X_n]\). The set \(M\) is said to be archimedean if there exists a natural number \(N\) such that \(N-\sum_{i=1}^n X_i^2 \in M\). The Positivstellensatz of \textit{M. Putinar} [Indiana Univ. Math. J. 42, No. 3, 969--984 (1993; Zbl 0796.12002)] states that if \(M\) is archimedean and if \(f>0\) holds on \(S\) for some \(f\in \mathbb R[X_1,\ldots, X_n]\), then \(f \in M\). In the present paper, the authors give a bound on the degrees of the terms \(\sigma_i g_i\) in the representation \(f=\sum_{i=0}^m\sigma_ig_i\) which depends on the description of \(S\), the degree of \(f\) and a measure of how close \(f\) is to having a zero on \(S\). As a consequence, information is obtained on the rate of convergence of a procedure of \textit{J. Laserre} [SIAM J. Optim. 11, No. 3, 796--817 (2001; Zbl 1010.90061)] for the optimization of a polynomial subject to polynomial inequality constraints. In special cases, the existence of such a degree bound was established by \textit{A. Prestel} [Fields Inst. Commun. 32, 253--260 (2002; Zbl 1015.14030)] using model theory and valuation theory.