Quick links

Structured Sum of Squares Polynomials in Optimization and Control

Date and Time
Thursday, November 12, 2015 - 4:30pm to 5:30pm
Computer Science Small Auditorium (Room 105)
CS Department Colloquium Series

Amirali Ahmadi
In recent years, algebraic techniques in optimization such as sum of squares (SOS) programming have led to powerful semidefinite programming relaxations for a wide range of NP-hard problems in computational mathematics. We begin by giving an overview of these techniques, emphasizing their implications for optimization and Lyapunov analysis of dynamical systems, and pointing out some challenges that remain in terms of scalability. We then introduce new algebraic relaxation schemes that are very similar to SOS relaxations in nature but instead of semidefinite programs result in linear or second order cone programs. These are what we call ``DSOS and SDSOS programs.'' We show that these relaxations are orders of magnitude more scalable than SOS relaxations while enjoying many of the same asymptotic theoretical guarantees. (Joint work with Anirudha Majumdar.)

Time permitting, we will also present our recently-introduced area of ``robust-to-dynamics optimization'', which has to do with optimizing over invariant sets of dynamical systems. (Joint work with Oktay Gunluk.)

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 and in computational aspects of dynamics and control. Amir Ali's recent awards include the INFORMS Computing Society Prize (for best series of papers at the interface of operations research and computer science), the AFOSR Young Investigator Program Award, the Goldstine Fellowship of IBM Research, 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 Optimization and Control in 2013-2015. Amir Ali is also a three-time recipient of the NSF Oberwolfach Fellowship and a best student paper award finalist at the 47th IEEE Conference on Decision and Control.

Follow us: Facebook Twitter Linkedin