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

  • $\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$ – gradstudent Mar 22 '16 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$ – Yuval Filmus Mar 22 '16 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$ – gradstudent Mar 24 '16 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$ – Yuval Filmus Mar 24 '16 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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