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, 2013 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, 2013 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, 2013 at 19:41
  • $\begingroup$ @IgorRivin : I have edited and explained in more details. $\endgroup$
    – Royeh
    Oct 18, 2013 at 16:36

1 Answer 1


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, 2013 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, 2013 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, 2013 at 18:20

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.