Journal
JOURNAL OF COMPLEXITY
Volume 23, Issue 1, Pages 135-150Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jco.2006.07.002
Keywords
positivstellensatz; complexity; positive polynomial; sum of squares; quadratic module; moment problem; optimization of polynomials
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available