Sums of Nonnegative Circuit Polynomials and Combinatorics in Polynomial Optimization
- Prof. Dr. Thorsten Theobald (Goethe-Universität Frankfurt)
- Prof. Dr. Timo de Wolff (TU Braunschweig)
The task of a polynomial optimization problem is to minimize a multivariate real polynomial under a finite number of polynomial inequality constraints. This problem is closely related to the nonnegativity of real polynomials, a classical key problem in real algebraic geometry.
Nonnegative polynomials over a given finite support set form a convex cone in the space of real polynomials. As deciding nonnegativity is hard both in theory and practice, one often approaches polynomial optimization problems via more tractable convex subcones of the nonnegativity cone.
For the class of circuit polynomials, the support sets are circuits of the affine matroid defined by the ground support and the nonnegativity can be expressed in terms of the inequality of arithmetic and geometric means. The convex cone of all finite Sums Of Nonnegative Circuit polynomials with a given support set is called the SONC cone.
Polynomials in the SONC cone admit a nonnegativity certificate and the question whether a given polynomial is contained in the SONC cone can be decided in terms of a convex optimization problem, specifically, a relative entropy program, which is a generalization of geometric programs. In non-linear optimization, the SONC cone can be used to determine lower bounds of polynomials and this basic approach can be turned into more refined as well as hierarchical optimization schemes using representation theorems. Moreover, many of the techniques extend to exponential sums also known as signomials.
In the subproject, Exactness of unconditional and conditional SONC polynomials, conditions on the ground support set are derived such that the SONC cone coincides with the nonnegativity cone. The subproject The algebraic boundary of the conditional SONC cone develops combinatorial and algebraic techniques to extend boundary characterizations for the unconditional SONC cone to the conditional case. In the subproject Generalized circuit principles, generalizations and enhancements of the fundamental concept of circuit polynomials are developed. Moreover, applications in sparse polynomial optimization are considered in the subproject Parametric sums of nonnegative circuit polynomials and applications on real-world data.
