Convexity of a sum

Question

I am revisiting a book and came across the following problem:

---

Let $$\begin{align*} f(\boldsymbol{x}) = \sum_{i=1}^{r} |x|_{[i]} \end{align*}$$ where $\vert x \vert_{[i]}$ is the $i$ th largest component of $|x_1|, \cdots, |x_n|$. Is $f$ convex?

---

I have been attempting to do this for hours using the second-order condition of convexity ($\nabla^2 f(x) \ge 0$) as well as trying to approach it as a set and prove the convexity of a set.

The fact it is a sum is completely throwing me off. Would appreciate some help with this. Thank you.

Answer 1

The function is not differentiable, so going the Hessian route is probably not a fruitful approach.

Let $S$ be the set of $n$ dimensional vectors with $\pm 1$ in $r$ places and zero elsewhere.

Note that $f(x) = \max_{s \in S} s^T x$ and the $\max$ of a finite number of convex functions is convex.

Establishing equality is straightforward. Show that $f(x) \ge s^T x$ for any $s\in S$ and then show that for any $x$ there must be some $s \in S$ that achieves equality.

Elaboration:

To establish the equality $f(x) = \max_{s \in S} s^T x$ , first pick any $s \in S$. Note that $s$ is zero except for $r$ entries that are $\pm 1$.

Since $f(x)$ is the sum of the largest $r$ components of $x$ we must have $f(x) \ge s^T x$ (remember that $|x_k| \ge \pm x_k$).

To show equality, let $i_1,...,i_r$ be the indices of the $r$ largest elements of $|x|$, and let $s = \sum_{k=1}^r (\operatorname{sgn} x_{i_k}) e_{i_k}$. Note that $s \in S$ and $s^T x = \sum_{k=1}^r | x_{i_k} | = f(x)$.