Explicit LMI representation of sum of square (SOS) cones

290 Views Asked by At

The cone of sum of square (SOS) polynomials is a projected spectrahedron. This should mean we can find a linear matrix inequality (LMI) whose projection is a SOS cone. For example, the quartic SOS polynomials cone $\Sigma_{1,4}:\{(f_0,f_1,f_2,f_3,f_4) \in \mathbb{R}^5 \mid \sum_{i=0}^4f_ix^i\geq0, \forall x \in \mathbb{R}\}$ can be represented as

$$\begin{bmatrix} f_0 & \frac{1}{2}f_1 & \frac{1}{3}f_2-\mu \\ \frac{1}{2}f_1& \frac{1}{3}f_2+2\mu & \frac{1}{2}f_3 \\\frac{1}{3}f_2-\mu & \frac{1}{2}f_3 & f_4 \end{bmatrix}\succeq 0$$

where $\mu$ is the "lifting variable".

The question is, is there a general expression for general (multivariate) polynomial space? For example, for polynomial in $n$ variables and with degree at most 2d, is there a explicit expression of projected LMI parametrized by coefficients of the polynomials and lifting variables for SOS cone in such vector space?

1

There are 1 best solutions below

0
On

This is a late reply, but it might be helpful for other people who stumble upon this question as I did.
It is well known, that $\Sigma_{n,2d}$ can be represented as a subset of the space $\mathbb{R}[x]_{2d}$ of multivariate polynomials of degree at most $2d$ as follows, see e.g. here: $$ \Sigma_{n,2d} = \left\lbrace v_{n,d}^{\mathsf{T}}Av_{n,d} \mid A \in \mathcal{S}_+^k \right\rbrace $$ Here, $\mathcal{S}_+^k$ denotes the positive semidefinite cone of $k\times k$ matrices, $k = {n+d \choose n}$ and $v_{n,d}$ is the vector of all monomials of degree at most $d$ in $n$ variables.
In order the get an LMI representation in terms of the coefficients, one would have to expand the expression $v_{n,d}^{\mathsf{T}}Av_{n,d}$ to obtain linear equations relating the coefficients to the entries of $A$. These equations can then incorporated into the representation by introducing lifting variables.
Let's consider your example of $\Sigma_{1,4}$. We have $v_{1,2} = (x^2,x,1)^{\mathsf{T}}$ and $$ v_{1,2}^{\mathsf{T}}Av_{1,2} = a_{11}x^4+2a_{12}x^3+(2a_{13}+a_{22})x^2+2a_{23}x+a_{33}.$$ We see, that, except for the coefficient of $x^2$, all coefficients depend on one entry of $A$ only. Therefore, we can already set $f_4=a_{11}, \frac{1}{2}f_3=a_{12}, \frac{1}{2}f_1=a_{23}, f_0=a_{33}$. It remains the equation $f_2=2a_{13}+a_{22}$, where we have one degree of freedom. Defining $\mu := \frac{1}{2}a_{22}-\frac{1}{6}f_2$ gives your representation.