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.
日期
2026年09月16日 至 12月16日
位置
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| 周三 | 10:40 - 12:15 | Qiuzhen | - | - | - |
| 周三 | 13:30 - 15:05 | Qiuzhen | - | - | - |
修课要求
Algebra 2; Analysis 2; Numerical Analysis 2.
课程大纲
- 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.
参考资料
Jean-Bernard Lasserre: An Introduction to Polynomial and Semi-Algebraic Optimization
听众
Graduate
视频公开
公开
笔记公开
公开
语言
英文
讲师介绍
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.