On the complexity of Schmüdgen's Positivstellensatz

AbstractSchmüdgen's Positivstellensatz roughly states that a polynomial f positive on a compact basic closed semialgebraic subset S of Rn can be written as a sum of polynomials which are non-negative on S for certain obvious reasons. However, in general, you have to allow the degree of the summands to exceed largely the degree of f. Phenomena of this type are one of the main problems in the recently popular approximation of non-convex polynomial optimization problems by semidefinite programs. Prestel (Springer Monographs in Mathematics, Springer, Berlin, 2001) proved that there exists a bound on the degree of the summands computable from the following three parameters: The exact description of S, the degree of f and a measure of how close f is to having a zero on S. Roughly speaking, we make explicit the dependence on the second and third parameter. In doing so, the third parameter enters the bound only polynomially