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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.