Polynomial SOS

In mathematics, a homogeneous form "h"("x") of degree 2"m" in the real "n"-dimensional vector "x" is a SOS (sum of squares) of homogeneous forms if and only if it can be written as a sum of squares of homogeneous forms of degree "m":

:$h(x)~mbox\{is\; SOS\}~iff~exists~mbox\{homogeneous\; forms\}~g\_1(x),ldots,g\_k(x):~h(x)=sum\_\{i=1\}^k\; g\_i(x)^2$

SOS of polynomials is a special case of SOS of homogeneous forms since any polynomial is a homogeneous form with an additional variable set to 1.

Square matricial representation

To establish whether a form "h"("x") is a SOS or not amounts to solving a convex optimization problem. Indeed, any "h"("x") can be written according to the square matricial representation (SMR) as

:$h(x)=x^\{\{m\}\text{'}\}left(H+L(alpha)\; ight)x^\{\{m$

where $x^\{\{m$ is a vector containing a base for the homogeneous 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

:$h(x)=x^\{left\{m\; ight\}\text{'}\}Hx^\{\{m$

and $L(alpha)$ is a linear parameterization of the linear space

:$mathcal\{L\}=left\{L=L\text{'}:~x^\{\{m\}\text{'}\}\; L\; x^\{\{m=0\; ight\}.$

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

:

whereas the dimension of the vector $alpha$ is given by

:$omega(n,2m)=frac\{1\}\{2\}sigma(n,m)left(1+sigma(n,m)\; ight)-sigma(n,2m).$

Then, "h"("x") is a SOS if and only if there exists a vector α such that

:$H\; +\; L(alpha)\; ge\; 0,$

meaning that the matrix $H\; +\; L(alpha)$ is positive-semidefinite. This is a linear matrix inequality (LMI) feasibility test and, hence, a convex optimization problem. The SMR and its use for testing SOS via LMI have been introduced in [1] . The SMR is also known as Gram matrix.

Examples

• Consider the homogeneous form of degree 4 in two variables, which is given by $h(x)=x\_1^4-x\_1^2x\_2^2+x\_2^4$. We have:Since there exists an α such that $H+L(alpha)ge\; 0$, namely $alpha=1$, it follows that "h"("x") is a SOS.
• $h(x)=2x\_1^4-2.5x\_1^3x\_2+x\_1^2x\_2x\_3-2x\_1x\_3^3+5x\_2^4+x\_3^4$:Since $H+L(alpha)ge\; 0$ for α = (1.18, −0.43, 0.73, 1.13, −0.37, 0.57)', it follows that "h"("x") is a SOS

Matrix SOS

A matrix homogeneous form "H"("x") (i.e., a matrix whose entries are homogeneous forms) of dimension "r" and degree "2m" in the real "n"-dimensional vector "x" is a SOS if and only if it can be written as sum of products of matrix homogeneous forms of degree "m" times their transpose:

:$H(x)~mbox\{is\; SOS\}~iff~exists~mbox\{matrix\; homogeneous\; forms\}~G\_1(x),ldots,G\_k(x):~H(x)=sum\_\{i=1\}^k\; G\_i(x)\text{'}G\_i(x)$

Matrix SMR

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

:$h(x)=left(x^\{\{motimes\; I\_r\; ight)\text{'}left(H+L(alpha)\; ight)left(x^\{\{motimes\; I\_r\; ight)$

where $otimes$ is the Kronecker product of matrices, "H" is any symmetric matrix satisfying

:$h(x)=left(x^\{\{motimes\; I\_r\; ight)\text{'}Hleft(x^\{\{motimes\; I\_r\; ight)$

and $L(alpha)$ is a linear parameterization of the linear space

:$mathcal\{L\}=left\{L=L\text{'}:~left(x^\{\{motimes\; I\_r\; ight)\text{'}Lleft(x^\{\{motimes\; I\_r\; ight)=0\; ight\}.$

The dimension of the vector $alpha$ is given by

:$omega(n,2m,r)=frac\{1\}\{2\}rleft(sigma(n,m)left(rsigma(n,m)+1\; ight)-(r+1)sigma(n,2m)\; ight).$

Then, "H"("x") is a SOS if and only if the following LMI holds:

:$exists\; alpha:~H+L(alpha)\; ge\; 0.$

Matrix SOS and matrix SMR have been introduced in [2] .

References

[1] G. Chesi, A. Tesi, A. Vicino, and R. Genesio, "On convexification of some minimum distance problems", 5th European Control Conference, Karlsruhe (Germany), 1999.

[2] G. Chesi, A. Garulli, A. Tesi, and A. Vicino, "Robust stability for polytopic systems via polynomially parameter-dependent Lyapunov functions", in 42nd IEEE Conference on Decision and Control, Maui (Hawaii), 2003.