3
$\begingroup$

Sum of Squares proofs and the Lasserre hierarchy can both be stated as SDPs. It is often claimed without proof that these SDPs are dual to each other, although I do not see that this is obvious. I was hoping to get some help proving that these are in-fact SDP duals of each other.

I will state the two SDPs and then give some background information. We will have variables $y_I$ for $I \subseteq [n]$ a multi-set and $|I| \leq d$. Let $Y$ be an $n^d + 1 \times n^d+1$-dimensional matrix, indexed by multi-sets $I \subseteq [n]$, $|I| \leq d$, and let $Y_{I,J} = y_{I \cup J}$ (under multi-set union). Let $A$ be a diagonal matrix. Let $B_I$, $C_I$ be matrices of the same dimension as $Y$. Define the trace $\langle A,B \rangle = \sum_{i,j} A_{i,j} B_{i,j}$; that is, the inner product between $A$ and $B$ when treated as vectors. We can state the primal Lasserre SDP abstractly as

$$\max \langle A, Y \rangle \\ \sum_I y_I B_I \succeq 0 \\ \sum_I y_I C_I \succeq 0 \\ y_\emptyset = 1 $$

Let $e \in \mathbb{R}^{n^d +1}$ be a vector such that $e_\emptyset = 1$ and $e_I = 0$ for all $I \neq \emptyset$. The dual is

$$ \min \lambda \\ A_I - \lambda e_I = \langle Z_1, B_I \rangle + \langle Z_2, C_I \rangle \hspace{3em} \forall I \subseteq [n], |I| \leq d \\ Z_1 \succeq 0 \\ Z_2 \succeq 0 $$

Background: Suppose that we're trying to optimize a polynomial $P_0(x)$ over $ P_1(x) \geq 0$. The Lasserre hierarchy is a hierarchy is a hierarch of SDP relaxations, where the $d$-th level is defined as follows: Let $Y$ be as above and let $p_0, p_1 \in \mathbb{R}^{n^d+1}$ be the coefficient vectors of $P_0(x), P_1(x)$ respectively. That is, $p_{0,I}$ is the coefficient of the monomial $\prod_{i \in I} x_i$ in $P_0(x)$.

Define the matrices $M(y) := Y$ and $M(y,P_1)_{|I|,|J| \leq d - deg(P_1)/2} := \sum_{|K| \leq deg(P_1)} p_{1,K} y_{I \cup J \cup K}$, and let $P$ be the diagonal matrix with $p_0$ arranged along the diagonal. Then, the primal degree-$d$ Lasserre SDP is

$$ \max P \cdot Y \\ M(y) \succeq 0 \\ M(y,P_1) \succeq 0 \\ y_\emptyset = 1 $$

We can obtain the primal SDP that I stated originally from the Lasserre SDP by letting $B_I, C_I$ be such that $M(y) = \sum_I B_I y_I$ and $M(y,P_i) = \sum_I C_I y_I$. For more information, I recommend Chapter 1.7 in "Handbook on Semidefinite, Conic and Polynomial Optimization" https://link.springer.com/book/10.1007%2F978-1-4614-0769-0#page14

$\endgroup$

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.