# Optimization Over Polynomials with Moment Matrices and Sums of Squares

Friday, January 12, 2007 - 2:40pm - 3:30pm

EE/CS 3-180

Jean Lasserre (Centre National de la Recherche Scientifique (CNRS))

Remarks: (Due to visa problems Monique Laurent was not be able to attend the tutorial. Jean Bernard Lasserre substituted for Monique Laurent.)

We consider the problem (P) of minimizing a polynomial function over a semialgebraic set defined by polynomial inequalities and equations. This is a hard problem, which includes well known NP-hard instances such as 0/1 linear programming, the partition problem for integer sequences, or matrix copositivity.

While it is hard to test whether a polynomial is nonnegative, one can test efficiently whether it can be written as a sum of squares of polynomials using semidefinite programming. Based on this paradigm, one can formulate tractable semidefinite programming relaxations for (P) by replacing the hard 'nonnegativity' condition by the tractable 'sum of squares'

condition. The corresponding dual semidefinite programs involve positive

semidefinite moment matrices, which reflects the classical duality theory

between positive polynomials and moment sequences.

The objective of this tutorial is to present in detail the main properties

of these semidefinite programming relaxations: asymptotic/finite

convergence, optimality certificate, and extraction of global optimum

solutions for (P), and to review the underlying mathematical tools:

representation theorems for positive polynomials from real algebraic

geometry, results about the truncated moment problem, and the algebraic

eigenvalue method for solving systems of polynomial equations. These

characteristic features are implemented in GloptiPoly, a solver for

polynomial optimization developped by Henrion and Lasserre, and will be

demonstrated on examples. Additional topics that may be covered if time

allows include: various algebraic approaches to unconstrained polynomial

minimization, link to combinatorial methods for 0/1 polynomial

optimization, techniques for exploiting symmetry, sparsity, etc.

We consider the problem (P) of minimizing a polynomial function over a semialgebraic set defined by polynomial inequalities and equations. This is a hard problem, which includes well known NP-hard instances such as 0/1 linear programming, the partition problem for integer sequences, or matrix copositivity.

While it is hard to test whether a polynomial is nonnegative, one can test efficiently whether it can be written as a sum of squares of polynomials using semidefinite programming. Based on this paradigm, one can formulate tractable semidefinite programming relaxations for (P) by replacing the hard 'nonnegativity' condition by the tractable 'sum of squares'

condition. The corresponding dual semidefinite programs involve positive

semidefinite moment matrices, which reflects the classical duality theory

between positive polynomials and moment sequences.

The objective of this tutorial is to present in detail the main properties

of these semidefinite programming relaxations: asymptotic/finite

convergence, optimality certificate, and extraction of global optimum

solutions for (P), and to review the underlying mathematical tools:

representation theorems for positive polynomials from real algebraic

geometry, results about the truncated moment problem, and the algebraic

eigenvalue method for solving systems of polynomial equations. These

characteristic features are implemented in GloptiPoly, a solver for

polynomial optimization developped by Henrion and Lasserre, and will be

demonstrated on examples. Additional topics that may be covered if time

allows include: various algebraic approaches to unconstrained polynomial

minimization, link to combinatorial methods for 0/1 polynomial

optimization, techniques for exploiting symmetry, sparsity, etc.