The sum of the k smallest components of a vector is a concave function
I came across this statement but have been unable to convince myself why it's true. I've been going at it from the definition of concavity:
$f(\theta a + (1 - \theta)b) \ge \theta f(a) + (1-\theta) f(b)$.
Can someone help me find a proof of this? Thanks!
Update
Thanks for the feedback - in the equation above, I'm using the following definitions:
- $a, b \in {\rm I\!R}^n$
- $0 \le \theta \le 1$
- $f(x) = \sum_{i}^k x_{[i]}, x \in {\rm I\!R}^n$, where $x_{[i]}$ denotes the ith smallest entry of x
I found what I was looking for in Boyd and Vandenberghe, pp. 80, Ex. 3.6 "Sum of r largest components". The sum of a k specific components of a vector is a linear function. For example, the sum of the first two components would be:
$\sum_{i=0}^1 x_i = a^Tx$ where $a^T = \begin{matrix} [1&1&0&0&\ldots & 0]\end{matrix}$
The set of all possible sums of k components is thus a finite set of linear functions. The sum of the largest components is the pointwise supremum of this set. The Pointwise supremum $\sup_k {f_k(x)}$ preserves convexity if $f_k$ is convex for all k, thus the sum of the k largest components of a vector is convex.
To extend this proof for the k smallest components, simply negate the vector.