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.

3more comments