CORE Series

Amir Ali Ahmadi, *ORFE, Princeton University*

**Friday, May 17, 2019**

**ECE 037, 2:30-3:30pm**

*Title:

Nonnegative polynomials: from optimization to control and learning

*Speaker:

Amir Ali Ahmadi

Princeton, ORFE

*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 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)).

*Bio:

Amir Ali Ahmadi ( http://aaa.princeton.edu/ ) 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