Didier Henrion presents 50th Prague Computer Science Seminar: The Moment-SOS Hierarchy

Didier Henrion is a senior researcher at the Laboratory of Analysis and
Architecture of Systems (LAAS) of the National Center for Scientific Research
(CNRS) in Toulouse, France. He is also a Professor at the Department of Control
Engineering of the Faculty of Electrical Engineering of the Czech Technical
University in Prague. His main research interest is in polynomial optimization
for systems control.

ABSTRACT:
The polynomial optimization problem (POP) is a very general problem which seeks
to minimize a polynomial of many real variables subject to polynomial
inequalities. Its special case is the problem of finding real solutions of a
system of polynomial equalities and inequalities. This NP-hard problem has many
applications in fields such as statistics, signal processing, machine learning,
computer vision, computational geometry, and control engineering.

The Moment-SOS hierarchy is an approach to the POP that allows us to solve it
globally at the price of solving a family of convex (semidefinite) optimization
problems of increasing size. The lecture will introduce the approach, describe
its main milestones during the last two decades (including the contributions of
the speaker) and applications in statistics, signal processing and control. The
focus will be on the computational features of the Moment-SOS hierarchy, its
limitations and current efforts to overcome them.