Printable PDF
Department of Mathematics,
University of California San Diego

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

Math 278C - Optimization and Data Science Seminar

Mareike Dressler

UCSD

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 recognized using semidefinite programming (SDP). This approach, however, has some issues, especially in practice if the optimization 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. Moreover, I will provide an overview about polynomial optimization via SONC polynomials. Similar as SOS correspond to SDP, the new SONC certificates correspond to geometric programming and relative entropy programming. Based on a Positivstellensatz for SONC polynomials we establish a converging hierarchy of efficiently computable lower bounds for constrained optimization problems. The talk is based on joint work with Sadik Iliman, Adam Kurpisz, and Timo de Wolff.

Host: Jiawang Nie

January 23, 2019

2:00 PM

AP&M 7321

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