Dual de un programa semidefinido en forma no estándar

Question

Tengo un problema con el cálculo del problema dual de :

$$ \mbox{Minimize } tr(Y) + \frac{1}{\eta} tr(Z) $$

$$ \begin{pmatrix} Y & X \\ X & Z+\varepsilon I \end{pmatrix} \succeq 0 \mbox{, } % \begin{pmatrix} I & X \\ X & Z \end{pmatrix} \succeq 0$$

$$ \langle A_i,X\rangle = 0\mbox{, } i=1,\cdots,m \mbox{, } \; \; 1\leq tr(X) \leq \sqrt{n} \mbox{, } \; \; X\succeq 0$$

donde ; $X,Y,Z$ son matrices simétricas de dimensión $n \times n$ , $A_i$ son m matrices simétricas de carrete dadas de dimensión $n \times n$ , $\varepsilon$ y $\eta$ son constantes del carrete, y $\langle A,X\rangle = \sum a_{ij}x_{ij}$

si alguien sabe algo me lo dice por favor, porque mi único conocimiento del problema dual es lo que está en el libro de Stephen Boyd y Lieven Vandenberghe, Optimización convexa (capítulo 5). pero no veo cómo puedo reformular este problema para obtener la forma estándar del SDP especialmente cuando la función objetivo contiene dos variables (Y, Z) donde en la forma estándar es un $X\succeq 0$ . No me interesa la formulación estándar pero supongo que este es el primer paso para encontrar el problema dual, ¿me equivoco?

Gracias;

Answer 1

Permítame decirle de dónde saqué esta pregunta: Es de un artículo escrito por Yun-Bin Zhao, Approximation Theory of Matrix Rank Minimization and Its Application to Quadratic Equations. En la versión publicada se omite el procedimiento para obtener el problema dual, pero, por casualidad lo encontré en el preprint one :

este es el procedimiento en detalle, la única información requerida es que :

si formulamos el SDP en la forma : $$ \begin{array}{rll} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n} & \\ \text{subject to} & \langle A_i, X \rangle_{\mathbb{S}^n} = b_i, \quad i = 1,\ldots,m & (P) \\ & X \succeq 0 & \end{array} $$ El problema dual viene dado por : $$ \begin{array}{rll} {\displaystyle\max_{y \in \mathbb{R}^m}} & \langle b, y \rangle_{\mathbb{R}^m} & \\ & & (D) \\ \text{subject to} & {\displaystyle\sum_{i=1}^m} y_i A_i \preceq C & \end{array} $$

donde para dos matrices cualesquiera P y Q, $P \succeq Q$ significa $P-Q \succeq 0$ .

a partir de la cual podemos comprobar fácilmente que el dual de (observaré que por $(P')$ ) :

\begin{equation} \min \{\langle C_0, W \rangle : \langle C_i, W\rangle = b_i, i=1, ..., l, ~ \delta_1\leq \langle C, W \rangle \leq \delta_2, ~ W \succeq 0, \} \end{equation} viene dada por \begin{equation} \max \left\{ b^T y + \delta_1 t_1 +\delta_2 t_2: ~ \sum_{i=1}^l y_i C_i +(t_1 +t_2) C \preceq C_0, ~t_1\geq 0, ~t_2\leq 0 \right\}, \end{equation} donde $b=(b_1, ..., b_l)^T$ . ( nota que $b^Ty=\langle b, y \rangle_{\mathbb{R}^m}$ :) )

Para obtener el problema dual del problema de mi pregunta, reescribamos el problema como la forma de (P) . Obsérvese que las condiciones semidefinidas positivas (restricción) en el problema de mi pregunta son equivalentes a :

$$ W' =\begin{pmatrix} X & 0 & 0 & 0 & 0\\ 0 & I & X & 0 & 0 \\ 0 & X & Z & 0 & 0 \\ 0 & 0 & 0 & Y & X \\ 0 & 0 & 0 & X & Z+\varepsilon I \end{pmatrix} \succeq 0 . $$ Dejemos que $ E^{(k, l)} \in S^ {5n\times 5n} $ ( $k,l=1,..., 5n)$ denotan las matrices simétricas con $(k, l)$ Esta entrada = $(l, k)$ la entrada $= 1$ y cero en el resto. Cuando $k=l$ , $ E^{(k, k)} $ denota la matriz con ( $k,k)$ 1 y todos los demás elementos 0. Claramente, tenemos $E^{(l,k)}=E^{(k,l)}$ para cualquier $(k,l).$ Obsérvese que para cualquier matriz $W=(w_{i,j}) \in S^{5n\times 5n},$ se puede representar como $W=\sum_{k=1}^{5n} \sum_{l=k}^{5n} w_{k,l}E^{(k,l)},$ y $ \langle E^{(k, l)}, W \rangle = w_{k,l}+w_{l,k} = 2w_{k,l}$ para $k\not=l,$ y $ \langle E^{(k, k)}, W \rangle = w_{k,k}. $ En en términos de $E^{(\cdot, \cdot)},$ la condición ( $W' \succeq 0 $ ) puede escribirse como el siguiente conjunto de restricciones

