Speaker: Amir Ali Ahmadi, Postdoctoral Associate (Candidate for WID Optimization Faculty Position)

Lab for Information & Decision Systems (LIDS) and Computer Science & Artificial Intelligence Laboratory, Massachusetts Institute of Technology

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, semi-definite 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 seminal1888 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 sciences: 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.