Computational Mathematics and Scientific Computing Seminar

---

The Interplay of Convexity and Algorithmic Algebra in Optimization and Systems Analysis

Speaker: Amir Ali Ahmadi, IBM Watson Research Center

Location: Warren Weaver Hall 1302

Date: March 8, 2013, 10 a.m.

Synopsis:

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.