# Polynomial SOS

This article is about representing a non-negative polynomial as sum of squares of polynomials. For representing polynomial as a sum of squares of rational functions, see Hilbert's seventeenth problem. For the sum of squares of consecutive integers, see square pyramidal number. For representing an integer as a sum of squares of integers, see Lagrange's four-square theorem.

In mathematics, a form (i.e. a homogeneous polynomial) h(x) of degree 2m in the real n-dimensional vector x is sum of squares of forms (SOS) if and only if there exist forms ${\displaystyle g_{1}(x),\ldots ,g_{k}(x)}$ of degree m such that

${\displaystyle h(x)=\sum _{i=1}^{k}g_{i}(x)^{2}.}$

Every form that is SOS is also a positive polynomial, and although the converse is not always true, Hilbert proved that for n = 2, m = 1 or n = 3 and 2m = 4 a form is SOS if and only if is positive.[1] The same is also valid for the analog problem on positive symmetric forms.[2][3]

Although not every form can be represented as SOS, explicit sufficient conditions for a form to be SOS have been found.[4][5] Moreover, every real nonnegative form can be approximated as closely as desired (in the ${\displaystyle l_{1}}$-norm of its coefficient vector) by a sequence of forms ${\displaystyle \{f_{\epsilon }\}}$ that are SOS.[6]

## Square matricial representation (SMR)

To establish whether a form h(x) is SOS amounts to solving a convex optimization problem. Indeed, any h(x) can be written as

