Doble de un SDP ${\min}_{X \in \mathcal{S}^n} \quad \ {\rm trace}( W X )$ s.t. $X_{ii} = 1$ ; $X \succeq 0$

Question

Cómo obtener el dual del siguiente problema de programación semidefinida (SDP)

\begin{align} \text{minimize}_{X \in \mathcal{S}^n} \quad & {\rm trace}( W X ) \\ \text{subject to }\quad & X_{ii} = 1 \Longleftrightarrow {\rm trace}( e_i^T X e_i) = 1 \quad \forall i = 1,\ldots,n\\ & X \succeq 0 \ \Longleftrightarrow -{\rm trace}( a^T X a) \leq 0 , \quad {\rm for all } \ a \in \mathbb{R}^n \diagdown 0. \end{align} donde $e \in \mathbb{R}^n$ es un vector de base estándar, $X \in \mathcal{S}^{n \times n}$ matrices simétricas, y $W \in \mathbb{R}^{n \times n}$ .

Answer 1

Se trata de la relajación SDP de un programa cuadrático binario. Por lo tanto, como se señala, por ejemplo, en la sección 1.2 de estos notas tiene el siguiente problema dual: \begin{align*} \max \quad & \mathrm{tr}(\Lambda)\\ \text{s.t.} \quad & W \succeq \Lambda,\\ & \Lambda_{i,j}=0, \ \forall i \neq j. \end{align*}

Answer 2

He aquí mi intento de escribir el dual del problema anterior. ¿Pueden los expertos comentar mi enfoque? Gracias de antemano.

El Lagrangiano puede formarse como \begin{align} L(X, S, t) :&= {\rm trace}\left( W X \right) - {\rm trace}\left( S^T X \right) + t^T\left( {\rm diag}(X) - 1\right) \\ &= {\rm trace}\left( \left[ W - S^T + {\rm Diag}(t) \right] X \right) -1^T t \end{align} donde $S \succeq 0$ matriz y $t$ vector columna son multiplicadores de Lagrange. ${\rm diag}(\cdot)$ crea un vector extrayendo los elementos diagonales de una matriz. ${\rm Diag}(\cdot)$ crea una matriz diagonal apilando los elementos del vector a lo largo de la diagonal principal de una matriz. Todos los vectores de unos se muestran como $1$ .

Ahora, la función dual puede mostrarse como \begin{align} g(S,y) :&= \inf_{X} L(X,S,t) \\ &= \left\{ \begin{matrix} -1^T t & \quad W - S^T + {\rm Diag}(t) =0 ; \\ -\infty & {\rm otherwise}. \end{matrix} \De acuerdo. \Fin.

Sin pérdida de generalidad, podemos suponer que $S$ es una matriz simétrica, es decir, $S^T = S$ .

El problema dual es \begin{equation} \begin{aligned} & \underset{S, \ y}{\text{maximize}} & & -1^T t \\ & \text{subject to} & & {\rm Diag}(t) \ - S = W ,\\ &&& S \succeq 0 \ . \end{aligned} \end{equation}