Amir Ali Ahmadi
Laboratory for Information and Decision Systems
Massachusetts Institute of Technology
The Interplay of Convexity and Algorithmic Algebra in Optimization and Systems Analysis
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 charactization 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.