Real Algebraic and Analytic Geometry

Preprint Server

Previous   Next
56. Markus Schweighofer:
Optimization of polynomials on compact semialgebraic sets.


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.

Server Home Page