Welcome to the World of SONCs
- Mareike Dressler (MPI MiS, Leipzig)
Abstract
In science and engineering we regularly face hard, nonlinear polynomial optimization problems. Solving these problems is essentially equivalent to certifying nonnegativity of real, multivariate polynomials – a fundamental problem in real algebraic geometry since the 19th century. It is well-known that in general, this problem is very hard; therefore, one is interested in finding sufficient conditions (certificates) for nonnegativity, which are easier to check. A standard nonnegativity certificate is given by sums of squares (SOS), which can be detected by semidefinite programming (SDP). This SOS/SDP approach, however, has some issues, especially in practice if the problem has many variables or high degree.
In this talk, I will introduce sums of nonnegative circuit (SONC) polynomials - a new class of nonnegativity certificates for real, multivariate polynomials. These certificates are independent of sums of squares. I will present some structural results of SONC polynomials and I will provide an overview of polynomial optimization via SONC polynomials.