SOS-convexity explained

A multivariate polynomial is SOS-convex (or sum of squares convex) if its Hessian matrix H can be factored as H(x) = S^T(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) = y^TH(x)y is a sum of squares of forms.^[2]

Connection with convexity

If a polynomial is SOS-convex, then it is also convex. 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 polynomial of degree large than four 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:

$$p(x)=\; 32\; x\_^+118\; x\_^\; x\_^+40\; x\_^\; x\_^+25\; x\_^\; x\_^\; -43\; x\_^\; x\_^\; x\_^-35\; x\_^\; x\_^+3\; x\_^\; x\_^\; x\_^\; -16\; x\_^\; x\_^\; x\_^+24\; x\_^\; x\_^+16\; x\_^\; +44\; x\_^\; x\_^+70\; x\_^\; x\_^+60\; x\_^\; x\_^+30\; x\_^$$

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]

Connection with non-negativity and sum-of-squares

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

See also

• Hilbert's seventeenth problem
• Polynomial SOS
• Sum-of-squares optimization

Notes and References

1. Helton. J. William. Nie. Jiawang. 2010. Semidefinite representation of convex sets. Mathematical Programming. en. 122. 1. 21–64. 10.1007/s10107-008-0240-y. 0025-5610. 0705.4068. 1352703.
2. Book: Ahmadi. Amir Ali. Parrilo. Pablo A.. 49th IEEE Conference on Decision and Control (CDC) . On the equivalence of algebraic conditions for convexity and quasiconvexity of polynomials . 2010. 3343–3348. 10.1109/CDC.2010.5717510. 1721.1/74151. 978-1-4244-7745-6. 11904851. free.
3. Ahmadi. Amir Ali. Olshevsky. Alex. Parrilo. Pablo A.. Tsitsiklis. John N.. 2013. NP-hardness of deciding convexity of quartic polynomials and related problems. Mathematical Programming. en. 137. 1–2. 453–476. 10.1007/s10107-011-0499-2. 0025-5610. 1012.1908. 2319461.
4. Book: Ahmadi. Amir Ali. Parrilo. Pablo A.. Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference . A positive definite polynomial Hessian that does not factor . 2009. 1195–1200. 10.1109/CDC.2009.5400519. 1721.1/58871. 978-1-4244-3871-6. 5344338. free.
5. Blekherman. Grigoriy. 2009-10-04. Convex Forms that are not Sums of Squares. math.AG. 0910.0656.
6. Saunderson. James. A Convex Form That is Not a Sum of Squares. . 2022 . 48 . 569–582 . 10.1287/moor.2022.1273 . 2105.08432. 234763204 .
7. Ahmadi. Amir Ali. Parrilo. Pablo A.. 2013. A Complete Characterization of the Gap between Convexity and SOS-Convexity. SIAM Journal on Optimization. en. 23. 2. 811–833. 10.1137/110856010. 1052-6234. 1111.4587. 16801871.