I have a problem with calculating the dual problem of :
$$ \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$$
where ; $X,Y,Z$ are reel symmetric matrices of dimension $n \times n$ , $A_i$ are m given reel symmetric matrices of dimension $n \times n$, $\varepsilon$ and $\eta$ are reel constants, and $\langle A,X\rangle = \sum a_{ij}x_{ij}$
if someone know something tells me please, because my only knowledge of the dual problem is what is in the book of Stephen Boyd and Lieven Vandenberghe, Convex Optimization (chapter 5). but I don't see how I can reformulate this problem to get the standard form of SDP especially when the objective function contain two-variable (Y, Z) where in the standard form it's an $X\succeq 0$. I'm not interested in the standard formulation but I suppose this is the first step to find the dual problem, am I wrong?
thank you;
Let me tell you from where I got this question: It is from a paper written by Yun-Bin Zhao, Approximation Theory of Matrix Rank Minimization and Its Application to Quadratic Equations. In the published version the procedure to get the dual problem is omitted, but, by chance I found it in preprint one :
this is the procedure in detail, the only required information is that :
if we formulat the SDP in the forme : $$ \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} $$ The dual problem is given by : $$ \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} $$
where for any two matrices P and Q, $P \succeq Q$ means $P-Q \succeq 0$.
from that we can easy verify that the dual of (I will note that by $(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} is given by \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} where $b=(b_1, ..., b_l)^T$. ( note that $b^Ty=\langle b, y \rangle_{\mathbb{R}^m}$ :) )
To obtain the dual problem of my question's problem, let us rewrite the problem as the form of (P) . Notice that the positive semidefinite conditions (constraint) in my question problem are equivalent to :
$$ 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 . $$ Let $ E^{(k, l)} \in S^ {5n\times 5n} $ ($k,l=1,..., 5n)$ denote the symmetric matrices with $(k, l)$th entry = $(l, k)$th entry $= 1$ and zero elsewhere. When $k=l$, $ E^{(k, k)} $ denotes the matrix with ($k,k)$th entry 1 and all other elements 0. Clearly, we have $E^{(l,k)}=E^{(k,l)}$ for any $(k,l).$ Note that for any matrix $W=(w_{i,j}) \in S^{5n\times 5n},$ it can be represented as $W=\sum_{k=1}^{5n} \sum_{l=k}^{5n} w_{k,l}E^{(k,l)},$ and $ \langle E^{(k, l)}, W \rangle = w_{k,l}+w_{l,k} = 2w_{k,l}$ for $k\not=l,$ and $ \langle E^{(k, k)}, W \rangle = w_{k,k}. $ In terms of $E^{(\cdot, \cdot)},$ the condition ($W' \succeq 0 $) can be written as the following set of constraints
$$ \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} $$
where (1) and (2) represent the zero blocks in the matrix $W'$, conditions (3) and (4) describe the block $I$ (the $n\times n $ identity matrix), conditions (5) to (8) represent the $X$ blocks, and (9) and (10) describe the relation between the blocks $Z$ and $Z+\varepsilon I$ therein.
In terms of $W\in S^{5n\times 5n},$ the equality $\langle A_i, X\rangle =0$ in my question's problem can be written as $\langle P_i, W\rangle =0, $ the inequality $ 1\leq \textrm{tr}(X)\leq \sqrt{n} $ can be represented as $ 1 \leq \langle P_0 , W \rangle \leq \sqrt{n}, $ and the objective of my question's problem can be written as $\langle P, W\rangle $ where $P_i,P_0, P\in S^{5n\times 5n}$ are given by : $$ 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), $$ Thus, my question's problem can be written as the following SDP problem: $$ \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} $$ which is of the form ($P'$). So, its dual problem is given by : \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*}
By the structure of $ P, P_0 , E^{(\cdot,\cdot)}$'s and $P_i$'s, the above problem can be written as \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 \end{eqnarray}
where $\alpha_i$ and $-\beta_i$ are the diagonal entries of $\Phi$ and $Q$, respectively.
I hop you enjoy reading the answer, Personally it was really enjoyable to read this Zhao's article.