$$ \begin{array} & &W & \succeq & 0 , \\ 1& \langle E^{(i, ~n+j)}, W \rangle & = & 0, ~~i = 1, ..., n, j=1,..., 4n, \\ 2& \langle E^{(n+i, ~3n+j)}, W \rangle & = & 0, ~~i,j = 1, ..., 2n, \\ 3& \langle E^{(n+i, ~n+j)}, W \rangle & = & 0, ~ i=1, ..., n-1, j=i+1,..., n, \\ 4& \langle E^{(n+i, ~n+i)}, W \rangle & = & 1, ~ i=1,..., n, \\ 5& \langle E^{(i,j)}-E^{(n+i, ~2n+j)}, W \rangle & = & 0, ~~ i=1,..., n-1, ~ j=i+1, ..., n, \\ 6& \langle E^{(j,i)}-E^{(n+j, ~2n+i)}, W \rangle & = & 0, ~i=1,..., n-1, ~j=i+1, ..., n, \\ 7& \langle 2 E^{(i,i)}-E^{(n+i, ~2n+i)}, W \rangle & = & 0, ~~ i =1, ..., n, \\ 8& \langle E^{(n+i,2n+j)}-E^{(3n+i, ~4n+j)}, W \rangle & = & 0, ~~ i,j=1, ..., n, \\ 9& \langle E^{(4n+i, ~4n+j)}- E^{(2n+i, ~2n+j)} , W \rangle & = & 0, ~~i=1,..., n-1, j =i+1,..., n , \\ 10& \langle E^{(4n+i, ~4n+i)}- E^{(2n+i, ~2n+i)} , W \rangle & = & \varepsilon, ~~i=1, ..., n , \end{array} $$

donde (1) y (2) representan los bloques cero de la matriz $W'$ las condiciones (3) y (4) describen el bloque $I$ (el $n\times n $ matriz de identidad), las condiciones (5) a (8) representan la $X$ bloques, y (9) y (10) describen la relación entre los bloques $Z$ y $Z+\varepsilon I$ en el mismo.

