Home | Contact | About MOS | Membership | Publications | Prizes | Meetings | IPCO | ISMP | Links | Album | Jobs
Mathematical Optimization Society

MOS Prizes

MPS Prizes


2009 Lagrange Prize Citation

Jean B. Lasserre,
"A sum of squares approximation of nonnegative polynomials",
SIAM Journal on Optimization 16 (2006), 751-765.
(The paper was also reproduced in the SIGEST section of SIAM Review 49 (2007), 651-669.)

Lasserre has been a pioneer in the field of global polynomial optimization since his 2001 paper "Global optimization with polynomials and the problem of moments", SIOPT 11, 796-817. His approach relies on certificates of positivity for polynomials on compact sets defined by polynomial inequalities, using representations as sums of squared polynomials - a deep and powerful technique taken from real algebraic geometry. Using semidefinite programming to recognize sums of squares, Lasserre constructs a hierarchy of semidefinite relaxations converging to a solution of the (NP hard!) global optimization p roblem. The convergence is often fast or even finite in practice, as illustrated in software packages such as GloptiPoly, SOSTOOLS and SPARSEPOPT. The duality theory for the semidefinite relaxations corres ponds exactly to the duality between polynomial optimization and generalized moment problems, a relationship explored in great generality in Lasserre's paper "A semidefinite programming approach to the gene ralized problem of moments", Mathematical Programming 112 (2008), 65-92.

The winning paper is a particularly striking exemplar of Lasserre's work on polynomial optimization. He presents an elegant new proof of a classical foundation stone for the theory: that any nonne gative polynomial can be approximated by sums of squares. Combining convex duality theory and a moment-theoretic result, he constructs approximating polynomials that are both simple and explicit. One conse quence is a satisfying simplification of his original relaxation hierarchy. The paper is a beautiful blend of modern optimization theory and deep classical mathematics, with striking computational implicat ions.