6
$\begingroup$

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;

$\endgroup$
  • 3
    $\begingroup$ Translating to standard form is most certainly not the first step to finding the dual. In fact, you will get the wrong dual if you do so. Yes, it will be "equivalent" in some sense, but it will not be straightforward to map the dual variables you obtain back to the original problem. Instead, you should attach an appropriate Lagrange multiplier to each constraint, and differentiate with respect to each primal variable to find the implicit dual equality constraints. $\endgroup$ – Michael Grant Mar 23 '14 at 1:39
  • 2
    $\begingroup$ I'll be honest: I considered answering this question in full, but I soon gave up. Truth is, it is quite a complex process; not difficult, per se, but tedious and error-prone. Still better than trying to convert to standard form and then taking the dual, but still a real bear. In particular, you have to break up the Lagrange multipliers for those $2\times 2$ LMIs into blocks themselves. I commend anyone else willing to slog through it for you but I am not optimistic. $\endgroup$ – Michael Grant Mar 23 '14 at 1:41
  • $\begingroup$ @Michael C. Grant thank you very much Michael, I will try to do so. I wont to ask you a recommendation of any source of, practical calculus of duality of "complicated" or non-standard cases like this. $\endgroup$ – Aymane Fihadi Mar 23 '14 at 11:38
  • $\begingroup$ Well, perhaps "Optimization by Vector Space Methods" by Luenberger. $\endgroup$ – Michael Grant Mar 23 '14 at 16:34
  • $\begingroup$ Thank you Michael, I took my time browsing through It, it seem really nice and familiar, maybe because I know some of the subjects treated ( like linear algebra, Banach and Hilbert space, convexity and semi-continuity), but there are not solution to the problems :) where I look for self-studying books. It will be helpful if you tell me any remarkable book for you in that way. $\endgroup$ – Aymane Fihadi Mar 24 '14 at 11:08
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you very much for the answer Aymane. I have one question: why do we have i=1,...,n-1 in conditions (5) and (6) instead of i=1,...,n please? In condition (5) for example, this means j= 2,...,n?, I think. Why please? Thanks. $\endgroup$ – G. Trav Sep 7 '17 at 14:56
  • $\begingroup$ @G.Trav You are welcome! Considering that this is a few years ago, I am not sure I can provide very reliable clarifications. But reading quickly, the (5) equation provide the information that the strictly upper and lower triangular positions of the block matrix (1,1) are equal to the strictly upper triangular positions of the block matrix (2,3) and the strictly lower positions of the (3,2) block. Because we want the strictly upper and lower positions, with the diagonal discarded, this is why we have the $n-1$ instead of $n$ and $i+1$ instead of $i$ respectively. $\endgroup$ – Aymane Fihadi Sep 7 '17 at 16:46
  • $\begingroup$ The same logic is used in the equation (6). The diagonal positions are described by the equations (7) and (8). Feel free to ask if something still not clear, I will try to provide an answer if/when I can. $\endgroup$ – Aymane Fihadi Sep 7 '17 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.