There is a great work of Alizadeh that in section 4 speaks about Minimizing sum of the first few(k-largest) eigenvalues of a symmetric matrix. Instead of a symmetric model we use the weighted Laplacian $(L_c(G) = \displaystyle \sum_{ij \in E} c_{ij}E_{ij})$of graph $G = (N, E)$. Then the dual problem is the following model:

\begin{equation*} \begin{array}{llll} \min & k z + {\rm trace~}V \\ \rm{s.t.} & Iz + V - \sum_{ij \in E} c_{ij}E_{ij} \succeq 0 , \\ % U & \sum_{ij \in E} c_{ij} = 1 ,\\ % V & c \geq 0, ~ V \succeq 0 . \end{array} \end{equation*}

Again, we write the dual of the above model to obtain this model:

\begin{equation*} \begin{array}{llll} \max & x\\ \rm{s.t.} & {\rm trace~} Y = k, \\ & x \leq \langle E_{ij}, Y \rangle ~~~~ \textrm{for } ij \in E,\\ & 0 \preceq Y \preceq I. \end{array} \end{equation*}

Because $Y$ is a positive semidefinite matrix, i.e., $Y \succeq 0$, one property of such a matrices allows us to use the Gram representation: $Y = V^T V$ with $V \in \mathbb{R}^{n \times n}$. If $v_i$ denotes the $i$-th column of $V$ then how can one write condition $Y \preceq I$ in terms of $v_i$ which $I$ is identity matrix with all diagonal entries equal to $1$?

For example the gram representation of first constraint is: $${\rm trace~} Y = \sum_{i \in N} \| v_i \|^2 = k$$

  • $\begingroup$ Where does this question come from? It looks like homework to me. $\endgroup$ – Igor Rivin Oct 17 '13 at 17:27
  • $\begingroup$ @IgorRivin this is a part of an sdp optimization model and I could not figure out this constraint. It is from Alizadeh's paper(famous work) in sdp. $\endgroup$ – Royeh Oct 17 '13 at 19:08
  • 1
    $\begingroup$ OK, fair enough. You might want to put the "back story" in the question in the future... $\endgroup$ – Igor Rivin Oct 17 '13 at 19:41
  • $\begingroup$ @IgorRivin : I have edited and explained in more details. $\endgroup$ – Royeh Oct 18 '13 at 16:36

Probably you are looking for the following (Schur-complements lemma):

\begin{equation*} V^TV = Y \preceq I,\quad\leftrightarrow\quad \begin{bmatrix} I & V^T\\ V & I \end{bmatrix} \succeq 0. \end{equation*}

  • $\begingroup$ @suvrit: Now, do you think with new explanation your suggestion will work? $\endgroup$ – Royeh Oct 18 '13 at 16:39
  • $\begingroup$ I don't really understand what you're getting at. I could write your constraint as $\|V^TV\| \le 1$, which is a difficult nonlinear constraint, which you can then write it terms of singular values of $V$, but one doesn't gain much by that... $\endgroup$ – Suvrit Oct 18 '13 at 18:03
  • $\begingroup$ I want to have an embedding model in terms of column of $V$, i.e. $v_i$'s. $\endgroup$ – Royeh Oct 18 '13 at 18:20

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.

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