Polynomial SOS

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

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

where $x^\{\backslash \{m\backslash \}\}$ 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

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

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

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

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

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

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

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

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

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

meaning that the matrix $H\; +\; L(\backslash alpha)$ is positive-semidefinite. This is a linear matrix inequality (LMI) feasibility test, which is a convex optimization problem. The expression $h(x)=x^\{\backslash \{m\backslash \}\text{'}\}\backslash left(H+L(\backslash alpha)\backslash right)x^\{\backslash \{m\backslash \}\}$ was introduced in {{cite conference |url=https://ieeexplore.ieee.org/document/7099515 |title=On convexification of some minimum distance problems |last1=Chesi |first1=G. |last2=Tesi |first2=A. |last3=Vicino |first3=A. |last4=Genesio |first4=R. |date=1999 |publisher=IEEE |book-title=Proceedings of the 5th European Control Conference |pages=1446–1451 |location=Karlsruhe, Germany}} 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.{{cite conference |title=Sums of squares of real polynomials |last1=Choi |first1=M. |last2=Lam |first2=T. |last3=Reznick |first3=B. |date=1995 |book-title=Proceedings of Symposia in Pure Mathematics |pages=103–125 |url=https://www.researchgate.net/publication/240268385}}

• Consider the form of degree 4 in two variables $h(x)=x\_1^4-x\_1^2x\_2^2+x\_2^4$. We have $$m\; =\; 2,~x^\{\backslash \{m\backslash \}\}\; =\; \backslash begin\{pmatrix\}\; x\_1^2\backslash \backslash x\_1x\_2\backslash \backslash x\_2^2\backslash end\{pmatrix\}\backslash !,$$

~H+L(\alpha) = \begin{pmatrix}

1&0&-\alpha_1\\0&-1+2\alpha_1&0\\-\alpha_1&0&1

\end{pmatrix}\!. Since there exists α such that $H+L(\backslash alpha)\backslash ge\; 0$, namely $\backslash alpha=1$, it follows that h(x) is SOS.

• Consider the form of degree 4 in three variables $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$. We have $$m=2,~x^\{\backslash \{m\backslash \}\}=\backslash begin\{pmatrix\}x\_1^2\backslash \backslash x\_1x\_2\backslash \backslash x\_1x\_3\backslash \backslash x\_2^2\backslash \backslash x\_2x\_3\backslash \backslash x\_3^2\backslash end\{pmatrix\},$$

~H+L(\alpha) = \begin{pmatrix}

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{pmatrix}. Since $H+L(\backslash alpha)\backslash ge\; 0$ for $\backslash alpha=(1.18,-0.43,0.73,1.13,-0.37,0.57)$, it follows that {{math|h(x)}} is 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 $G\_1(x),\backslash ldots,G\_k(x)$ of degree m such that

$$F(x)=\backslash sum\_\{i=1\}^k\; G\_i(x)\text{'}G\_i(x)\; .$$

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

$$F(x)\; =\; \backslash left(x^\{\backslash \{m\backslash \}\}\backslash otimes\; I\_r\backslash right)\text{'}\backslash left(H+L(\backslash alpha)\backslash right)\backslash left(x^\{\backslash \{m\backslash \}\}\backslash otimes\; I\_r\backslash right)$$

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

$$F(x)\; =\; \backslash left(x^\{\backslash \{m\backslash \}\}\backslash otimes\; I\_r\backslash right)\text{'}H\backslash left(x^\{\backslash \{m\backslash \}\}\backslash otimes\; I\_r\backslash right)$$

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

$$\backslash mathcal\{L\}=\backslash left\backslash \{L=L\text{'}:~\backslash left(x^\{\backslash \{m\backslash \}\}\backslash otimes\; I\_r\backslash right)\text{'}L\backslash left(x^\{\backslash \{m\backslash \}\}\backslash otimes\; I\_r\backslash right)=0\backslash right\backslash \}.$$

The dimension of the vector $\backslash alpha$ is given by

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

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

$$H+L(\backslash alpha)\; \backslash ge\; 0.$$

The expression $F(x)\; =\; \backslash left(x^\{\backslash \{m\backslash \}\}\backslash otimes\; I\_r\backslash right)\text{'}\backslash left(H+L(\backslash alpha)\backslash right)\backslash left(x^\{\backslash \{m\backslash \}\}\backslash otimes\; I\_r\backslash right)$ was introduced in {{cite conference |title=Robust stability for polytopic systems via polynomially parameter-dependent Lyapunov functions |last1=Chesi |first1=G. |last2=Garulli |first2=A. |last3=Tesi |first3=A. |last4=Vicino |first4=A. |date=2003 |publisher=IEEE |book-title=Proceedings of the 42nd IEEE Conference on Decision and Control |pages=4670–4675 |location=Maui, Hawaii | doi=10.1109/CDC.2003.1272307 }} in order to establish whether a matrix form is SOS via an LMI.

Consider the free algebra R⟨X⟩ generated by the n noncommuting letters X = (X₁, ..., X_n) and equipped with the involution ^T, such that ^T fixes R and X₁, ..., X_n and reverses words formed by X₁, ..., X_n.

By analogy with the commutative case, the noncommutative symmetric polynomials f are the noncommutative polynomials of the form {{math|1=f = f^T}}. When any real matrix of any dimension r × 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 $h\_1,\backslash ldots,h\_k$ such that

$$f(X)\; =\; \backslash 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 it is matrix-positive.{{cite journal|last1=Helton|first1=J. William|title="Positive" Noncommutative Polynomials Are Sums of Squares|journal=The Annals of Mathematics|date=September 2002|volume=156|issue=2|pages=675–694|doi=10.2307/3597203|jstor=3597203}} Moreover, there exist algorithms available to decompose matrix-positive polynomials in sum of squares of noncommutative polynomials.{{cite journal | last1=Burgdorf|first1=Sabine|last2=Cafuta|first2=Kristijan|last3=Klep|first3=Igor|last4=Povh|first4=Janez|title=Algorithmic aspects of sums of Hermitian squares of noncommutative polynomials|journal=Computational Optimization and Applications|date=25 October 2012|volume=55|issue=1|pages=137–153|doi=10.1007/s10589-012-9513-8|citeseerx=10.1.1.416.543|s2cid=254416733 }}

{{Reflist}}

• Sum-of-squares optimization
• Positive polynomial
• Hilbert's seventeenth problem
• SOS-convexity

Category:Homogeneous polynomials

Category:Real algebraic geometry