Polynomial optimization and optimal control


Didier Henrion, CNRS "Directeur de Recherche" (senior researcher) at LAAS, Toulouse, France and Professor at the Department of Automatic Control of the Faculty of Electrical Engineering of the Czech Technical University in Prague.

Schedule and place

This 15-hour course will take place in 6 sessions over three days on November 16,17,18 2020 


  •  November 16, 17, 18 : from 9:30 to 12:15 and 13:15 to 16:00

Teaching method:

The course will be entirely online. The connection information to attend the lectures will be communicated by email to the registered students before the start of the course.

The registration deadline is Wednesday 11 November 2020.


Abstract: First, we survey a mathematical technology introduced in 2000 by Jean Bernard Lasserre to solve globally non-convex optimization problems on multivariate polynomials with the help of a hierarchy of convex semidefinite programming problems (linear matrix inequalities or LMI = linear programming problems in the cone of positive semidefinite matrices). Instrumental to the development of this technique is the duality between the cone of positive polynomials (real algebraic geometry) and the cone of moments (functional analysis). These basic objects are introduced and studied in detail, with a special focus on conic optimization duality, and some illustrative examples are described.

Then in a second part, we study polynomial optimal control, which consists of minimizing a polynomial Lagrangian over a polynomial vector field subject to semi-algebraic control and state constraints, typically a nonconvex problem for which there is no solution in classical Lebesgue spaces. To overcome this, polynomial optimal control problems are first formulated as linear programming (LP) problems in the cone of occupation measures (standard objects in Markov decision processes and ergodic theory of dynamical systems), and infinite-dimensional convex duality is used to establish the link with subsolutions of the Hamilton-Jacobi-Bellman (HJB) partial differential equation satisfied by the value function. Then, the Lasserre hierarchy is applied to solve numerically these infinite-dimensional LP problems.

In the third part, we address the problem of computing the region of attraction (ROA) of a target set (e.g., a neighborhood of an equilibrium point) of a polynomial control system. We show that the ROA can be computed by solving an infinite-dimensional LP over occupation measures. In turn, this problem can be solved approximately with the Lasserre hierarchy. Our approach is genuinely primal in the sense that convexity of the problem of computing the ROA is an outcome of optimizing directly over system trajectories. The dual infinite-dimensional LP on nonnegative continuous functions (approximated by polynomial sum-of-squares) allows us to generate a hierarchy of semialgebraic outer approximations of the ROA at the price of solving a sequence of LMI problems with asymptotically vanishing conservatism.

In the final part, we develop further our LP approach for the optimal control of nonlinear switched systems where the control is the switching sequence. This is done by introducing modal occupation measures, which allow to relax the problem as a primal LP. Its dual LP of HJB inequalities is also characterized. The LPs are then solved numerically with the Lasserre hierarchy. Because of the special structure of switched systems, we obtain a much more efficient method than could be achieved by applying the standard Lasserre hierarchy for general optimal control problems.


Course material

To be determined


To be determinded