Abstract
Minimizing a polynomial function over a region defined by polynomial inequalities
models broad classes of hard problems from combinatorics, geometry and optimization.
New algorithmic approaches have emerged recently for computing the global
minimum, by combining tools from real algebra (sums of squares of polynomials) and functional
analysis (moments of measures) with semidefinite optimization. Sums of squares
are used to certify positive polynomials, combining an old idea of Hilbert with the recent algorithmic insight that they can be checked efficiently with semidefinite optimization. The dual approach revisits the classical moment problem and leads to algorithmic methods for checking optimality of semidefinite relaxations and extracting global minimizers. We review some selected features of this general methodology, illustrate how it applies to
some combinatorial graph problems, and discuss links with other relaxation methods.
models broad classes of hard problems from combinatorics, geometry and optimization.
New algorithmic approaches have emerged recently for computing the global
minimum, by combining tools from real algebra (sums of squares of polynomials) and functional
analysis (moments of measures) with semidefinite optimization. Sums of squares
are used to certify positive polynomials, combining an old idea of Hilbert with the recent algorithmic insight that they can be checked efficiently with semidefinite optimization. The dual approach revisits the classical moment problem and leads to algorithmic methods for checking optimality of semidefinite relaxations and extracting global minimizers. We review some selected features of this general methodology, illustrate how it applies to
some combinatorial graph problems, and discuss links with other relaxation methods.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the International Congress of Mathematicians 2014 (ICM 2014) |
| Editors | Sun Young Jang, Young Rock Kim, Dae-Woong Lee, Ikkwon Yie |
| Place of Publication | Seoul |
| Publisher | Kyung Moon SA Co. Ltd. |
| Pages | 843-869 |
| ISBN (Print) | 9788961058070 |
| Publication status | Published - 2014 |
| Event | International Congress of Mathematicians 2014 - Seoul, Korea, Republic of Duration: 13 Aug 2014 → 21 Aug 2014 |
Conference
| Conference | International Congress of Mathematicians 2014 |
|---|---|
| Abbreviated title | ICM 2014 |
| Country/Territory | Korea, Republic of |
| City | Seoul |
| Period | 13/08/14 → 21/08/14 |