绝对值不等式 | 中位数 | 货仓选址问题

摘要: 绝对值不等式

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 排序不等式 | 微扰法 中，我们介绍了排序不等式，它在由排列顺序决定某些指标的优劣的场合中，可以诱导出贪心算法。比如排队打水问题，要使得所有人的等待之和最小，那么由排序不等式就可以直接知道，按照打水时间从小到大的顺序排队总时间就最小。

本文我们继续看一个非常基础的不等式，即以下绝对值不等式：

$|x - a| + |x - b| \geq |a - b|$，当且仅当 $x$ 在 $a, b$ 之间时取等号。

该不等式与中位数相关，某些优化问题的最优解是在中位数取到，可以通过该不等式出发去推导，比如货仓选址问题。

本文我们首先证明上述不等式，然后通过该不等式证明货仓选址问题中最优解为中位数的正确性。

三角不等式

对于绝对值来讲，最基本的不等式是以下两个，通过绝对值的定义直接得到。

当 $b > 0$ 时，有：

• (1) $|a| < b \Leftrightarrow -b \leq a \leq b$
• (2) $|a| > b \Leftrightarrow a > b$ 或 $a < -b$

同样非常基本，但需要一些推导的是三角不等式，即 $|a + b| \leq |a| + |b|$，当且仅当 $ab \geq 0$，即 $a,b$ 同符号时，等号成立。

在一些抽象的空间，比如向量空间中，三角不等式同样成立，即 $\Vert\mathbf{u} + \mathbf{v}\Vert \leq \Vert\mathbf{u}\Vert + \Vert\mathbf{v}\Vert$，下面仅证明绝对值下的三角不等式。

证明

将两边分别平方：

$$(|a| + |b|)^{2} = a^{2} + b^{2} + 2|a||b|$$ $$|a + b|^{2} = (a + b)^{2} = a^{2} + b^{2} + 2ab$$

而由于 $2ab \leq 2|a||b|$，当且仅当 $a, b$ 同号，即 $ab \geq 0$ 时等号成立。

所以 $|a + b|^{2} \leq (|a| + |b|)^{2}$。另一方面，$|a + b|, |a| + |b|$ 均非负。

所以 $|a+b| \leq |a| + |b|$，当且仅当 $a, b$ 同号，即 $ab \geq 0$ 时等号成立。

$\Box$

一个绝对值不等式

下面我们看本文要讨论的主要不等式，如下：

$|x - a| + |x - b| \geq |a - b|$，当且仅当 $x$ 在 $a, b$ 之间时取等号。

证明

考虑三角不等式 $|s| + |t| \geq |s + t|$，当且仅当 $st \geq 0$ 时取等号。

取 $s = x - a$，$t = b - x$，于是 $s + t = b - a$，代入上述三角不等式，得：

$$|x - a| + |b - x| \geq |b - a|$$

当且仅当 $st = (x - a)(b - x) \geq 0$ 时等号成立。该取等条件等价于 $x$ 在 $a, b$ 之间。

于是得到最终结论：$|x - a| + |x - b| \geq |a - b|$，当且仅当 $x$ 在 $a, b$ 之间时取等号。

$\Box$

中位数最优性证明

有了前面的绝对值不等式，我们可以轻易证明货仓选址问题的最优解为中位数。该问题我们此前我们解决过，参考文章 货仓选址与安排邮筒。

这里我们再描述一下问题，考虑数轴上的 $n$ 个点的集合 $A = \{a_{1}, a_{2}, \cdots, a_{n}\}$，其中 $a_{i}, i=1,2,\cdots,n$ 表示第 $i$ 个点的坐标。在数轴上取一个点 $x$，$A$ 中各点到 $x$ 的距离之和为：

$$f(x) = \sum\limits_{i=1}\limits^{n}|x - a_{i}|$$

则 $x$ 取到 $A$ 中的中位数时，$f(x)$ 取到最小值。

这里中位数的含义是：若 $n$ 为奇数，则中位数为最中间的那个数；若 $n$ 为偶数，则最中间的两个数之间的所有实数均视为中位数。

