Consider the following optimization problem:
$\max_{\lambda_j(X)}\sum_{j=1}^n d_j\lambda_j(X)$ subject to $v_j^TXv_j \leq 1, X \geq 0$.
$d_j$ are such that $d_1 \geq d_2 \geq \ldots \geq d_k > 0$, $\lambda_j(X)$ is the $j$th largest eigenvalue of the positive semidefinite matrix $X$ of dimension $n\times n$. $v_j$ are vectors with elements belonging to $\{-1,0,1\}$. $T$ denotes transpose. All variables are real-valued.
Are there any theoretical results about the optimal matrix $X$ for this problem?
We know that the objective function is a convex function on the elements of $X$, so this is about maximizing a convex function over the convex set that is defined by intersecting the positive semidefinite cone with some hyperplanes. I have noticed that the optimal solution is either at the vertices of the polyhedron defined by the linear inequalites (which is then full rank), or at lower rank matrices obtained by intersecting some of the planes with the surface of the semidefinite cone (the intersection is such that these low rank matrices are uniquely defined from the hyperplanes). So basically, the low rank solution is obtained by intersecting a line, obtained from the hyperplanes, and the cone.
Grateful for any hints or references.
Best Answer
If I understand the question correctly, the answer is that no, optima need not occur at a unique point where some of the hyperplanes defined by tightness of the linear inequalities meet the boundary of the positive semidefinite cone.
For example, let $v_i$ be the $i^{\text{th}}$ unit vector, so the linear constraints merely say that the diagonal entries of $X$ are each at most $1$. You can check that there are many positive semidefinite matrices with all diagonal entries equal to $1$.
Since the diagonal entries are each at most $1$, the trace of $X$ is at most $n$. Since $X$ is positive semidefinite its eigenvalues are nonnegative. Thus for any $k$, the sum of the $k$ largest eigenvalues of $X$ is at most $n$. This bound is achieved simultaneously for all $k$ by the all ones matrix, so this matrix is optimal for any $k$. The matrix whose $i,j$ entry is $(-1)^{i+j}$ also achieves this bound, giving another optimal solution.
Asking that the matrices $v_jv_j^T$ span the space of symmetric matrices does not rule out this counterexample. It suffices to add some more such matrices with right hand side constants $c_j$ very large, so the corresponding linear constraints can never be tight (without violating the other constraints).