Polynomial SOS

From Wikipedia, the free encyclopedia

In mathematics, a homogeneous form h(x) of degree 2m 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.

Contents

[edit] 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\}'}\left(H+L(\alpha)\right)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\right\}'}Hx^{\{m\}}

and L(α) is a linear parameterization of the linear space

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

The dimension of the vector x{m} is given by

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

whereas the dimension of the vector α is given by

\omega(n,2m)=\frac{1}{2}\sigma(n,m)\left(1+\sigma(n,m)\right)-\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(α) 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.

[edit] 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
    m=2,~x^{\{m\}}=\left(\begin{array}{c}x_1^2\\x_1x_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 an α such that H+L(\alpha)\ge 0, namely α = 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
    m=2,~x^{\{m\}}=\left(\begin{array}{c}x_1^2\\x_1x_2\\x_1x_3\\x_2^2\\x_2x_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 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

[edit] 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)'G_i(x)

[edit] 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^{\{m\}}\otimes I_r\right)'\left(H+L(\alpha)\right)\left(x^{\{m\}}\otimes I_r\right)

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

h(x)=\left(x^{\{m\}}\otimes I_r\right)'H\left(x^{\{m\}}\otimes I_r\right)

and L(α) is a linear parameterization of the linear space

\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 α is given by

\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, 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].

[edit] 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.