Research Program on
Polynomial Optimization and Applications
Polynomial optimization is an exciting new field, which emerged in the last two decades. Building up on cross fertilization between mathematics, theoretical computer science and engineering, it has seen recently a spectacular development, with a growing number of potential application areas and a growing community of researchers, largely due to its wide applicability and versatility. The aim of this research program is to highlight some of these recent developments.
Polynomial optimization deals with optimization problems involving polynomial objective and constraints. These are computationally hard problems, in general nonlinear and nonconvex, ubiquitous in diverse fields and application areas such as discrete optimization, operations research, discrete geometry, theoretical computer science, control theory, and quantum information. Polynomial optimization offers a versatile modeling framework, able to capture decision variables that can be scalar integer- or continuous-valued (useful for applications in discrete and continuous optimization), as well as matrix- or operator-valued (useful for applications in quantum information), or measure-valued (useful for applications in control).
The key idea is to exploit algebraic and geometric properties of polynomials and develop dedicated solution methods for polynomial optimization problems. These methods are based, on the one hand, on real algebraic results about positive polynomials, and, on the other hand, on functional analytic results about moments of positive measures. They are rooted in early work by Hilbert (about sums of squares) and by Stieltjes, Hausdorff and Hamburger (about the moment problem) at the turn of the 20th century. Of particular relevance is Hilbert 17-th problem, in his famous list of 23 mathematical problems posed in 1900, which asks whether every nonnegative polynomial can be written as a sum of squares of rational functions, answered affimatively by Artin in 1927.
These techniques permit to design hierarchies of convex relaxations, known as sums of squares hierarchies and Lasserre moment hierarchies, that deliver efficient approximations converging asymptotically to the optimum solution of the original optimization problem. The computational paradigm underlying these relaxations is semidefinite optimization, a far reaching generalization of linear optimization, which boils down to linear optimization over the cone of positive semidefinite matrices and admits efficient algorithms. Semidefinite optimization indeed permits to model sums of squares of polynomials (used as a proxy to certify polynomial positivity) as well as positivity conditions for moments of measures. These key principles have led in the recent years to novel algorithmic methods permitting to attack a large spectrum of hard problems within various application areas, as will be covered by the events in this research program.
This program aims to bring together reseachers from the Netherlands and beyond, with an interest on topics at the interface of (applied) mathemaics, optimization and theoretical computer science. We invite all researchers, especially PhD students and postdoctoral researchers who are working in related topics, to join the events.
The program is devoted to recent advancements in polynomial optimization and applications. It will start with a one-week workshop, followed by two shorter events, featuring invited lectures by (inter)national experts in the field:
Workshop on Semidefinite and Polynomial Optimization, 29 August - 2 September, 2022
Workshop on Solving Polynomial Equations and Applications, 5-7 October, 2022
Workshop on Polynomial Optimization and Applications in Control and Energy, 17-18 November, 2022
The research program is organized by the CWI Networks and Optimization research group (Monique Laurent, Simon Telen), in collaboration with Jop Briët (Algorithms and Complexity) and Bert Zwart (Stochastics). If you have any questions please contact us.
This program also fits within the scope of the European
POEMA (Polynomial Optimization, Efficiency through Moments and Algebra) project, supported by the Marie Sklodowska-Curie Actions - Innovative Training
Networks (ITN) funding scheme.
Workshop on Semidefinite and Polynomial Optimization
29 August - 2 September, 2022
This workshop is co-orgnized by Jop Briët and Monique Laurent.
Here you can find more information on the program of CWI's Semidefinite and Polynomial Optimization Workshop.
Workshop on Solving Polynomial Equations and Applications
5-7 October, 2022
This workshop is co-organized by Monique Laurent and Simon Telen.
Here you can find more information on the
program of CWI's Solving Polynomial Equations and Applications workshop.
Workshop on Polynomial Optimization and Applications in Control and Energy
17-18 November, 2022
This workshop is co-organized by Monique Laurent and Bert Zwart.
Here you can find more information on the program of CWI's Polynomial Optimization and Applications in Control and Energy workshop.