Skip to yearly menu bar Skip to main content

Workshop: Nonconvex Optimization for Machine Learning: Theory and Practice

The moment-LP and moment-SOS approaches in optimization and some related applications

Jean Lasserre


In a first part we provide an introduction to the basics of the moment-LP and moment-SOS approaches to global polynomial optimization. In particular, we describe the hierarchy of LP and semidefinite programs to approximate the optimal value of such problems. In fact, the same methodology also applies to solve (or approximate) Generalized Moment Problems (GMP) whose data are described by basic semi-algebraic sets and polynomials (or even semi-algebraic functions). Indeed, Polynomial optimization is a particular (and even the simplest) instance of the GMP.

In a second part, we describe how to use this methodology for solving some problems (outside optimization) viewed as particular instances of the GMP. This includes: - Approximating compact basic semi-algebraic sets defined by quantifiers. - Computing convex polynomials underestimators of polynomials on a box. - Bounds on measures satisfying some moment conditions. - Approximating the volume of compact basic semi-algebraic sets. - Approximating the Gaussian measure of non-compact basic semi-algebraic sets. - Approximating the Lebesgue decomposition of a measure μ w.r.t. another measure ν, based only on the moments of μ and ν.

Live content is unavailable. Log in and register to view live content