Title: An Introduction to Nonnegativity and Polynomial Optimization
Abstract: In science and engineering, we regularly face (constrained) polynomial optimization problems (CPOP).
That is the task to minimize a real, multivariate polynomial under polynomial constraints.
Solving these problems is essentially equivalent to certifying nonnegativity of real polynomials -- a key problem in real algebraic geometry since the 19th century.
Since this is a notoriously hard to solve problem (e.g., various NP-complete problems admit a CPOP formulation), 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 sums 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. Circuit polynomials are a particular type of very sparse polynomial, which allow to decide nonnegativity easily. SONC certificates are interesting both from a theoretical and practical viewpoint, as they are independent of sums of squares and can be computed effectively via relative entropy programs.
In this talk, I will give an introduction to polynomial optimization, nonnegativity, and the role of sparsity within these problem ensembles. I will moreover introduce SOS and SONC, and, if time permits, give some examples of applications of SONCs.
(Host: Mathias Oster)