<p>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$. </p>

<ul>
<li>Can this relaxed problem be now completely defined over the reals with no need to anymore look at the Boolean hypercube? </li>
</ul>

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

<p>(A)</p>

<p>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? </p>

<p>Next we have in principle $2$ options about how to define $\mu$,</p>

<p>(B1)</p>

<p>$\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$. </p>

<p>(B2) </p>

<p>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}$?</p>

<p>(..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..)</p>

<hr>

<ul>
<li><p>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.</p></li>
<li><p>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. </p></li>
</ul>

CC BY-SA 3.0
2017-02-02T03:44:11.507Z
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
CC BY-SA 3.0
2017-02-03T02:20:40.727Z
@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
CC BY-SA 3.0
2017-02-03T02:23:55.773Z
@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
CC BY-SA 3.0
2017-02-03T02:33:55.423Z
@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
<cc.complexity-theory><np-hardness><semidefinite-programming><sum-of-squares>
Can the Lasserre relaxation be defined over the reals?
gradstudent
# Can the Lasserre relaxation be defined over the reals?

(Asked by: username_0 on 2017-02-01)

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.

**Tags:** cc.complexity-theory, np-hardness, semidefinite-programming, sum-of-squares

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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$  
> **username_0**: @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.  
> **username_0**: @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)!?  

---

## 0 answers

