Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 208 - Algebraic Geometry Seminar

Mareike Dressler

UC San Diego

A New Approach to Nonnegativity and Polynomial Optimization

Abstract:

Deciding nonnegativity of real polynomials is a key question in real algebraic geometry with crucial importance in polynomial optimization. It is well-known that in general this problem is NP-hard, therefore one is interested in finding sufficient conditions (certificates) for nonnegativity, which are easier to check. Since the 19th century, sums of squares (SOS) are a standard certificate for nonnegativity, which can be detected by using 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 polynomials (SONC). SONC polynomials are certain sparse polynomials having a special structure in terms of their Newton polytopes and supports and serve as a nonnegativity certificate for real polynomials, which is independent of sums of squares. I will present some structural results of SONC polynomials and I will provide an overview about polynomial optimization via SONC polynomials.

Host: James McKernan

December 11, 2020

12:00 PM

Contact David Stapleton, dstapleton@ucsd.edu, for zoom access

****************************