# Can the Lasserre relaxation be defined over the reals?

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.

• 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. – Joshua Grochow Feb 2 '17 at 3:44
• @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$ – gradstudent Feb 3 '17 at 2:20
• @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. – gradstudent Feb 3 '17 at 2:23
• @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)!? – gradstudent Feb 3 '17 at 2:33