Weekly Bulletin

In science and engineering, we regularly face (constrained) polynomial optimization problems (CPOP). That is the task to minimize a real, multivariate polynomial under polynomial con-straints. Solving these problems is essentially equivalent to certifying nonnegativity of real polyno-mials – 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 nonneg-ative 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 polynomial optimization, nonnegativity, SOS, and SONC, and, if time permits, give an examples of applications of SONCs.