Are elements in each stage of the Lasserre hierarchy convex?

39 Views Asked by At

The Lasserre hierarchy is a schema for proving multivariate polynomials positive via a sum of squares decomposition. At the first level, a polynomial $p$ is written $$p = \sum_i f_i^2$$ where each $\deg(f_i) \le \deg(p)/2$. At higher levels, an additional quadratic is multiplied onto each side $$\left(\sum_i g_i^2\right)p = \sum_i f_i^2$$ $$\implies p = \sum_i \frac{f_i^2}{\sum_j g_j^2}$$ A particular "level" of the hierarchy is given by fixing the maximum degree of $g$. It is known that all positive polynomials can be proved positive at some level of this hierarchy.

Now, at the first level are just polynomials that are sum of squares. This is clearly a convex set. At the "infinite" level are the positive polynomials. This is also clearly a convex set.

What about the polynomials that can be solved at e.g. the third level (or below)? It isn't obvious how, given two polynomials and their decompositions, a decompostion could be guaranteed for their convex combination.

1

There are 1 best solutions below

0
On BEST ANSWER

I have found that in fact a given level of the hierarchy isn't necessarily convex. As a concrete example, the Motzkin polynomial (in a certain inhomogeneous formulation) is:

$$M_1 = w^4x^2 + w^2x^4 + 1 - 3w^2x^2$$

and it is known to be positive, but not sum-of-squares, but it is in the second level of the Lasserre hierarchy: it becomes sum-of-squares when multiplied by $(w^2+x^2)$. Changing variables gives an equivalent polynomial

$$M_2 = y^4z^2 + y^2z^4 + 1 - 3y^2z^2$$

which has the same properties. A convex combination (specifically their mean) is then

$$M_3 = \frac{M_1+M_2}{2} = \frac{1}{2}\left(w^4x^2 + w^2x^4 + y^4z^2 + y^2z^4 - 3w^2x^2 - 3y^2z^2 + 2\right)$$

I checked this polynomial with an SOS solver at the second level and, unlike $M_1$ and $M_2$, $M_3$ cannot be proven to be positive at the second level. It of course ''can'' be proven to be positive at the third level, by multiplying $(w^2+x^2)(y^2+z^2)$. In general a pair of polynomials $p$ and $q$ that are SOS at levels $m$ and $n$ are always SOS at level $n+m-1$.

I'm not aware of this fact being mentioned anywhere in literature. But, it's hard to search for, because "convex" is so overloaded here.