Real Algebraic and Analytic Geometry
Submission: 2004, August 24.
We give a short introduction to Lasserre's method for minimizing a polynomial on a compact basic closed semialgebraic set. It consists of successively solving tighter and tighter convex relaxations of this problem which can be formulated as semidefinite programs. We give a new short proof for the convergence of the optimal values of these relaxations to the minimum which is constructive and elementary. In the case that there is a unique minimizer, we prove that every sequence of nearly optimal solutions of the successive relaxations gives rise to a sequence of points converging to this minimizer.
Mathematics Subject Classification (2000): 90C26, 13J30, 44A60, 14P10, 11E25.
Keywords and Phrases: nonconvex optimization, positive polynomial, sum of squares, moment problem, Positivstellensatz, semidefinite programming.
Full text, 21p.: dvi 104k, ps.gz 166k, pdf 263k.