# 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?

-
I would purpose writing out $y^Tx$ and then shift the coefficients of the $x_i$ towards the $x_{[i]}$ by inequalities until you get to $f(x)$. – mkl Jan 27 '13 at 15:43

$[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$$

-
I didn't understand your first line. Does $x_{[i]}$ stand for the $i$ th largest element of $x$ according to your definition? – neticin Jan 27 '13 at 19:49
@neticin: yes. As in the question, $x_{[i]}$ represents the the $i^{\text{th}}$ largest of the $x$s. $[i]$ is a permutation on the indices, although not unique if some of the $x$s are equal. In any case, we can pick a permutation. Is this making sense? – robjohn Jan 27 '13 at 19:55
Ok. But how could you write $y^Tx = \sum_{i=1}^n y_{[i]} x_{[i]}$? The $i$th largest $y$ does not have to correspond the $i$ th largest $x$. – neticin Jan 27 '13 at 19:58
@neticin: $y_{[i]}$ is not the $i^{\text{th}}$ largest $y$. The permutation $[i]$ is based on the sizes of the $x$s. Thus, $$\sum_{i=1}^ny_{[i]}x_{[i]}=\sum_{i=1}^ny_ix_i$$ – robjohn Jan 27 '13 at 20:02
Ok, now I got it. Thanks for the explanation – neticin Jan 27 '13 at 20:06

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.

-