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.

  • $\begingroup$ what is $k$...? $\endgroup$ – Suvrit Oct 23 '11 at 9:18
  • $\begingroup$ I edited my post now, so you see that $k$ is $1 \leq k < n$. $\endgroup$ – Kap Oct 23 '11 at 9:46
  • $\begingroup$ Do you know anything about how many constraint vectors $v_j$ there are? For example, more than $k$? Less than or equal to $k$? Something else? $\endgroup$ – cardinal Oct 23 '11 at 21:06
  • $\begingroup$ Yes you can assume there are more than $k$ independent constraint vectors. $\endgroup$ – Kap Oct 23 '11 at 22:26
  • $\begingroup$ Could you clarify a bit what your question is? Let's say the feasible reason is compact so an optimum exists. Then there will be one at an extreme point $X$ of the feasible region. Of course, if $X$ is not extreme for the polyhedron defined by dropping the semidefiniteness constraint, then $X$ cannot be positive definite, so it lies on the boundary of the positive semidefinite cone. Also, why do you say the intersections between some of the hyperplanes and the semidefinite cone are unique? $\endgroup$ – Noah Stein Oct 24 '11 at 14:35

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).

  • $\begingroup$ The place where spanning does come in with respect to the constraints is that the problem is bounded if and only if the $v_j$ span $\mathbb{R}^n$. This doesn't seem particularly relevant to your question but I can add a proof if you'd like, or you can ask it separately. $\endgroup$ – Noah Stein Oct 24 '11 at 23:17
  • $\begingroup$ Thank you very much for your answer Noah. But let's say I have all $c_j = 1$ and vectors $v_j$ such that each of their element can be $-1,0,1$, so that there are $3^n - 1$ vectors in total (the all zero vector is not included). Then the matrices you presented don't satisfy the constraints. So you think it is still possible to find other low rank matrix solutions that are not defined uniquely from our planes? $\endgroup$ – Kap Oct 25 '11 at 10:51
  • $\begingroup$ Also, note that the matrices you wrote have integer entries (because you assumed integer vectors and constants), which I think should hold for the optimal matrix. I can explain why $X$ should have integer entries if the solution is full rank, because then it satisfies a set of integer equations. But for the lower rank, I'm not completely sure. $\endgroup$ – Kap Oct 25 '11 at 12:28
  • $\begingroup$ Are you only interested in those particular values of $c_j$ and $v_j$? I haven't thought about them in particular, only the general case which you originally asked about. Also, why do you expect the optimal solution should be integral? It is helpful to include such additional conditions and preliminary results in the statement of the question when possible. $\endgroup$ – Noah Stein Oct 25 '11 at 13:10
  • $\begingroup$ Yes you're right, I have changed the description now. As you see, for some $d_j$, I can prove the optimal $X$ should have rational entries (so it's integer up to a scaling), because the optimum is then at the vertices of the hyperplanes. I suspect the same structure holds even for lower rank $X$. $\endgroup$ – Kap Oct 25 '11 at 13:48

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.