0
$\begingroup$

Let $\Lambda_1,\Lambda_2$ be $n\times n$ diagonal matrices with diagonal elements positive and decreasing (i.e., $\Lambda_{j,11}>\Lambda_{j,22}\ldots>\Lambda_{j,nn}>0$ for $j\in\{1,2\}$). Let $\{a_i\}$ be another decreasing sequence of positive numbers. I want to find the orthonormal matrix $U$ that maximizes $$ \sum_{i=1}^d a_i\cdot \mathrm{eigval}_i(\Lambda_1 U^\top \Lambda_2 U \Lambda_1), $$ where $\mathrm{eigval}_i(\cdot)$ denotes the $i$-th largest eigenvalue of a matrix.

I think the optima should satisfy $U^2 = I$. This would be true if we restricted $U$ to be a permutation matrix, or if $a_i\equiv 1$ held, or if we were doing a greedy optimization of the sum (first choosing the first column $U_{:,1}$ while leaving the other columns to be zero, then choosing $U_{:,2}$ in the orthogonal complement of $\mathrm{span}\{U_{:,1}\}$, etc). But the general form of the problem makes e.g. using the first-order condition difficult. Any help will be appreciated.

$\endgroup$

1 Answer 1

1
$\begingroup$

I find a proof. Define $a_{d+1}:=0$. Then our objective function equals $$ \begin{aligned} \sum_{i=1}^d (a_i-a_{i+1})\sum_{j=1}^i \mathrm{eigval}_j (U^\top \Lambda_2 U \Lambda_1^2) &\le \sum_{i=1}^d (a_i-a_{i+1})\sum_{j=1}^i \mathrm{eigval}_j (U^\top \Lambda_2 U)\; \mathrm{eigval}_j(\Lambda_1^2) \\ &= \sum_{i=1}^d a_i \;\mathrm{eigval}_i(U^\top \Lambda_2 U)\;\mathrm{eigval}_i(\Lambda_1^2), \end{aligned} $$ where we use the property $\mathrm{eigval}_i(AB)=\mathrm{eigval}_i(BA)$ for s.p.d. $A,B$, and the inequality is from this mathoverflow answer. (As the diagonal matrices have positive and decreasing diagonal elements,) equality is attained when $U^2=I$.

It remains to prove these are the only solutions. Another application of the aforementioned inequality yields $$ \text{Objective} \le \sum_{i=1}^{d-1} (a_i-a_d) \;\mathrm{eigval}_i(U^\top \Lambda_2 U)\;\mathrm{eigval}_i(\Lambda_1^2) + a_d \mathrm{Tr}(U^\top \Lambda_2 U \Lambda_1^2). $$ For the trace term to be maximized it must hold that $U^2=I$, and these choices of $U$ attain the equality here. Therefore, they are the only optimas.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .