Event
Control and Dynamical Systems Lecture Series: Amir Ali Ahmadi, "Convexity and Algorithmic Algebra"
Thursday, February 16, 2012
5:15 p.m.
1146 A.V. Williams Building
Pam White
301 405 6576
pwhite@umd.edu
The Interplay of Convexity and Algorithmic Algebra in Optimization and Systems Analysis
Amir Ali Ahmadi
Postdoctoral Researcher
Laboratory for Information and Decision Systems
Massachusetts Institute of Technology
Host
AndreTits
Abstract
Exciting recent developments at the interface of computational algebra and convex optimization have led to major algorithmic advances in a broad range of problems in optimization and systems theory. I will start this talk by giving an overview of these techniques and presenting applications in continuous and combinatorial optimization, statistics, and control theory. I will then focus on two recent results on computational and algebraic aspects of convexity in optimization: (i) I will show that deciding convexity of polynomials of degree as low as four is strongly NP-hard. This solves a problem that appeared as one of seven open problems in complexity theory for numerical optimization in 1992. (ii) I will introduce an algebraic, semidefinite programming (SDP) based sufficient condition for convexity known as sum-of-squares-convexity and present a complete characterization of the cases where it is equivalent to convexity. This characterization draws an interesting parallel to a seminal 1888 result of Hilbert in real algebraic geometry.
In the final part of the talk, I will move on to a problem with numerous applications in engineering and economics: understanding the asymptotic behavior of linear dynamical systems under uncertainty. I will tackle this problem with a novel class of SDP-based algorithms (with provable guarantees) that are based on new connections between ideas from control theory and the theory of finite automata.
Biography
Amir Ali Ahmadi received his Ph.D. in Electrical Engineering and Computer Science in September of 2011 from MIT, where he worked with Prof. Pablo Parrilo at the Laboratory for Information and Decision Systems (LIDS). Since then, he has been a Postdoctoral As- sociate at LIDS and at the MIT Computer Science and Artificial Intelligence Laboratory.
Amir Ali holds a master's degree in Electrical Engineering and Computer Science from MIT (2008) and two bachelor's degrees, in Electrical Engineering and in Mathematics, from the University of Maryland (2006). His current research interests are broadly in the development of mathematical tools and eficient computational techniques for optimization, verification, and design of complex systems in engineering and operations research. Amir Ali is a former recipient of the Washington Society of Engineers' Young Engineer Prize and a best student paper award finalist at the 47th IEEE Conference on Decision and Control.