En términos de $W\in S^{5n\times 5n},$ la igualdad $\langle A_i, X\rangle =0$ en el problema de mi pregunta se puede escribir como $\langle P_i, W\rangle =0, $ la desigualdad $ 1\leq \textrm{tr}(X)\leq \sqrt{n} $ puede representarse como $ 1 \leq \langle P_0 , W \rangle \leq \sqrt{n}, $ y el objetivo de problema de mi pregunta se puede escribir como $\langle P, W\rangle $ donde $P_i,P_0, P\in S^{5n\times 5n}$ vienen dadas por : $$ P_i = \left[ \begin{array}{cc} A_i & 0\\ 0& 0 \\ \end{array} \right], ~ P_0 = \left(\begin{array}{cc} I & 0 \\ 0 & 0 \end{array} \right), ~ P= \left(\begin{array}{ccc} 0 & & \\ & \left(\begin{array} {cc} 0 & \\ & \frac{1}{\eta} I \end{array} \right) & \\ & & \left(\begin{array}{cc} I & \\ & 0 \end{array} \right) \end{array} \right), $$ Así, El problema de mi pregunta se puede escribir como el siguiente problema SDP: $$ \begin{eqnarray} & \min & \left\langle P, W \right\rangle \\ & \textrm{s.t.} & \langle E^{(i, ~n+j)}, W \rangle =0, ~~i = 1, ..., n, j=1,..., 4n, \\ & & \langle E^{(n+i, ~3n+j)}, W \rangle =0, ~~i,j = 1, ..., 2n, \\ & & \langle E^{(n+i, ~n+j)}, W \rangle = 0, ~ i=1, ..., n-1, ~j=i+1, ..., n, \\ & & \langle E^{(n+i, ~n+i)}, W \rangle = 1, ~ i=1, ..., n, \\ & & \langle E^{(i,j)}-E^{(n+i, ~2n+j)}, W \rangle =0, ~i=1,..., n-1, ~j=i+1, ..., n, \\ & & \langle E^{(j,i)}-E^{(n+j, ~2n+i)}, W \rangle =0, ~i=1,..., n-1, ~j=i+1, ..., n, \\ & & \langle 2 E^{(i,i)}-E^{(n+i, ~2n+i)}, W \rangle =0, ~~ i =1, ..., n, \\ & & \langle E^{(n+i,2n+j)}-E^{(3n+i, ~4n+j)}, W \rangle =0, ~~ i,j=1, ..., n, \\ & & \langle E^{(4n+i, ~4n+j)}- E^{(2n+i, ~2n+j)}, W \rangle =0, ~~i=1,..., n-1,~ j =i+1, ..., n , \\ & & \langle E^{(4n+i, ~4n+i)}- E^{(2n+i, ~2n+i)}, W \rangle =\varepsilon, ~~i=1, ..., n , \\ & & \left\langle P_i, W \right\rangle = 0, ~~ i=1, ..., m, \\ & & 1 \leq \langle P_0 , W \rangle \leq \sqrt{n}, \\ & & W \succeq 0 \end{eqnarray} $$ que es de la forma ( $P'$ ). Así, su problema dual viene dado por : \begin{eqnarray*} & \max & \sum_{i=1}^n \alpha_i+ \sum_{i=1}^n \varepsilon \beta_i + t_1+ \sqrt{n} t_2 \nonumber \\ & \textrm{s.t.}& \nonumber \\ & & \sum_{i=1}^n\sum_{j=1}^{4n} \rho_{ij} E^{(i, n+j)} + \sum_{i,j=1}^{2n} \rho'_{ij} E^{(n+i, 3n+j)} + \sum_{i=1}^{n-1}\sum_{ j=i+1 }^n \rho''_{ij} E^{(n+i, n+j)} \nonumber \\ & & + \sum_{i=1}^n \alpha_i E^{(n+i, n+i)} + \sum_{i=1}^{n-1}\sum_{ j=i+1 }^n \left[ \xi_{ij} (E^{(i,j)}-E^{(n+i, 2n+j)}) + \xi'_{ij} (E^{(j,i)}-E^{(n+j, 2n+i)}) \right] \\ & & + \sum_{i=1}^{n} \eta_{i} (2E^{(i,i)}-E^{(n+i, 2n+i)}) + \sum_{i,j=1 }^{n} \theta_{ij} (E^{(n+i,2n+j)}-E^{(3n+i, 4n+j)}) \nonumber\\ & & + \sum_{ i=1}^{n-1}\sum_{ j=i+1 }^{n} \theta'_{ij} (E^{(4n+i, 4n+j)}- E^{(2n+i,2n+j)}) + \sum_{i=1 }^{n} \beta_i (E^{(4n+i, 4n+i)}- E^{(2n+i,2n+i)}) \nonumber\\ & & + \sum_{i=1}^m y_i P_i +t_1 P_0+t_2 P_0 \preceq P, \nonumber\\ & & t_1\geq 0, ~ t_2\leq 0. \nonumber \end{eqnarray*}

Por la estructura de $ P, P_0 , E^{(\cdot,\cdot)}$ 's y $P_i$ el problema anterior puede escribirse como \begin{eqnarray} & ~~~\max & \sum_{i=1}^n \alpha_i+ \sum_{i=1}^n \varepsilon \beta_i + t_1+\sqrt{n} t_2 ~~\left( = \textrm{tr}(\Phi) -\varepsilon \textrm{tr}(Q) + t_1+\sqrt{n} t_2\right) \nonumber \\ &\textrm{ s.t.}& \nonumber \\ & & \left( \begin{array}{ccccc} V+V^T +\sum_{i=1}^m y_i A_i+(t_1+t_2)I & U_1 & U_2 & U_3 & U_4 \\ U_1^T & \Phi & \Theta-V & U_5 & U_6 \\ U_2^T & \Theta^T-V^T & Q-\frac{1}{\eta}I & U_7 & U_8 \\ U_3^T & U_5^T & U_7^T & -I & -\Theta \\ U_4^T & U_6^T & U_8^T & -\Theta^T & -Q \\ \end{array} \ right) \preceq 0, \\\ ~ t_1\geq 0, ~ t_2\leq 0, \ ~nonumber & & t_1\geq 0, ~ t_2\leq 0, \number \N - fin{eqnarray}

donde $\alpha_i$ y $-\beta_i$ son las entradas diagonales de $\Phi$ y $Q$ respectivamente.

Espero que disfrutes leyendo la respuesta, personalmente fue muy agradable leer este artículo de Zhao.