3
$\begingroup$

If one wants to say minimize a function $f : \{-1,1\}^n \rightarrow \mathbb{R}$ on its domain then a degree$-d$ Lasserre relaxation of it would be to solve the problem of $\min \mathbb{E}_\mu [f(x)]$ over degree$-d$ pseudo-distributions $\mu$.

  • Can this relaxed problem be now completely defined over the reals with no need to anymore look at the Boolean hypercube?

It seems to me that there are a few choices here about how to define this relaxation.

(A)

Is the relaxation now well defined if $f$ is lifted in anyway to a function $f : \mathbb{R}^n \rightarrow \mathbb{R}$ such that on the Boolean hypercube it matches the original value?

Next we have in principle $2$ options about how to define $\mu$,

(B1)

$\mu$ can be defined as any function from $\mathbb{R}^n \rightarrow \mathbb{R}$ such (a) $ \sum_{x \in \{-1,1\}^n} \mu(x) =1$ and (b) when any function $g$ is taken from the real $SOS_d$ cone we would have $ \sum_{x \in \{-1,1\}^n} \mu(x)g(x) \geq 0$.

(B2)

Or is it necessary that $\mu$ and $g$ be satisfying the above properties but $\mu$ maps from $ \{-1,1\}^n \rightarrow \mathbb{R}$ and $g$ be a member of the $SOS_d$ cone of polynomials each of which is also a map, $ \{-1,1\}^n \rightarrow \mathbb{R}$?

(..the "degree" of a polynomial as in the real $SOS_d$ cone may not match the degree of its representative in the $SOS_d$ cone of functions on the Boolean hypercube and there is no unique way to go the otherway..)


  • I think the $\mu$s defined by conditions B1 will automatically satisfy the conditions in B2 and vice-verse. But there could be an effect of this choice depending on how one resolved the options in A.

  • Also I think the option B1 makes most sense since otherwise the relaxed problem is probably isnt a standard SDP that can be run in polynomial time.

$\endgroup$
  • 1
    $\begingroup$ I'm not an expert in SOS, but a natural way to go would be to consider only mutilinear real polynomials. Then their degree on the boolean cube (if we do an affine linear transformation to make it {0,1} instead of {-1,1}) agrees with their actual degree... Depends on what you want this generalization for, I guess. $\endgroup$ – Joshua Grochow Feb 2 '17 at 3:44
  • $\begingroup$ @JoshuaGrochow Thanks for your comment. Let me try to frame a little differently as to what I am concerned about. There are two distinct kinds of questions that one could have been given to solve. (Type 1) One is given a $f : \mathbb{R}^n \rightarrow \mathbb{R}$ and one wants to find its minima on $\{-1,1\}^n$. (Type 2) One is given a $g : \mathbb{F_2}^n \rightarrow \mathbb{R}$ and one wants to find its minima on $\{-1,1\}^n$ $\endgroup$ – gradstudent Feb 3 '17 at 2:20
  • $\begingroup$ @JoshuaGrochow Now if one wants to define the Lasserre relaxation of for any of this then I guess it makes sense only w.r.t the real $SOS_d$ cone defined as $\{ h : \mathbb{R}^n \rightarrow \mathbb{R} \vert h = \sum q_i^2 \text { where } q_i \text{ is a polynomial of degree atmost } \frac{d}{2}\}$. But to do this on Type 2 problems one will have to first lift (non-uniquely!) $g$ to a $\tilde{g} : \mathbb{R}^n \rightarrow \mathbb{R}$ such that $\tilde{g}$ and $g$ coincide on the Boolean hypercube. $\endgroup$ – gradstudent Feb 3 '17 at 2:23
  • $\begingroup$ @JoshuaGrochow Now when one is conventionally looking at say the Max-CUT polynomial of a graph $G=(V,E)$ then over $x \in \{-1,1\}^n$ the polynomial is written as $ \frac{1}{4} \sum_{(ij) \in E} (x_i - x_j)^2$ and now I am not sure whether to think of the optimization polynomial as as of (Type 1) or (Type 2)!? $\endgroup$ – gradstudent Feb 3 '17 at 2:33

Your Answer

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

Browse other questions tagged or ask your own question.