On the complexity of Putinar's Positivstellensatz

Let S = {x is an element of R-n \g(1) (x) >= 0,..., g(m), (x) >= 0} be a basic closed semialgebraic set defined by real polynomials g(i). Putinar's Positivstellensatz says that, under a certain condition stronger than compactness of S, every real polynomial f positive on S possesses a representation f = Sigma(m)(i=o) sigma(i)g(i) where g(o) := 1 and each sigma(i) is a sum of squares of polynomials. Such a representation is a certificate for the nonnegativity of f on S. We give a bound on the degrees of the terms sigma(i)g(i) in this representation 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, we get information about the convergence rate of Lasserre's procedure for optimization of a polynomial subject to polynomial constraints. (c) 2006 Elsevier Inc. All rights reserved.