Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

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 and 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.