Is a degree-$d$ pseudo distribution always a relaxation?

Question

The optimization problem we are generally concerned with looks like the following,
\begin{eqnarray*} &\inf \{ p(x) \vert x \in K\} \\ &K = \{ x \in \mathbb{R}^n \vert q_i(x) \geq 0, i = 1,..,m \} \end{eqnarray*}

where $p(x)$ is some polynomial objective function and $q_i(x)$ are polynomial constraints.

One can look at this corresponding question,

\begin{eqnarray*} &\inf_D \{ \tilde{\mathbb{E}_D} [p] \} \\ &s.t \\ &D : \{ 0,1\} ^n \rightarrow \mathbb{R} \\ &\sum_{x \in \{0,1\}^n} D(x) = 1 \\ & \forall u \in SOS_d \\ &\tilde{\mathbb{E}}_D [u] \geq 0 \\ &\tilde{\mathbb{E}}_D[q_i] \geq 0 \end{eqnarray*}

Here we use the ``pseudo-expectation" notation" whereby we have for any function $f$, $\tilde{\mathbb{E}}_D[f] = \sum_{x \in \{ 0,1\}^n } D(x)f(x)$ And $SOS_d$ is the cone of all real polynomials in $n-$variables which can be written as a sum of squares of polynomials of degree at most $\frac{d}{2}$

• Is it clear that for all $d$ the later is a relaxation of the former?

  If we restrict the polynomials to be valued on the hypercube $\{0,1\}^n$ then I can think of an argument which shows that the latter is a relaxation of the former by going through an intermediate Lassere relaxation. But if the polynomials are valued on the whole of $\mathbb{R}^n$ (as written above) then my above argument works only if $n^d < 2^n$.

• Is there a proof that if one keeps increasing the $d$ then at $d=n$ the later will exactly hit the infimum being searched for in the first?

Answer 1

To see that this is a relaxation, all you have to check is that each feasible solution to the first problem gives rise to a feasible solution to the second problem. All you have to do is, given $x \in K$, take an actual distribution $D$ concentrated on $x$. (This only works if in the definition of $K$ you replace $\mathbb{R}^n$ with $\{0,1\}^n$; your formulation doesn't make too much sense.)

When $d = n$, the conditions guarantee that $D$ is an actual distribution. If the objective function $p$ is concave then the optimal distributions are singletons, and so both programs have the same value. Otherwise it could be that for some distribution $D$ supported on $K$ it holds that $\mathbb{E}_{X\sim D}[p(X)] < \min_x p(x)$.