Nonnegative and SOS cones

Let $\mathbb{R}[x]_{n,d}$ be the vector space of real polynomials in $n$ variables of degree at most $d$.

(a) Let $P_{n,2d}$ be the set of nonnegative polynomials in $\mathbb{R}[x]_{n,2d}$:

$P_{n,2d}=\{ p \in \mathbb{R}[x]_{n,2d} | p(x) \geq 0, \forall x \in \mathbb{R}^n\}$

Then $P_{n,2d}$ is a closed full-dimensional convex cone in $\mathbb{R}[x]_{n,2d}$

If $f,g \in P_{n,2d}$ and $x \in \mathbb{R}^n$, then for any $s,t \in \mathbb{R}_+$ we have $sf(x)\geq 0$ and $tg(x) \geq 0$ so that $sf(x) +tg(x) \geq 0$. So $P_{n,2d}$ is a convex cone.

To show that $P_{n,2d}$ is closed, take a sequence $\{f_j\}$ in $P_{n,2d}$ converging to $f \in \mathbb{R}[x]_{n,2d}$. Evaluation at a point $x \in \mathbb{R}^n$ is a linear functional on the space $\mathbb{R}[x]_{n,2d}$, and so $f(x)=\lim f_j(x)\geq 0$.

In part (b) we'll show $\Sigma_{n,2d}$ is full-dimensional. This implies that $P_{n,2d}$ is full-dimensional because $P_{n,2d}$ contains $\Sigma_{n,2d}$.-MH

(b) Let $\Sigma_{n,2d}$ be the set of sums of squares in $\mathbb{R}[x]_{n,2d}$:

$\Sigma_{n,2d}=\{ p \in \mathbb{R}[x]_{n,2d} | p(x) = \Sigma q_i^2 \text{ for some } q_i \in \mathbb{R}[x]_{n,d}\}$.

Then $\Sigma_{n,2d}$ is a closed full-dimensional convex cone in $\mathbb{R}[x]_{n,2d}$.

Again, the proof of convexity and conehood is straightforward. Let us show that $\Sigma_{n,2d}$ is full-dimensional. Note that $\Sigma_{n,2d}$ contains $u^2$ and $(u+v)^2$ for all monomials $u,v$ of degree at most $d$. Since the set of all such polynomials spans $\mathbb{R}[x]_{n,2d}$, the convex cone $\Sigma_{n,2d}$ contains a spanning set. Any convex cone containing a spanning set must be full-dimensional (not true of a merely convex set!). Thus we have shown that $\Sigma_{n,2d}$ (and therefore $P_{n,2d}$) is full-dimensional.

Now to show that $\Sigma_{n,2d}$ is closed. Define $K = \{p \in \Sigma_{n,2d} : \int \limits_{[0,1]^n}p = 1\}$.

Then $K$ is convex and does not contain the origin because it is the intersection two convex sets one of which does not contain the origin. In order to invoke the previous exercise, we must show that $K$ is compact.

By Caratheodory's convex hull theorem, every member of $\Sigma_{n,2d}$ can be expressed as a sum of $N=dim(\mathbb{R}[x]_{n,2d})+1$ squares $q_i^2$ where $q_i \in \mathbb{R}[x]_{n,d}$. Since

$(q_1, \ldots, q_N) \mapsto (\int \limits_{[0,1]^n}(\sum\limits_{i=1}^Nq_i^2))^{\frac{1}{2}}$

is a norm, the constraint

$\int \limits_{[0,1]^n}(\sum\limits_{i=1}^Nq_i^2) = 1$

says that the norm of $(q_1, \ldots, q_N) \in \mathbb{R}[x]_{n,d}^N$ is equal to $1$. The set of such tuples is compact and its image under the polynomial map

$(q_1, \ldots, q_N) \mapsto \sum\limits_{i=1}^Nq_i^2$

is exactly the set $K$. Finally, since the conical hull of $K$ is equal to $\Sigma_{n,2d}$, we have shown that $\Sigma_{n,2d}$ is closed.-MH

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License