2014
2015
2016
2017
2018
2019
2020
2022

The 50th meeting of the Prague computer science seminar

Didier Henrion

The Moment-SOS Hierarchy

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.

November 10, 2022

4:15pm

Auditorium C-132, FEL CTU
Technická 2, Praha 6
Show on the map

Lecture annotation

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.

Lecturer

Didier Henrion

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. He seeks to unveil links between convex optimization, real algebraic geometry, functional analysis and dynamical systems, and to exploit them to approach classical problems of systems control theory from a new perspective. Since the late 1990s, he has been a key contributor to polynomial optimization and polynomial optimal control. In 2004 he was awarded the Bronze Medal from CNRS, for his achievements in systems control theory. In 2005 he was awarded, jointly with Fredrik Kahl, the David Marr Prize for the best paper at the International Conference on Computer Vision. In 2012 he was awarded, jointly with Jérôme Malick, the Charles Broyden prize for the best paper in the journal Optimization Methods and Software. In 2016 he was awarded, jointly with Cédric Josz, the Optimization Letters Best Paper Award. He is the recipient of the IFAC French NMO Award 2020.

ABOUT THE PRAGUE COMPUTER SCIENCE SEMINAR

The seminar typically takes place on Thursdays at 4:15pm in lecture rooms of the Czech Technical University in Prague or the Charles University.

Its program consists of a one-hour lecture followed by a discussion. The lecture is based on an (internationally) exceptional or remarkable achievement of the lecturer, presented in a way which is comprehensible and interesting to a broad computer science community. The lectures are in English.

The seminar is organized by the organizational committee consisting of Roman Barták (Charles University, Faculty of Mathematics and Physics), Jaroslav Hlinka (Czech Academy of Sciences, Computer Science Institute), Michal Chytil, Pavel Kordík (CTU in Prague, Faculty of Information Technologies), Michal Koucký (Charles University, Faculty of Mathematics and Physics), Jan Kybic (CTU in Prague, Faculty of Electrical Engineering), Michal Pěchouček (CTU in Prague, Faculty of Electrical Engineering), Jiří Sgall (Charles University, Faculty of Mathematics and Physics), Vojtěch Svátek (University of Economics, Faculty of Informatics and Statistics), Michal Šorel (Czech Academy of Sciences, Institute of Information Theory and Automation), Tomáš Werner (CTU in Prague, Faculty of Electrical Engineering), and Filip Železný (CTU in Prague, Faculty of Electrical Engineering)

The idea to organize this seminar emerged in discussions of the representatives of several research institutes on how to avoid the undesired fragmentation of the Czech computer science community.

Supporters

Contact

Prague computer science seminar is suspended until further notice to prevent spread of the new coronavirus.