Polynomial Optimization
The polynomial optimization problem is nonconvex, infinite-dimensional, and NP-hard with a variety of applications in economics, quantum physics, and urban development. This course introduces the algebraic, geometric, and computational framework, focusing on the connections between nonnegative polynomials, sums of squares, moments, and semidefinite programming via the moment-SOS hierarchy. We develop the theory of positivity certificates, quadratic modules, and Positivstellensatz results, and use them to construct semidefinite bounds. Additionally, the course touches on the generalized moment problem, duality theory, extraction of minimizers, and Christoffel-Darboux kernels.
Lecturer
Date
16th September ~ 16th December, 2026
Location
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| Wednesday | 10:40 - 12:15 | Qiuzhen | - | - | - |
| Wednesday | 13:30 - 15:05 | Qiuzhen | - | - | - |
Prerequisite
Algebra 2; Analysis 2; Numerical Analysis 2.
Syllabus
- Introduction to Polynomial Optimization: Global optimization of polynomial functions in one and several commutative variables; optimization with algebraic and semi-algebraic constraints; examples and applications.
- Nonnegative Polynomials and Sums of Squares (SOS): The cone of nonnegative polynomials; Hilbert 17; basic closed semi-algebraic sets; predorderings and quadratric modules; the Archimedean property; Positivstellensatz results.
- The Moment Problem: Representing measures; linear functionals and moment sequences; duality between positive polynomials and moments; weak and strong duality.
- Moment Relaxation and SOS Reinforcement: Gram matrix representations; pseudomoments; truncation and localization; semidefinite programming formulations; the moment-SOS hierarchy.
- Optimality Certificates: Optimality conditions; finite convergence; flat extension; extraction of minimizers.
- Structured Polynomial Optimization: Nonstandard and orthogonal polynomial bases; symmetry reduction; sparsity explitation.
- Extensions: Theory vs practice; the Christoffel–Darboux kernel; spectrahedral shadows; optimization over varieties; applications in extremal combinatorics and dynamical systems.
- Nonnegative Polynomials and Sums of Squares (SOS): The cone of nonnegative polynomials; Hilbert 17; basic closed semi-algebraic sets; predorderings and quadratric modules; the Archimedean property; Positivstellensatz results.
- The Moment Problem: Representing measures; linear functionals and moment sequences; duality between positive polynomials and moments; weak and strong duality.
- Moment Relaxation and SOS Reinforcement: Gram matrix representations; pseudomoments; truncation and localization; semidefinite programming formulations; the moment-SOS hierarchy.
- Optimality Certificates: Optimality conditions; finite convergence; flat extension; extraction of minimizers.
- Structured Polynomial Optimization: Nonstandard and orthogonal polynomial bases; symmetry reduction; sparsity explitation.
- Extensions: Theory vs practice; the Christoffel–Darboux kernel; spectrahedral shadows; optimization over varieties; applications in extremal combinatorics and dynamical systems.
Reference
Jean-Bernard Lasserre: An Introduction to Polynomial and Semi-Algebraic Optimization
Audience
Graduate
Video Public
Yes
Notes Public
Yes
Language
English
Lecturer Intro
Tobias Metzlaff works at the intersection of algebra, optimization and combinatorics, specializing in the exploitation of symmetry in computations. Prior to joining BIMSA, he held postdoctoral positions at University of Kaiserslautern-Landau with Ulrich Thiel and LAAS-CNRS with Victor Magron. As a Marie Sklodowska-Curie fellow, he conducted his doctorate at Inria d'Universite Cote d'Azur with Evelyne Hubert and served as representative for the POEMA early stage researchers. Tobias Metzlaff studied Mathematics at RWTH Aachen University.