Friday, November 16, 2018 - 3:00pm to Saturday, November 17, 2018 - 3:55pm
Event Calendar Category
Other LIDS Events
Speaker Name
Amir Ali Ahmadi
Affiliation
Princeton ORFE
Building and Room Number
32-D677
Abstract
We propose and/or analyze semidefinite programming-based algorithms for two problems at the interface of optimization and dynamical systems:
In part (i), we study the power and limitations of sum of squares optimization and semialgebraic Lyapunov functions for proving asymptotic stability of polynomial dynamical systems. We give the first example of a globally asymptotically stable polynomial vector field with rational coefficients that does not admit a polynomial (or even analytic) Lyapunov function in any neighborhood of the origin. We show, however, that if the polynomial vector field is homogeneous, then its asymptotic stability is equivalent to existence of a rational Lyapunov function whose inequalities have sum of squares proofs. This statement generalizes the classical result in control on the equivalence between asymptotic stability of linear systems and existence of a quadratic Lyapunov function satisfying a certain linear matrix inequality.
In part (ii), we study a new class of optimization problems that have constraints imposed by trajectories of a dynamical system. As a concrete example, we consider the problem of minimizing a linear function over the set of points that remain in a given polyhedron under the repeated 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. We show that on problem instances where the spectral radius of the linear system is bounded above by some constant less than one, our hierarchies find an optimal solution and a certificate of optimality in polynomial time. Joint work with Bachir El Khadir (part (i)) and with Oktay Gunluk (part (ii)).
Biography
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 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 Award for Excellence in Undergraduate Teaching at Princeton University. Amir Ali is also the recipient of a number of best-paper awards, including the INFORMS Optimization Society's Young Researchers Prize, 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.