Seminar Details
2012-11-20 (14.00) : The Interplay of Convexity and Algorithmic Algebra in Optimization and Systems Analysis
At Euler building
Organized by Mathematical Engineering
Speaker :
Amirali AHMADI (MIT, USA)
Abstract :
We present complexity results and algebraic relaxations for two problems of interest in optimization and control theory: (i) recognizing convexity in polynomial optimization, and (ii) proving stability of polynomial differential equations.
(i) We 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. We then introduce an algebraic, semidefinite programming 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 seminal 1888 result of Hilbert in real algebraic geometry.
(ii) We show that deciding asymptotic stability of cubic polynomial vector fields is strongly NP-hard. Currently, one of the most widely used techniques for proving stability of polynomial vector.