Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
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
1  
@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
show 1 more comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.