Polynomial SOS on arvau

Wikipedia / Polynomial SOS

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 of degree m

Every form that is SOS is also a positive polynomial, although the converse is not always true in general. In the special cases of n = 2 and 2m = 2, or n = 3 and 2m = 4, Hilbert proved that a form is SOS if and only if it is positive. The same is also true for the analogous problem with positive symmetric forms.

Although not every form is SOS, there are efficiently testable sufficient conditions for a form to be SOS. that are SOS.

Square matricial representation (SMR)

To establish whether a form is SOS amounts to solving a convex optimization problem. Indeed, any is a vector containing a basis for the space of forms of degree m in x (such as all monomials of degree m), H is any symmetric matrix is a linear parameterization of the linear subspace

The polynomial is a positive-semidefinite matrix. This is a linear matrix inequality is a convex feasibility problem.

was introduced with the name square matricial representation (SMR) in order to establish whether a form is SOS via an LMI. is also known as a Gram matrix.

Examples

Since there exists , it follows that h(x) is SOS.
, it follows that is SOS.

Generalizations and analogs

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 of degree m

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 is the Kronecker product of matrices, H

Then,

was introduced 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 , such that fixes R and X1, ..., Xn and reverses words formed by X1, ..., Xn. We consider Hermitian noncommutative polynomials f, which are the noncommutative polynomials of the form . When evaluating a Hermitian noncommutative polynomial f on any n-tuple of real matrices of any size r × r produces in a positive semi-definite matrix, f is said to be matrix-positive.

Surprisingly, in the noncommutative scenario a noncommutative polynomial is SOS if and only if it is matrix-positive. Moreover, there exist algorithms available to decompose matrix-positive polynomials in sum of squares of noncommutative polynomials.

Polynomial HSOS

is the Hermitian transpose can be done by testing if a single, fixed matrix is positive-semidefinite.