Generalized rearrangement inequality Suppose that $f$ is a convex function and  $\{x_i\}_{i=1}^n$ and $\{y_i\}_{i=1}^n$ are real numbers such that $x_1\leq x_2\leq \dots \leq x_n$ and $y_1\leq y_2\leq \dots \leq y_n$. Let $\{u_i\}_{i=1}^n$ be any permutation of $y_i$'s. Then $$f(x_1+y_n)+f(x_2+y_{n-1})+\dots+f(x_n+y_1)\leq f(x_1+u_1)+f(x_2+u_{2})+\dots+f(x_n+u_n)\leq $$ $$\leq f(x_1+y_1)+f(x_2+y_2)+\dots+f(x_n+y_n).$$
In my book it is called as Generalized rearrangement inequality. I do know the regular rearrangement inequality and its proof.
I have no ideas how to prove the above inequality and how the regular one follows from it?
Would be very grateful for help!
 A: One can proceed similarly as in the proof of the “regular” rearrangement inequality: If $\sigma$ is a permutation of $\{1, \ldots ,n\}$ and not the identity then there are indices $j < k$ such that exchanging $\sigma(j)$ and $\sigma(k)$ gives a new permutation $\tau$ with more fixed points than $\sigma$ and
$$ \tag{*}
 \sum_{i=1}^n f(x_i + y_{\sigma(i)}) \le \sum_{i=1}^n f(x_i + y_{\tau(i)}) \, .
$$
If $\tau$ is not the identity then this step can be repeated, and after finitely many steps one obtains
$$
 \sum_{i=1}^n f(x_i + y_{\sigma(i)}) \le \sum_{i=1}^n f(x_i + y_i) \, .
$$
In the case of the “regular” rearrangement inequality one uses that for $a_1 \le a_2$ and $b_1 \le b_2$
$$
 (a_2-a_1)(b_2-b_1) \ge 0 \implies a_1 b_2 + a_2 b_1 \le a_1 b_1 + a_2 b_2 \, .
$$
In our case one can use the following to prove $(*)$:

If $f$ is a convex function and $a_1 \le a_2$ and $b_1 \le b_2$ then
$$
 f(a_1 + b_2) + f(a_2 + b_1) \le f(a_1 + b_1) + f(a_2 + b_2) \, .
$$

This holds trivially if $a_1 =a_2$ or $b_1 = b_2$. In the case $a_1 < a_2$ and $b_1 < b_2$ it follows from adding the convexity conditions:
$$
 f(a_1 + b_2) \le \frac{a_2-a_1}{a_2+b_2-a_1-b_1} f(a_1 + b_1) + \frac{b_2 - b_1}{a_2+b_2-a_1-b_1} f(a_2 + b_2) \\
 f(a_2 + b_1) \le \frac{b_2-b_1}{a_2+b_2-a_1-b_1} f(a_1 + b_1) + \frac{a_2 - a_1}{a_2+b_2-a_1-b_1} f(a_2 + b_2) 
$$

For positive sequences $u_1, \ldots, u_n$ and $v_1, \ldots, v_n$ the normal rearrangement inequality follows from the generalized one with $f(t)=e^t$ applied to $x_i = \log u_i$ and $y_i = \log v_i$, since then
$$
f(x_i + y_{\sigma(i)}) = u_i \cdot v_{\sigma(i)} \ .
$$

It is also a consequence of Karamata's inequality: Set
$$
 (a_1, a_2, \ldots , a_n) = (x_n + y_n, x_{n-1}+y_{n-1}, \ldots, x_1 + y_1)
$$
and let $(b_1, b_2, \ldots , b_n)$ be a decreasing rearrangement of
$$
 (x_n + u_n, x_{n-1}+u_{n-1}, \ldots, x_1 + u_1) \, .
$$
Then
$$
(a_1,a_2,\ldots,a_n)\succ(b_1,b_2,\ldots,b_n)
$$
so that
$$
f(a_1)+f(a_2)+ \ldots +f(a_n) \ge f(b_1)+f(b_1)+ \ldots +f(b_n)
$$
which is the desired conclusion.