下面我们通过绝对值不等式证明上述优化问题的结论。

证明

不妨设 $A = \{a_{1}, a_{2}, \cdots, a_{n}\}$ 已经从小到大排序。一对一对地考虑 $f(x) = \sum\limits_{i=1}\limits^{n}|x - a_{i}|$ 中的各个项。

首先考虑最小的 $a_{1}$ 和最大的 $a_{n}$ 对应的项：

$$f(x) = |x - a_{1}| + \sum\limits_{i=2}\limits^{n-1}|x - a_{i}| + |x - a_{n}|$$

由绝对值不等式，有 $|x - a_{1}| + |x - a_{n}| \geq |a_{1} - a_{n}|$，于是有：

$$f(x) \geq \sum\limits_{i=2}\limits^{n-1}|x - a_{i}| + |a_{1} - a_{n}|$$

当且仅当 $a_{1} \leq x \leq a_{n}$ 时取到等号。

接下来考虑次小的 $a_{2}$ 和次大的 $a_{n-1}$ 对应的项：

$$\sum\limits_{i=2}\limits^{n-1}|x - a_{i}| = |x - a_{2}| + \sum\limits_{i=3}\limits^{n-2}|x - a_{i}| + |x - a_{n-1}|$$

由绝对值不等式，有 $|x - a_{2}| + |x - a_{n-1}| \geq |a_{2} - a_{n-1}|$，于是有：

$$\sum\limits_{i=2}\limits^{n-1}|x - a_{i}| \geq \sum\limits_{i=3}\limits^{n-2}|x - a_{i}| + |a_{2} - a_{n-1}|$$

当且仅当 $a_{2} \leq x \leq a_{n-1}$ 时取到等号。

当前不等式是第二个不等式，取等条件 $a_{2} \leq x \leq a_{n-1}$ 隐含了第一个不等式的取等条件 $a_{1} \leq x \leq a_{n}$，因此两个不等式可以合起来，如下：

$$f(x) \geq \sum\limits_{i=3}\limits^{n-2}|x - a_{i}| + |a_{2} - a_{n-1}|$$

当且仅当 $a_{2} \leq x \leq a_{n-1}$ 时取到等号。

以此类推，后续还有若干个不等式，且后面的不等式的取等条件隐含着前面的不等式的取等条件，因此这若干个不等式都可以合起来。

下面我们按照 $n$ 为奇数和偶数分别考虑合起来后的最终情况。

当 $n$ 为奇数：

$$f(x) \geq \sum\limits_{i=1}\limits^{\frac{n-1}{2}}|a_{i} - a_{n + 1 - i}| + |a_{\frac{n+1}{2}} - x|$$

当且仅当 $a_{\frac{n-1}{2}} \leq x \leq a_{\frac{n+3}{2}}$ 时等号成立。另一方面 $|a_{\frac{n+1}{2}} - x| \geq 0$ 当且仅当 $x = a_{\frac{n+1}{2}}$ 时等号成立。

因此 $f(x) \geq \sum\limits_{i=1}\limits^{\frac{n-1}{2}}|a_{i} - a_{n + 1 - i}|$ 当且仅当 $x = a_{\frac{n+1}{2}}$ 时等号成立。

当 $n$ 为偶数：

$$f(x) \geq \sum\limits_{i=1}\limits^{\frac{n}{2}}|a_{i} - a_{n + 1 - i}|$$

当且仅当 $a_{\frac{n}{2}} \leq x \leq a_{\frac{n+2}{2}}$ 时等号成立。

$\Box$

总结

在 衡量分布的中心趋势，均值和中位数汇报哪个更好 中，我们在随机变量上面讨论过类似的问题。结论是在随机变量的均值处，均方误差取到最小；在随机变量的中位数处，平均绝对误差取到最小。

随机变量上定义的中位数，以及平均绝对误差，可以类比到数轴上的中位数定义、以及总距离。因此两篇文章可以对比着看。

本文的推导过程中，要注意的就是在多个含取等的不等式的合并中，各不等式的取等条件是否矛盾的问题。

---