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?


1 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)$.

  • $\begingroup$ 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$? $\endgroup$ Mar 22, 2016 at 0:29
  • $\begingroup$ (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. $\endgroup$ Mar 22, 2016 at 6:33
  • $\begingroup$ 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! $\endgroup$ Mar 24, 2016 at 14:33
  • $\begingroup$ Yes, my gut feeling is that when $d = n$ you will get an actual distribution. I'll let you figure out the rest. $\endgroup$ Mar 24, 2016 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.