Computer Science NASC Seminar
The Interplay of Convexity and Algorithmic Algebra in Optimization and Systems Analysis
Amir Ali Ahmadi, IBM Watson Research Center
March 08, 2013
Warren Weaver Hall, Room 1302
251 Mercer Street
New York, NY, 10012-1110
Spring 2013 NASC Seminars Calendar
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, semidefnite programming (SDP) based suffcient 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 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.