multivariate polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...

is SOS-convex (or sum of squares convex) if its

Hessian matrix In mathematics, the Hessian matrix or Hessian is a square matrix of second-order partial derivatives of a scalar-valued function, or scalar field. It describes the local curvature of a function of many variables. The Hessian matrix was developed ...

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

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 Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize) over the intersection of the cone of positiv ...

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. The first counterexample of a polynomial which is convex but not SOS-convex was constructed by

Amir Ali Ahmadi Amir Ali Ahmadi is a professor in the Department of Operations Research and Financial Engineering at Princeton University. He is primarily known for his work on mathematical optimization. Biography Ahmadi obtained a B.S. in both mathematics and e ...

and

Pablo Parrilo Pablo A. Parrilo from MIT (Massachusetts Institute of Technology) was named Fellow of the Institute of Electrical and Electronics Engineers (IEEE) in 2016 for contributions to semidefinite and sum-of-squares optimization. He was named a SIAM Fellow ...

in 2009. 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 In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object. This is in contrast to a non-constructive proof (also known as an existen ...

manner that there exist convex forms that is not representable as sum of squares. 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.

Connection with non-negativity and sum-of-squares

In 2013

and

showed that every convex homogeneous polynomial in ''n'' variables and degree 2''d'' is SOS-convex if and only if either (a) ''n'' = 2 or (b) 2''d'' = 2 or (c) ''n'' = 3 and 2''d'' = 4. Impressively, the same relation is valid for non-negative homogeneous polynomial in ''n'' variables and degree 2''d'' that can be represented as sum of squares polynomials (See

Hilbert's seventeenth problem Hilbert's seventeenth problem is one of the 23 Hilbert problems set out in a celebrated list compiled in 1900 by David Hilbert. It concerns the expression of positive definite rational functions as sums of quotients of squares. The original ques ...

References

{{Reflist

Connection with convexity

Connection with non-negativity and sum-of-squares

References

See also