SOS-convexity

A multivariate polynomial is SOS-convex (or sum of squares convex) if its Hessian matrix H can be factored as H(x) = ST(x)S(x) where S is a matrix (possibly rectangular) which entries are polynomials in x.

[1] In other words, the Hessian matrix is a SOS matrix polynomial.

An equivalent definition is that the form defined as g(x,y) = yTH(x)y is a sum of squares of forms.

[2] If a polynomial is SOS-convex, then it is also convex.

[citation needed] Since establishing whether a polynomial is SOS-convex amounts to solving a semidefinite programming problem, SOS-convexity can be used as a proxy to establishing if a polynomial is convex.

In contrast, deciding if a generic quartic polynomial of degree four (or higher even degree) is convex is a NP-hard problem.

[3] The first counterexample of a polynomial which is convex but not SOS-convex was constructed by Amir Ali Ahmadi and Pablo Parrilo in 2009.

[4] The polynomial is a homogeneous polynomial that is sum-of-squares and given by:[4]

p ( x ) = 32

x

1

8

x

6

+ 40

x

x

+ 3

In the same year, Grigoriy Blekherman proved in a non-constructive manner that there exist convex forms that is not representable as sum of squares.

[5] An explicit example of a convex form (with degree 4 and 272 variables) that is not a sum of squares was claimed by James Saunderson in 2021.

[6] In 2013 Amir Ali Ahmadi and Pablo Parrilo showed that every convex homogeneous polynomial in n variables and degree 2d is SOS-convex if and only if either (a) n = 2 or (b) 2d = 2 or (c) n = 3 and 2d = 4.

[7] Impressively, the same relation is valid for non-negative homogeneous polynomial in n variables and degree 2d that can be represented as sum of squares polynomials (See Hilbert's seventeenth problem).