I have a block matrix $F$ of dimension $mn\times mn$: $$F=\begin{pmatrix}F_{11}& F_{12}&\cdots\\F_{21}&\cdots&\cdots\\\cdots&\cdots&F_{mm} \end{pmatrix}$$ where each block $F_{ij}$ is $n\times n$. I want to maximize over $\mathbf{x}\in \mathbb{C}^m$ the sum of the $k$ largest modules of the eigenvalues of the $n\times n$ matrix $T=\sum_{ij} x_i^*x_j F_{ij}$ (note that if we think in blocks, $T=\mathbf{x}^\dagger F\mathbf{x}$):

$$\max_\mathbf{x}\sum_{l=1}^k|\lambda_l(T)|\\s.t. ||\mathbf{x}||_2=1$$

Where can I go from here? The objective is convex... If it can help, I'm okay with relaxing the objective to $\sum_{ij}X_{ij}F_{ij}$, with $X$ positive semidefinite and $\mathrm{Tr}(X)=1$.

EDIT (What I've tried so far):

As the eigenvalues of $T$ are either real or they come in conjugate pairs, I can't use lambda_sum_largest in CVX, because it complains that it doesn't know how to order them.

But the objective can be rewritten as a partial trace: $\max_X \sum_{j=1}^k\lambda_j\bigl[Tr_A(F_{AB}\, X_A\otimes 1_B)\bigr]$, which in turn is the same as $\max_{S\in\Omega}||Tr(F_{AB}\,1_A\otimes S_B)||_\infty$ where $\Omega=\{S: S=S^\dagger, 0\leq S\leq 1, Tr(S)=k\}$ is the convex hull of the set of rank-$k$ projectors. The issue is now that the matrix $Tr(F_{AB}\,1_A\otimes S_B)$ is not hermitian, so functions like lambda_max in CVX will still complain, even if the value they should compute is now positive.

  • $\begingroup$ What is the domain of $\mathbf x$? Is it $\mathbb R^n$, $\mathbb R^{mn}$, maybe $\mathbb C^n$? It's not obvious from your question. $\endgroup$ – Rahul Dec 9 '16 at 19:45
  • $\begingroup$ Corrected, it's in $\mathbb{C}^ m$. Thanks! $\endgroup$ – Ziofil Dec 9 '16 at 20:15
  • $\begingroup$ Although, one can always represent complex numbers with 2x2 real matrices $\left(\begin{smallmatrix}R&-I\\I&R\end{smallmatrix}\right)$, so it's equivalent to think of even dimensions and all real numbers, with that 2x2 structure. $\endgroup$ – Ziofil Dec 12 '16 at 15:37

Your Answer

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

Browse other questions tagged or ask your own question.