PACM Colloquium: Tractable approximations to nonnegative polynomials with applications to the joint spectral radius

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 (SOS) optimization”. In this talk, we give a brief overview of the developments in this field and then focus on two recent results. In part (i), we show that the joint spectral radius of a finite set of matrices is less than one if and only if there exists a polynomial norm (i.e., a norm which is the d-th root of a degree-d homogeneous polynomial) that decreases under the application of all matrices. Moreover, the convexity of this polynomial and its decrease inequalities can all be verified using SOS certificates. This result generalizes the classical theorem in linear algebra that the spectral radius of a matrix is less than one if and only if there exists a decreasing quadratic norm. In part (ii), we introduce new algebraic sufficient conditions for polynomial nonnegativity that are very similar to the SOS condition but instead of semidefinite programs lead to linear or second order cone programs when implemented numerically. These are what we call ``DSOS and SDSOS programs.’’ We show that these relaxations are orders of magnitude more scalable than the SOS relaxation while enjoying many of the same asymptotic theoretical guarantees.

Joint work (in different subsets) with Etienne de Klerk, Georgina Hall, Raphael Jungers, and Anirudha Majumdar.

Amir Ali Ahmadi ( http://aaa.princeton.edu/ ) is an Assistant Professor at the Department of Operations Research and Financial Engineering at Princeton University and an Associated Faculty member of the Department of Computer Science. Amir Ali received his PhD in EECS from MIT and was a Goldstine Fellow at the IBM Watson Research Center prior to joining Princeton. His research interests are in optimization theory, computational aspects of dynamics and control, and algorithms and complexity. Amir Ali's distinctions include the Sloan Fellowship in Computer Science, the NSF CAREER Award, the AFOSR Young Investigator Award, the DARPA Faculty Award, the Google Faculty Award, the Goldstine Fellowship of IBM Research, and the Oberwolfach Fellowship of the NSF. His undergraduate course at Princeton (ORF 363, ``Computing and Optimization’’) has received the 2017 Excellence in Teaching of Operations Research Award of the Institute for Industrial and Systems Engineers. Amir Ali is also the recipient of a number of best-paper awards, including the INFORMS Computing Society Prize (for best series of papers at the interface of operations research and computer science), the Best Conference Paper Award of the IEEE International Conference on Robotics and Automation, and the prize for one of two most outstanding papers published in the SIAM Journal on Control and Optimization in 2013-2015.