An Introduction to Nonnegativity and Polynomial Optimization

Date

Dec 4, 2025

Time

3:00 PM - 4:00 PM

Speaker

Timo de Wolff

Affiliation

TU Braunschweig

Language

en

Main Topic

Biologie

Host

Local Organisers: Nikola Sadovek, Maximilian Wiesmann, Giulio Zucal

Description

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, give some examples of applications of nonnegativity certificatess.

Last modified: Dec 4, 2025, 7:37:29 AM