Convexity of Sum of $k$-smallest Eigenvalue

Question

If I have a real positive definite matrix $A\in\mathbb{R}^{n\times n}$, and denote its eigenvalues as $\lambda_1\leq \lambda_2 \leq ... \leq \lambda_n $.

Define the function as $f(A)=\sum_{i=1}^{k} \lambda_i$ for a constant $k<n$. What do we know about the convexity of $f(A)$? Is it convex or concave?

Answer 1

Given $A \in {\bf S}^n$ (a positive definite matrix) with eigenvalues $\lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n $, then:

1. $\displaystyle f_k(A)=\sum_{i=1}^{k} \lambda_i$ is concave. Why?

   $$f_k(A) = \inf \left\{ {\bf tr}(V^T A V) | V \in {\bf R}^{n \times k}, V^T V = I \right\}$$

   This follows from the Poincare separation theorem (see e.g. Horn and Johnson's Matrix analysis, 2nd ed., corollaries 4.3.37 and 4.3.39). $f_k$ is the pointwise infimum of a family of linear functions ${\bf tr}(V^T A V)$, hence it is concave (Boyd and Vandenberghe, section 3.2.3).

2. $\displaystyle g_k(A)=\sum_{i=n-k+1}^{n} \lambda_i$ is convex. Again, we can show that

   $$g_k(A)=\sum_{i=n-k+1}^{n} \lambda_i(A) = \sup \left\{ {\bf tr}(V^T A V) | V \in {\bf R}^{n \times k}, V^T V = I \right\}$$

   $g_k$ is the pointwise supremum of a family of linear functions ${\bf tr}(V^T A V)$, hence it is convex (Boyd and Vandenberghe, section 3.2.3).

Answer 2

cvxpy treats that function as being concave (link).