4
$\begingroup$

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?

$\endgroup$

2 Answers 2

9
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ How is this the pointwise supremum rather than partial maximization over V? Aren’t we choosing just one best V, sort of optimizing it out, so the function remaining is only in A? I ask because pointwise maximization preserves convexity, but partial maximization instead preserves concavity. $\endgroup$ Commented Mar 5 at 6:09
0
$\begingroup$

cvxpy treats that function as being concave (link).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.