PACM Colloquium: Polynomial Optimization and Dynamical Systems

Amir Ali Ahmadi, Princeton University
Sep 25 2017 - 4:00pm
Event type: 
PACM Colloquium
214 Fine Hall

In recent years, there has been a surge of exciting research activity at the interface of optimization (in particular polynomial, semidefinite, and sum of squares optimization) and the theory of dynamical systems. In this talk, we focus on two of our current research directions that are at this interface. 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 new 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 introduce a new class of optimization problems whose constraints are imposed by trajectories of a dynamical system. As a concrete example, we consider the problem of optimizing a linear function over the set of initial conditions that forever remain inside a given polyhedron under the action of a linear, or a switched linear, dynamical system. We present a hierarchy of linear and semidefinite programs that respectively lower and upper bound the optimal value of such problems to arbitrary accuracy. 

Amir Ali Ahmadi ( ) 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.