Karamata不等式是凸优化中重要的不等式，它推广了离散的Jensen不等式，还可进一步推广得到Shur凸函数的概念.
Theorem 1. 假设$I$是实数轴上的一个区间。若$\left\{ x_i \right\}_{i=1}^n$以及$\left\{ y_i \right\}_{i=1}^n$都是$I$上的实数序列，满足:
- $x_1\geq x_2\geq \cdots\geq x_n$以及$y_1\geq y_2\geq\cdots\geq y_n$;
- $\sum_{i=1}^kx_i\geq\sum_{i=1}^ky_i$, 对任意的$k=1,2,\ldots, n$都成立;
- $\sum_{i=1}^nx_i=\sum_{i=1}^ny_i$.
若$f:I\to \mathbb{R}$是一个凸函数。即，$f(\lambda x+(1-\lambda)y)\leq \lambda f(x)+(1-\lambda)f(y)$，对任意的$x,y\in I$都成立。则，对$\left\{ x_i \right\}_{i=1}^n\succ \left\{ y_{i} \right\}_{i=1}^n$, 有
\[
f(x_1)+\cdots+f(x_n)\geq f(y_1)+\cdots+f(y_n).
\]
我们首先给出凸函数的一个重要性质：
Lemma 2. 假设$f:I\to \mathbb{R}$是凸函数，若定义$\Gamma(x,y):=\frac{f(y)-f(x)}{y-x}$, 则对任意的$x,x_1,x_2\in I$, $x_1\leq x_2$, 有$\Gamma(x_1,x)\leq \Gamma(x_2,x)$.
Proof . 只需分类讨论。例如，当$x_1\leq x\leq x_2$时，我们有$x=\lambda x_1+(1-\lambda)x_2$, 从而$\lambda=\frac{x-x_2}{x_1-x_2}$, $1-\lambda=\frac{x_1-x}{x_1-x_2}$. 利用凸函数的定义，我们得到
\[
\lambda f(x)+(1-\lambda)f(x)=f(x)\leq \lambda f(x_1)+(1-\lambda)f(x_2),
\]
即
\[
\lambda \left( f(x)-f(x_1) \right)\leq(1-\lambda)(f(x_2)-f(x)),
\]
代入$\lambda$以及$1-\lambda$, 整理即得结论。
\[
\lambda f(x)+(1-\lambda)f(x)=f(x)\leq \lambda f(x_1)+(1-\lambda)f(x_2),
\]
即
\[
\lambda \left( f(x)-f(x_1) \right)\leq(1-\lambda)(f(x_2)-f(x)),
\]
代入$\lambda$以及$1-\lambda$, 整理即得结论。
现在，我们来证明定理。为此，令$c_i=\Gamma(x_i,y_i)$, 并令$A_i:=\sum_{j=1}^ix_i$, $A_0=0$以及$B_i:=\sum_{j=1}^iy_i$, $B_0=0$. 则根据引理，并注意到$x_{i+1}\leq x_i$, $y_{i+1}\leq y_i$, 我们得到
\[
c_{i+1}=\Gamma(x_{i+1},y_{i+1})\leq \Gamma(x_i,y_{i+1})=\Gamma(y_{i+1},x_i)\leq\Gamma(y_i,x_i)=c_i.
\]
从而
\begin{align*}
\sum_{i=1}^nf(x_i)-\sum_{i=1}^nf(y_i)&=\sum_{i=1}^n \left( f(x_i)-f(y_i) \right)=\sum_{i=1}^nc_i(x_i-y_i)\\
&=\sum_{i=1}^nc_i\left( A_i-A_{i-1}-B_i+B_{i-1} \right)\\
&=\sum_{i=1}^nc_i(A_i-B_i)-\sum_{i=0}^{n-1}c_{i+1}(A_i-B_i)\\
&=A_n-B_n+\sum_{i=1}^{n-1}(c_i-c_{i+1})(A_i-B_i)-c_1(A_0-B_0)\\
&=\sum_{i=1}^{n-1}(c_i-c_{i+1})(A_i-B_i)\geq0.
\end{align*}
作为应用，我们考察如下
Example 1. 证明不等式
\[
(x+y)^p\geq x^p+y^p,\quad p\geq1, x,y\geq0.
\]
\[
(x+y)^p\geq x^p+y^p,\quad p\geq1, x,y\geq0.
\]
Proof . 考察$I=[0,+\infty)$上到凸函数$f(t)=t^p$, $p\geq1$. 注意到$(1,0)\succ \left( \frac{x}{x+y},\frac{y}{x+y} \right)$, 由Karamata不等式得到
\[
f(1)+f(0)\geq f\left( \frac{x}{x+y} \right)+f\left( \frac{y}{x+y} \right),
\]
即
\[
1\geq\left( \frac{x}{x+y} \right)^p+\left( \frac{y}{x+y} \right)^p.
\]
变形即得
\[
(x+y)^p\geq x^p+y^p.
\]
\[
f(1)+f(0)\geq f\left( \frac{x}{x+y} \right)+f\left( \frac{y}{x+y} \right),
\]
即
\[
1\geq\left( \frac{x}{x+y} \right)^p+\left( \frac{y}{x+y} \right)^p.
\]
变形即得
\[
(x+y)^p\geq x^p+y^p.
\]