${\displaystyle h(x)=x^{\{m\}'}\left(H+L(\alpha )\right)x^{\{m\}}}$

where ${\displaystyle x^{\{m\}}}$ is a vector containing a base for the forms of degree m in x (such as all monomials of degree m in x), the prime ′ denotes the transpose, H is any symmetric matrix satisfying

${\displaystyle h(x)=x^{\left\{m\right\}'}Hx^{\{m\}}}$

and ${\displaystyle L(\alpha )}$ is a linear parameterization of the linear space

${\displaystyle {\mathcal {L}}=\left\{L=L':~x^{\{m\}'}Lx^{\{m\}}=0\right\}.}$

The dimension of the vector ${\displaystyle x^{\{m\}}}$ is given by

${\displaystyle \sigma (n,m)={\binom {n+m-1}{m}}}$

whereas the dimension of the vector ${\displaystyle \alpha }$ is given by

${\displaystyle \omega (n,2m)={\frac {1}{2}}\sigma (n,m)\left(1+\sigma (n,m)\right)-\sigma (n,2m).}$

Then, h(x) is SOS if and only if there exists a vector ${\displaystyle \alpha }$ such that

${\displaystyle H+L(\alpha )\geq 0,}$

meaning that the matrix ${\displaystyle H+L(\alpha )}$ is positive-semidefinite. This is a linear matrix inequality (LMI) feasibility test, which is a convex optimization problem. The expression ${\displaystyle h(x)=x^{\{m\}'}\left(H+L(\alpha )\right)x^{\{m\}}}$ was introduced in [7] with the name square matricial representation (SMR) in order to establish whether a form is SOS via an LMI. This representation is also known as Gram matrix.[8]

### Examples

• Consider the form of degree 4 in two variables ${\displaystyle h(x)=x_{1}^{4}-x_{1}^{2}x_{2}^{2}+x_{2}^{4}}$. We have
${\displaystyle m=2,~x^{\{m\}}=\left({\begin{array}{c}x_{1}^{2}\\x_{1}x_{2}\\x_{2}^{2}\end{array}}\right),~H+L(\alpha )=\left({\begin{array}{ccc}1&0&-\alpha _{1}\\0&-1+2\alpha _{1}&0\\-\alpha _{1}&0&1\end{array}}\right).}$
Since there exists α such that ${\displaystyle H+L(\alpha )\geq 0}$, namely ${\displaystyle \alpha =1}$, it follows that h(x) is SOS.
• Consider the form of degree 4 in three variables ${\displaystyle h(x)=2x_{1}^{4}-2.5x_{1}^{3}x_{2}+x_{1}^{2}x_{2}x_{3}-2x_{1}x_{3}^{3}+5x_{2}^{4}+x_{3}^{4}}$. We have
${\displaystyle m=2,~x^{\{m\}}=\left({\begin{array}{c}x_{1}^{2}\\x_{1}x_{2}\\x_{1}x_{3}\\x_{2}^{2}\\x_{2}x_{3}\\x_{3}^{2}\end{array}}\right),~H+L(\alpha )=\left({\begin{array}{cccccc}2&-1.25&0&-\alpha _{1}&-\alpha _{2}&-\alpha _{3}\\-1.25&2\alpha _{1}&0.5+\alpha _{2}&0&-\alpha _{4}&-\alpha _{5}\\0&0.5+\alpha _{2}&2\alpha _{3}&\alpha _{4}&\alpha _{5}&-1\\-\alpha _{1}&0&\alpha _{4}&5&0&-\alpha _{6}\\-\alpha _{2}&-\alpha _{4}&\alpha _{5}&0&2\alpha _{6}&0\\-\alpha _{3}&-\alpha _{5}&-1&-\alpha _{6}&0&1\end{array}}\right).}$
Since ${\displaystyle H+L(\alpha )\geq 0}$ for ${\displaystyle \alpha =(1.18,-0.43,0.73,1.13,-0.37,0.57)}$, it follows that h(x) is SOS.

## Generalizations

### Matrix SOS

A matrix form F(x) (i.e., a matrix whose entries are forms) of dimension r and degree 2m in the real n-dimensional vector x is SOS if and only if there exist matrix forms ${\displaystyle G_{1}(x),\ldots ,G_{k}(x)}$ of degree m such that

${\displaystyle F(x)=\sum _{i=1}^{k}G_{i}(x)'G_{i}(x).}$

#### Matrix SMR

To establish whether a matrix form F(x) is SOS amounts to solving a convex optimization problem. Indeed, similarly to the scalar case any F(x) can be written according to the SMR as

${\displaystyle F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'\left(H+L(\alpha )\right)\left(x^{\{m\}}\otimes I_{r}\right)}$

where ${\displaystyle \otimes }$ is the Kronecker product of matrices, H is any symmetric matrix satisfying

${\displaystyle F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'H\left(x^{\{m\}}\otimes I_{r}\right)}$

and ${\displaystyle L(\alpha )}$ is a linear parameterization of the linear space

${\displaystyle {\mathcal {L}}=\left\{L=L':~\left(x^{\{m\}}\otimes I_{r}\right)'L\left(x^{\{m\}}\otimes I_{r}\right)=0\right\}.}$

The dimension of the vector ${\displaystyle \alpha }$ is given by

${\displaystyle \omega (n,2m,r)={\frac {1}{2}}r\left(\sigma (n,m)\left(r\sigma (n,m)+1\right)-(r+1)\sigma (n,2m)\right).}$

Then, F(x) is SOS if and only if there exists a vector ${\displaystyle \alpha }$ such that the following LMI holds:

${\displaystyle H+L(\alpha )\geq 0.}$

The expression ${\displaystyle F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'\left(H+L(\alpha )\right)\left(x^{\{m\}}\otimes I_{r}\right)}$ was introduced in [9] in order to establish whether a matrix form is SOS via an LMI.

### Noncommutative polynomial SOS

Consider the free algebra RX⟩ generated by the n noncommuting letters X = (X1,...,Xn) and equipped with the involution T, such that T fixes R and X1,...,Xn and reverse words formed by X1,...,Xn. By analogy with the commutative case, the noncommutative symmetric polynomials f are the noncommutative polynomials of the form f=fT. When any real matrix of any dimension r x r is evaluated at a symmetric noncommutative polynomial f results in a positive semi-definite matrix, f is said to be matrix-positive.

A noncommutative polynomial is SOS if there exists noncommutative polynomials ${\displaystyle h_{1},\ldots ,h_{k}}$ such that

${\displaystyle f(X)=\sum _{i=1}^{k}h_{i}(X)^{T}h_{i}(X).}$

Surprisingly, in the noncommutative scenario a noncommutative polynomial is SoS if and only if is matrix-positive.[10] Moreover, there exist algorithms available to decompose matrix-positive polynomials in sum of squares of noncommutative polynomials.[11]

## References

1. ^ Hilbert, David (September 1888). "Ueber die Darstellung definiter Formen als Summe von Formenquadraten". Mathematische Annalen. 32 (3): 342–350. doi:10.1007/bf01443605.
2. ^ Choi, M. D.; Lam, T. Y. (1977). "An old question of Hilbert". Queen's papers in pure and applied mathematics. 46: 385–405.
3. ^ Goel, Charu; Kuhlmann, Salma; Reznick, Bruce (May 2016). "On the Choi–Lam analogue of Hilbert's 1888 theorem for symmetric forms". Linear Algebra and its Applications. 496: 114–120. doi:10.1016/j.laa.2016.01.024.
4. ^ Lasserre, Jean B. "Sufficient conditions for a real polynomial to be a sum of squares". Archiv der Mathematik. 89 (5): 390–398. doi:10.1007/s00013-007-2251-y.
5. ^ Powers, Victoria; Wörmann, Thorsten (1998). "An algorithm for sums of squares of real polynomials" (PDF). Journal of Pure and Applied Algebra. 127 (1): 99–104. doi:10.1016/S0022-4049(97)83827-3.
6. ^ Lasserre, Jean B. (2007). "A Sum of Squares Approximation of Nonnegative Polynomials". SIAM Review. 49 (4): 651–669. doi:10.1137/070693709.
7. ^ Chesi, G.; Tesi, A.; Vicino, A.; Genesio, R. (1999). "On convexification of some minimum distance problems". Proceedings of the 5th European Control Conference. Karlsruhe, Germany: IEEE. pp. 1446–1451.
8. ^ Choi, M.; Lam, T.; Reznick, B. (1995). "Sums of squares of real polynomials". Proceedings of Symposia in Pure Mathematics. pp. 103–125.
9. ^ Chesi, G.; Garulli, A.; Tesi, A.; Vicino, A. (2003). "Robust stability for polytopic systems via polynomially parameter-dependent Lyapunov functions". Proceedings of the 42nd IEEE Conference on Decision and Control. Maui, Hawaii: IEEE. pp. 4670–4675.
10. ^ Helton, J. William (September 2002). ""Positive" Noncommutative Polynomials Are Sums of Squares". The Annals of Mathematics. 156 (2): 675–694. doi:10.2307/3597203.
11. ^ Burgdorf, Sabine; Cafuta, Kristijan; Klep, Igor; Povh, Janez (25 October 2012). "Algorithmic aspects of sums of Hermitian squares of noncommutative polynomials". Computational Optimization and Applications. 55 (1): 137–153. doi:10.1007/s10589-012-9513-8.