Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


The moment-LP and moment-SOS approach in Optimization

We review and compare basic properties of the moment-LP and moment-SOS hierarchies for polynomial optimization problems P: min {f(x): x in K} where "f" is a polynomial and "K" is a compact basic semi-algebraic set. Thanks to powerful positivity certificates from real algebraic geometry, both approaches provide a sequence of lower bounds which converge to the global minimum of P: We also describe an alternative hierarchy based on a different characterization of nonnegativity on K which now yields a sequence of upper bounds that converges to the global minimum of P (provided that the (non necessarily compact) set K is such that one may compute moments of a measure whose support is exactly K).

Type of Seminar:
Optimization and Applications Seminar
Prof. Jean Bernard Lasserre
LAAS-CNRS, Toulouse
Mar 03, 2014   16:30

HG G 19.1
Contact Person:

Prof. John Lygeros
File Download:

Request a copy of this publication.
Biographical Sketch:
Jean B. Lasserre graduated from "Ecole Nationale Superieure d'Informatique et Mathematiques Appliquees" (ENSIMAG) in Grenoble (France), then got his PhD (1978) and "Doctorat d'Etat" (1984) degrees both from the University of Toulouse (France). Since 1980 he has been at LAAS-CNRS in Toulouse where he is currently "Directeur de Recherche" and is also an associate member of the Institute of Mathematics of Toulouse. He was a one year visitor (1978-79 and 1985-86) at the Electrical Engineering Dept. of the University of California at Berkeley with a fellowship from INRIA and NSF. He is the recipient of the 2009 Lagrange Prize in Optimization, has published over 130 journal articles and is author of the books "Modern Optimization Modelling Techniques" with R. Cominetti and F. Facchinei, Springer 2012), "Moments, Positive Polynomials and Their Applications (Imperial College, 2009), "Linear and Integer Programming vs Linear Integration and Counting" (Springer 2009), and co-author with O. Hernandez-Lerma of the books "Markov Chains and Invariant Probabilities" (Birkhauser, 2003), "Discrete-Time Markov Control Processes: Basic Optimality Criteria" (Springer, 1996), and "Further Topics ion Discrete-Time Markov Control Processes" (Springer, 1999). he is also co-editor with M. Anjos of "Handbook on Semidefinite, Conic and Polynomial Optimization", Springer 2011.