proving this inequality related to conjugate functions

Question

For $x \in \mathbb{R}^n$ let us denote $x_{[i]}$ the $i$th largest component of $x$ s.t $$ x_{[1]} \geq x_{[2]} \geq x_{[3]}\ge\cdots $$ The function $$ f(x)= \sum_{i=1}^r x_{[i]} $$ is the sum of $r$ largest element of $x$. Here I want to show that for each $x \in \mathbb{R}^n$ $$ y^Tx \leq f(x) $$ for $y \in \mathbb{R}^n$ which satisfies $$ 0 \leq y_i \leq 1 \hspace{2mm}\forall i=1,2,\ldots,n \\ \sum_{i=1}^n y_i = r $$

So, I tried using Lagrange multipliers but I could not take the derivative of $f(x)$. So how can I show this inequality subject to these constraints?

Answer 1

$[i]$ is a permutation of $(1,2,3,\dots,n)$ so that $x_{[i]}\ge x_{[i+1]}$. Therefore, $$ \begin{align} f(x)-y^Tx &=\sum_{i=1}^rx_{[i]}-\sum_{i=1}^ny_{[i]}x_{[i]}\\ &=\sum_{i=1}^r\left(x_{[i]}-y_{[i]}x_{[i]}\right) +\sum_{i=r+1}^n\left(0-y_{[i]}x_{[i]}\right)\\ &=\sum_{i=1}^rx_{[i]}\left(1-y_{[i]}\right) -\sum_{i=r+1}^nx_{[i]}\left(y_{[i]}\right)\\ &=\sum_{i=1}^r\color{#00A000}{\left(x_{[i]}-x_{[r]}\right)}\color{#0000FF}{\left(1-y_{[i]}\right)} -\sum_{i=r+1}^n\color{#C00000}{\left(x_{[i]}-x_{[r]}\right)}\color{#0000FF}{\left(y_{[i]}\right)}\\[6pt] &\ge0 \end{align} $$ since every term in the left sum is $\color{#00A000}{\ge0}$ and every term in the right sum is $\color{#C00000}{\le0}$.

We can subtract $x_{[r]}$ from each term in both sums since $$ \sum_{i=1}^r\color{#0000FF}{\left(1-y_{[i]}\right)} -\sum_{i=r+1}^n\color{#0000FF}{\left(y_{[i]}\right)} =r-\sum_{i=1}^ny_{[i]}=0 $$

Answer 2

Assume wlog that $ x_1 \geq x_2 \geq \dots \geq x_n $.

Consider first the special case where the $x_i$'s are pairwise distinct, i.e., $ x_1 > x_2 > \dots > x_n .$

The set $$ S = \{ (y_1,y_2,\dots,y_n) : y_i \in [0,1], \sum y_i = r \}$$ is compact, and hence there is a $y=(y_1,y_2,\dots,y_n) \in S$ with $ y^Tx = \sup_{w \in S} w^Tx$.

We shall show at this point $y_i = 1$ for $ 1 \leq i \leq r $.

For if $0 \leq y_j < 1$, for some $ 1 \leq j \leq r $, then $\sum_{i=1}^r y_i < r$ and $ \sum_{i=r+1}^{n} y_i = r - \sum_{i=1}^r y_i > 0$. So there exists a $k$, $ r+1 \leq k \leq n$, with $y_k > 0$. Choosing $ \epsilon > 0$ such that $ y_j + \epsilon \leq 1$ and $ y_k - \epsilon \geq 0$, and letting $z = (y_1, \dots, y_{j-1},y_{j}+\epsilon, y_{j+1}, \dots , y_k - \epsilon , \dots , y_n )$, we have $z \in S$ and $z^{T}x - y^Tx = (x_j - x_k ) \epsilon > 0.$ This contradicts the maximality of $y$ and leads to the conclusion that at any maximum $y_1 = y_2 = \dots = y_r = 1$ and such a point in $S$ is unique. Hence the result holds for $x$ with pairwise distinct elements, that is for such $x$, $\sup_{w \in S} w^Tx = \sum_{i=1}^{r} x_i$.

Now relax the pairwise distinct assumption and given any $x = (x_1,x_2, \dots, x_n)$ with $x_1 \geq x_2 \dots \geq x_n$ let, $x^{k} = (x_1, x_2 - \frac{1}{k}, x_3 - \frac{2}{k} , \dots , x_{n} - \frac{n-1}{k} )$, the coordinates of $x^{k}$ are pairwise distinct and $x^k \to x$ as $k \to \infty$, and $x_1^k > x_2^k > \dots > x_n^k$. From our previous results we have for any $y \in S$, $$ y^Tx^k \leq \sum_{i=1}^{r} x_i^k,$$ letting $k \to \infty$ we are done.