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
of degree m such that
![{\displaystyle h(x)=\sum _{i=1}^{k}g_{i}(x)^{2}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/393576199445ebae5cc21be5aed8984c8e3faf35)
Every form that is SOS is also a positive polynomial, and although the converse is not always true, Hilbert proved that for n = 2, 2m = 2, or n = 3 and 2m = 4 a form is SOS if and only if it 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
-norm of its coefficient vector) by a sequence of forms
that are SOS.[6]
To establish whether a form h(x) is SOS amounts to solving a convex optimization problem. Indeed, any h(x) can be written as
where
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
and
is a linear parameterization of the linear space
![{\displaystyle {\mathcal {L}}=\left\{L=L':~x^{\{m\}'}Lx^{\{m\}}=0\right\}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/a01e91e36eaabaf4357c96a31dfe20d72906bec5)
The dimension of the vector
is given by
whereas the dimension of the vector
is given by
![{\displaystyle \omega (n,2m)={\frac {1}{2}}\sigma (n,m)\left(1+\sigma (n,m)\right)-\sigma (n,2m).}](//wikimedia.org/api/rest_v1/media/math/render/svg/48bca70d27dfd44bdf0906b8bbc33110b8a903dd)
Then, h(x) is SOS if and only if there exists a vector
such that
meaning that the matrix
is positive-semidefinite. This is a linear matrix inequality (LMI) feasibility test, which is a convex optimization problem. The expression
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
. We have
Since there exists α such that
, namely
, it follows that h(x) is SOS.
- Consider the form of degree 4 in three variables
. We have
Since
for
, it follows that h(x) is SOS.
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
of degree m such that
![{\displaystyle F(x)=\sum _{i=1}^{k}G_{i}(x)'G_{i}(x).}](//wikimedia.org/api/rest_v1/media/math/render/svg/10b91e2a687a210327c554f5cb5129de776ae91f)
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
where
is the Kronecker product of matrices, H is any symmetric matrix satisfying
and
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\}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/abc96c78eba6f9e86d68743ce34d96221b8d40b8)
The dimension of the vector
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).}](//wikimedia.org/api/rest_v1/media/math/render/svg/192b69d876a819d346809cfbec3558b47ae81d2c)
Then, F(x) is SOS if and only if there exists a vector
such that the following LMI holds:
![{\displaystyle H+L(\alpha )\geq 0.}](//wikimedia.org/api/rest_v1/media/math/render/svg/252463bebd22832c4003fcd0d97855b8e0bfb12a)
The expression
was introduced in [9] in order to establish whether a matrix form is SOS via an LMI.
Noncommutative polynomial SOS
Consider the free algebra R⟨X⟩ generated by the n noncommuting letters X = (X1, ..., Xn) and equipped with the involution T, such that T fixes R and X1, ..., Xn and reverses 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 × 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
such that
![{\displaystyle f(X)=\sum _{i=1}^{k}h_{i}(X)^{T}h_{i}(X).}](//wikimedia.org/api/rest_v1/media/math/render/svg/0a38864024bbb79acd55a1098f9c6dc24ad471d8)
Surprisingly, in the noncommutative scenario a noncommutative polynomial is SOS if and only if it is matrix-positive.[10] Moreover, there exist algorithms available to decompose matrix-positive polynomials in sum of squares of noncommutative polynomials.[11]
Choi, M. D.; Lam, T. Y. (1977). "An old question of Hilbert". Queen's Papers in Pure and Applied Mathematics. 46: 385–405.
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. doi:10.1109/CDC.2003.1272307. Helton, J. William (September 2002). ""Positive" Noncommutative Polynomials Are Sums of Squares". The Annals of Mathematics. 156 (2): 675–694. doi:10.2307/3597203. JSTOR 3597203.