What is polynomial optimization?

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.

Aim of this program

This program aims to bring together researchers from the Netherlands and beyond, with an interest on topics at the interface of (applied) mathematics, 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.

Overview of this program

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

Organization

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.

This workshop is dedicated to recent developments in semidefinite and polynomial optimization, and their applications in combinatorial and continuous optimization, discrete geometry and quantum information. The program will consist of invited lectures by experts in the field. It will also feature lectures by younger researchers and ample time will be left for free discussions.

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.

Polynomial equations are at the heart of many problems in pure and applied mathematics. They form a powerful tool for modelling nonlinear phenomena in the sciences. Application areas range from robotics, chemistry and computer vision to quantum physics and statistics. Recent progress has made it possible to reliably solve challenging polynomial equations arising in such practical contexts. This workshop will feature a friendly introduction to existing methods, presentations of the latest software tools and research talks by experts in the field. The focus will be on new trends and methodology, as well as applications in the sciences.

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.

This workshop is devoted to the application of polynomial optimization methods in the analysis and control of dynamical systems and energy networks. The polynomial optimization approach offers a powerful framework to model hard nonconvex, nonlinear control problems as infinite dimensional linear optimization problems over measure spaces. The rich interplay between functional analysis and operator theory, and real algebraic geometry, underlies the nowadays well-known moment/sum-of-squares hierarchy of relaxations, that allows to efficiently obtain converging sequences of bounds. This approach has also been recently developed to attack large optimal power flow problems in large electrical networks. The program (under construction) will feature lectures by experts in the field and ample time will be left for discussions.

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.