SDP and LP-relaxations in polynomial optimization: The power of real algebraic geometry

Wednesday, January 31, 2007 - 11:15am - 12:15pm
Lind 305
Jean Lasserre (Centre National de la Recherche Scientifique (CNRS))
In this seminar we consider the general polynomial optimization problem: that is, finding the GLOBAL minimum of a polynomial over a compact basic semi-algebraic set, a NP-hard problem. We will describe how powerfull representation results in real algebraic geometry are exploited to build up a hierarchy of linear or semidefinite programming (LP or SDP) relaxations, whose monotone sequence of optimal values converges to the desired value. A comparison with the usual Kuhn-Tucker local optimality conditions is also discussed.