An Introduction to Nonnegativity and Polynomial Optimization

Datum

04.12.2025

Zeit

15:00 - 16:00

Sprecher

Timo de Wolff

Zugehörigkeit

TU Braunschweig

Sprache

en

Hauptthema

Biologie

Host

Local Organisers: Nikola Sadovek, Maximilian Wiesmann, Giulio Zucal

Beschreibung

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.

Letztmalig verändert: 04.12.2025, 07:37:29