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

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?

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)$.
• Thanks! (1) So you mean that for functions not valued on the hypercube there is no such relaxation that can be proven? (2) When you say "an actual distribution $D$ concentrated on $x$" you mean a $D$ which maps $x$ to $1$ and the rest of the vertices to $0$. (3) Can you please explain how do you see that at $d=n$ the $D$ is forced to be an actual distribution? So are you saying that if $p$ has a local minima then $D$ at $d=n$ is somehow forced to be an indicator function for the vertex $x$? – gradstudent Mar 22 '16 at 0:29
• (1) Not in general. (2) Yes. (3) Use the fact that every function on the hypercube is a polynomial of degree at most $n$. You don't necessarily get an indicator function for one point ("a singleton"). In some cases there is always an optimal answer which is a singleton, and it can be gleaned from any other optimal answer. – Yuval Filmus Mar 22 '16 at 6:33
• Thanks! (2) So you are saying that at $d=n$ this pseudo-distribution will necessarily be an actual distribution on the hypercube which will be supported exactly on those vertices which are the minima of the original infimum problem? (2) Now I am wondering if in the "equivalent" pseudo-distribution problem I should have been maximizing the pseudo-expectation instead of trying to minimize it (as I wrote it in the question!) because more precisely the later is a conic dual of the former! – gradstudent Mar 24 '16 at 14:33
• Yes, my gut feeling is that when $d = n$ you will get an actual distribution. I'll let you figure out the rest. – Yuval Filmus Mar 24 '16 at 14:40