Let us start with the optimization question,

\begin{eqnarray*} min \{ c \vert c - f \in SOS_d \} \end{eqnarray*}

for some function $f : \{0,1\}^n \rightarrow \mathbb{R}$ and $SOS_d $ being the cone of all polynomials on $\mathbb{R}^n$ which can be written as a sum of squares of polynomials each of degree at most $\frac{d}{2}$. This can be cast as a SDP by doing the "gram matrix" rewriting of any polynomial in $SOS_d$.

  • Now how do we show that the above is dual with no duality gap to this following optimization question?

\begin{eqnarray*} &max_D \{ \tilde{\mathbb{E}}_D [f] \} \\ &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 \end{eqnarray*}

where for any function $g : \{0,1\}^n \rightarrow \mathbb{R}$ we have $\tilde{\mathbb{E}}_D [g] := \sum_{x \in \{0,1\}^n} D(x)g(x)$

I tried writing a conic duality for the first to get it to look like an optimization over Lasserre maps but that approach didn't work...

  • $\begingroup$ Talking to some professors I figured out why the later should be a conic dual of the former but I still don't know why the duality gap should be $0$. Any reference explaining this would be very helpful! $\endgroup$ – gradstudent Mar 24 '16 at 14:34

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.