Amir Ali Ahmadi, Princeton University

Abstract

The problem of recognizing nonnegativity of a multivariate polynomial has a celebrated history, tracing back to Hilbert’s 17th problem. In recent years, there has been much renewed interest in the topic because of a multitude of applications in applied and computational mathematics and the observation that one can optimize over an interesting subset of nonnegative polynomials using “sum of squares optimization”. In this talk, we first present two applications of nonnegative polynomials to problems that pop up in statistics and machine learning (shape-constrained regression and difference of convex programming). We then give an overview of our recent efforts to provide alternatives to sum of squares optimization that do not rely on semidefinite programming, but instead use linear programming, or second-order cone programming, or are altogether free of optimization. In particular, we present the first Positivstellensatz that certifies infeasibility of a set of polynomial inequalities simply by multiplying certain fixed polynomials together and checking nonnegativity of the coefficients of the resulting product. We also demonstrate the impact of our LP/SOCP-based algorithms on large-scale verification problems in control and robotics.

Joint work in part with Anirduha Majumdar (Princeton) and with Georgina Hall (Princeton → INSEAD).