proving this inequality related to conjugate functions 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? 
 A: $[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
$$
A: 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.
