Convexity and SOS-Convexity

Abstract:

In his famous 1888 paper, Hilbert showed that there exist nonnegative polynomials that cannot be decomposed as a sum of squares (sos) of polynomials. He further gave a complete characterization of the values for (n,d) for which one can have a polynomial in n variables and of degree d that is nonnegative but not sos, although explicit examples of such polynomials appeared only eighty years later. Today, the subject has seen much renewed interest mainly due to the observation that the existence of an sos decomposition can be checked efficiently via semidefinite programming, whereas deciding nonnegativity is NP-hard.

After a brief review of these results, I will turn to the main focus of the talk which is on drawing the analogue of this story where instead of nonnegativity and sum of squares, we look at convexity and sos-convexity of polynomials. The notion of sos-convexity (termed by Helton and Nie) is a tractable sufficient condition for convexity of polynomials based on an appropriately defined sum of squares decomposition of the Hessian matrix. I will discuss three results on the subject: (i) I will show that two other natural sos relaxations for convexity based on the definition of convexity an its first order characterization turn out to be equivalent to sos-convexity. (ii) I will present an explicit example of a convex but not sos-convex polynomial in six variables and of degree four, whose construction comes directly from our recent proof of NP-hardness of deciding convexity of quartic polynomials. (iii) I will show that for polynomials in n variables and of degree d, the notions of convexity and sos-convexity are equivalent if and only if n=1 or d=2 or (n,d)=(2,4). Remarkably, these are exactly the cases where nonnegative polynomials are guaranteed to be sums of squares, as proven by Hilbert.

Biography:

Amir Ali Ahmadi is a PhD student at LIDS, MIT, where he works with Prof. Pablo Parrilo. He holds a Master's degree in EECS from MIT and two Bachelor's degrees in EE and in Math from the University of Maryland. He is the recipient of the Washington Society of Engineers' Young Engineer Prize and a best student paper finalist at the 47th IEEE Conference on Decision and Control.