Tutte Colloquium - Timo de Wolff

Title: An Introduction to Nonnegativity and Polynomial Optimization

Abstract:

In science and engineering, we regularly face polynomial optimization problems, that is: minimize a real, multivariate polynomial under polynomial constraints. Solving these problems is essentially equivalent to certifying of nonnegativity of real polynomials -- a key problem in real algebraic geometry since the 19th century. Since this is a notoriously hard to solve problem, one is interested in certificates that imply nonnegativity and are easier to check than nonnegativity itself. In particular, a polynomial is nonnegative if it is a sum of squares (SOS) of other polynomials. Being an SOS can be detected effectively via semidefinite programming (SDP) in practice.

In 2014, Iliman and I introduced a new certificate of nonnegativity based on sums of nonnegative circuit polynomials (SONC), which I have developed further since then both in theory and practice joint with different coauthors. In particular, these certificates are independent of sums of squares and can be computed via relative entropy programs. In this talk, I will give an introduction to the world of polynomial optimization, nonnegativity, SOS, and SONC.