Moment Matrices and Optimization over Polynomials
We consider the problem of minimizing a polynomial over a semialgebraic set defined by polynomial equations and inequalities, which is NP-hard in general. Hierarchies of semidefinite relaxations have been proposed, in particular, by Lasserre and by Parrilo, based on positive semidefinite moment matrices and the dual theory of sums of squares of polynomials. We present these hierachies of approximations and their main properties: asymptotic/finite convergence, optimality certificate, and extraction of global optimum solutions. We discuss the mathematical tools underlying these properties, in particular, some results about moment matrices of Curto and Fialkow, and the algebraic eigenvalue method for solving zero-dimensional systems of polynomial equations. We also discuss some sums of squares representation results for nonnegative polynomials modulo their gradient variety, with applications to unconstrained polynomial minimization. Our objective is whenever possible to provide detailed proofs and background.
draft text for the participants
part 1 of 3
part 2 of 3
part 3 of 3