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.