Amir Ali Ahmadi; Nonnegative polynomials: from optimization to control and learning

CORE Series
Amir Ali Ahmadi, ORFE, Princeton University
Friday, May 17, 2019
ECE 037, 2:30-3:30pm

Poster PDF

Nonnegative polynomials: from optimization to control and learning

Amir Ali Ahmadi
Princeton, ORFE

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

In this talk, we give a brief overview of some of our recent
contributions to this area. In part (i), we propose more scalable
alternatives to sum of squares optimization and show how they impact
verification problems in control and robotics. Our algorithms 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.

In part (ii), we study the problem of learning dynamical systems from
very limited data but in presence of “side information”, such as
physical laws or contextual knowledge. This is motivated by
safety-critical applications where an unknown dynamical system needs
to be controlled after a very short learning phase where a few of its
trajectories are observed. (Imagine, e.g., the task of autonomously
landing a passenger airplane that has gone through sudden wing
damage.) We show that sum of squares and semidefinite optimization are
particularly suited for exploiting side information in order to assist
the task of learning when data is limited. Joint work with A. Majumdar
and G. Hall (part (i)) and with B. El Khadir (part (ii)).

Amir Ali Ahmadi ( ) is a Professor at the
Department of Operations Research and Financial Engineering at
Princeton University and an Associated Faculty member of the Program
in Applied and Computational Mathematics, the Department of Computer
Science, the Department of Mechanical and Aerospace Engineering, and
the Center for Statistics and Machine Learning. 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, a MURI award from the AFOSR, the
NSF CAREER Award, the AFOSR Young Investigator Award, the DARPA
Faculty Award, the Google Faculty Award, the Howard B. Wentz Junior
Faculty Award as well as the Innovation Award of Princeton University,
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 and the 2017 Phi Beta Kappa