附录B 凸集和凸函数

设 $V$ 是含有实数的一个域上的向量空间. $V$ 的一组选定的元素 $\pmb{v}_{1},\dots ,\pmb{v}_{k}\in V$ 的一个凸组合是其系数非负且和为1的线性组合：

\alpha_ {1} v _ {1} + \dots + \alpha_ {k} v _ {k}; \quad \alpha_ {1}, \dots , \alpha_ {k} \geqslant 0, \sum_ {i = 1} ^ {k} \alpha_ {i} - 1.

$V$ 的子集 $K$ 称为凸集，是指从 $K$ 中任意选定一组元素所作成的任一凸组合仍在 $K$ 中。等价地， $K$ 是凸集，是指 $K$ 中各个点偶的所有凸组合仍在 $K$ 中。几何上，这可以解释为连结 $K$ 的任意两点的线段必定在 $K$ 中；即 $K$ 没有“凹”或“洞”。一个凸集 $K$ 称为凸锥，是指每当 $\alpha > 0$ 和 $x \in K$ ，就有 $\alpha x \in K$ （等价地， $K$ 中元素的正线性组合仍在 $K$ 中）。直接验证可知，两个凸集（相应地，凸锥）的集和及交仍为一个凸集（相应地，凸锥）。

一个闭凸集 $K$ 的一个端点是这样一个点 $z \in K$ ，它只能用一种平凡的方式写成 $K$ 中点的一个凸组合，也就是说， $z = \alpha x + (1 - \alpha)y$ ， $0 < \alpha < 1$ ， $x, y \in K$ ，蕴涵 $x = y = z$ 。一个闭凸集可能有有限个端点（例如，一个多面体），也可能有无限多个端点（例如，一个闭圆盘），还可能无端点（例如， $\mathbb{R}^2$ 中的闭上半平面）。然面，一个紧凸集总有端点。 $V$ 中点的一个集合 $S$ 的凸包，记作 $\operatorname{Co}(S)$ ，就是选择 $S$ 的所有点组作成的所有凸组合的集合。或等价地，它是包含 $S$ 的（所有凸集的交）最小凸集。Krein-Milman 定理是说，一个紧凸集是它的端点的凸包，我们说一个紧凸集是有限生成的，是指它有有限多个端点，这些端点称为该凸集的生成元。

现在假定 $V$ 是具有一个给定范数的实或复向量空间，分离超平面定理是说，对于两个不相交的凸集 $K_{1} \subseteq V$ 和 $K_{2} \subseteq V$ ，存在 $V$ 中的一个超平面 $H$ ，使得 $K_{1}$ 位于由 $H$ 确定的两个闭半空间中的一个内，而 $K_{2}$ 位于另一个内；即 $H$ 分离 $K_{1}$ 和 $K_{2}$ . $V$ 中的一个超平面 $H$ 正好是 $V$ 的一个一维子空间的正交补的一个平移： $H = \{x \in V : \langle x - p, q \rangle = 0\}$ ，其中， $q \in V$ 是给定的向量， $q \neq 0$ . 超平面 $H$ 确定两个开半空间： $H' = \{x \in V : \langle x - p, q \rangle > 0\}$ ， $H' = \{x \in V : \langle x - p, q \rangle < 0\}$ . 集合 $H_{0}^{+} = H^{+} \cup H$ 和 $H_{0}^{-} = H \cup H$ 是由 $H$ 所确定的两个闭半空间．因此，分离意味着对某两个向量 $p, q$ 有 $K_{1} \subseteq H_{0}^{+}$ 和 $K_{2} \subseteq H_{0}$ . 对两个凸集附加某些条件就会有各种强化的分离结论．例如，如果 $K_{1}$ 和 $K_{2}$ 的闭包不相交，那么分离可以取得更为精确；即 $K_{1} \subseteq H^{+}$ ， $K_{2} \subseteq H$ ．任一有界集 $S \subset V$ 的凸包的闭包可以通过取包含 $S$ 的所有闭半空间的交面得到.

在 $V$ 是具有复内积 $\langle \cdot, \cdot \rangle$ 的向量空间 $\mathbf{C}^n$ 的情形，也可以类似地定义超平面和半空间，只是必须把 $\mathbf{C}^n$ 和 $\mathbf{R}^{2n}$ 等同起来，且必须用下述实内积 $\operatorname{Re}\langle \cdot, \cdot \rangle$ 代替 $\langle \cdot, \cdot \rangle$ 。将 $x + iy \in \mathbf{C}^n$ 等同于 $\left[ \begin{array}{c}x \\ y\end{array} \right] \in \mathbf{R}^{2n}$ ，还应注意到，根据复内积的共轭线性性质， $\operatorname{Re}\langle x_1 + iy_1, x_2 + iy_2 \rangle = \langle x_1, x_2 \rangle + \langle y_1, y_2 \rangle$ 。于是 $\langle x_1, x_2 \rangle + \langle y_1, y_2 \rangle$ 是 $\left[ \begin{array}{c}x_1 \\ y_1\end{array} \right]$ 和 $\left[ \begin{array}{c}x_2 \\ y_2\end{array} \right]$ 的（实）内积，而且 $\mathbf{R}^{2n}$ 中定义的超平面和半空间在 $\mathbf{C}^n$ 中有相应的几何解释。

我们说定义在一个凸集 $K \subseteq V$ 上的实值函数 $f$ 是凸函数，指的是对所有 $0 < \alpha < 1$ 和所有 $x, y \in K, y \neq x$ ，有

f (\alpha x + (1 - \alpha) y) \leqslant \alpha f (x) + (1 - \alpha) f (y). \tag {*}

如果上述不等式总是严格的，那么 $f$ 称为严格凸函数。如果对所有 $0 < \alpha < 1$ 和所有 $x, y \in K$ ， $y \neq x$ ，上述不等式是反向的，那么 $f$ 称为凹函数（或严格凹函数，如果反问不等式总是严格的）。等价地，一个凹函数（相应地，严格凹函数）正是一个凸函数（相应地，严格凸函数）的负值。几何上，连结任意两个函数值的弦位于一个凸函数（相应地，凹函数）的图象的上方（相应地，下方）。一个线性函数既是凸的，也是凹的。在 $V = \mathbb{R}^n$ 和 $K$ 是开集的情形，Hessian 矩阵为

H (x) \equiv \left[ \frac {\partial^ {2} f}{\partial x _ {i} \partial x _ {j}} (x) \right],

它是 $M_{n}(\mathbf{R})$ 中的对称矩阵，对于一个凸函数 $f$ ， $H(x)$ 在 $\kappa$ 中几乎处处存在，并且在使 $H(x)$ 存在的 $\kappa$ 中的各个点，它一定是半正定的．在严格凸的情形，它是正定的．反过来，一个函数，如果它的Hessian矩阵在整个凸集上是半正定(相应地，正定)的，那么该函数是凸（相应地，严格凸)的．类似地，负定性对应凹性.

凸函数和凹函数的最优化有一些好的性质。在紧凸集上，凸函数（相应地，凹函数）的极大值（相应地，极小值）在一个端点达到。另一方面，在一个凸集上，由那些达到一个凸函数（相应地，凹函数）的极小值（相应地，极大值）的点组成的集合是凸的，并且任一局部极小值（相应地，极大值）是全局极小值（相应地，极大值）。例如，一个严格凸函数至多在凸集的一个点达到极小值。且一个临界点一定是极小值点。

实数的凸组合满足某些简单而又常用的不等式．如果 $x_{1},\dots ,x_{k}$ 是给定的实数，那么

\min _ {1 \leqslant i, k} x _ {i} \leqslant \sum_ {i = 1} ^ {k} a _ {i} x _ {i} \leqslant \max _ {1 \leqslant i, k} x _ {i}

对任意凸组合 $\alpha_{1},\alpha_{2},\dots ,\alpha_{k}\geqslant 0$ 和 $\alpha_{1} + \dots +\alpha_{k} - 1$ 成立.

研究定义在一个区间上的某些简单的单变量凸函数 $f(\cdot)$ 可诱导出各种各样的经典不等式. 我们可以用归纳法证明, 定义在区间上的关于两个点的不等式 $(\star)$ 可以推出关于 $n$ 个点的不等式

f \left(\sum_ {i = 1} ^ {n} a _ {i} x _ {i}\right) \leqslant \sum_ {i = 1} ^ {n} a _ {i} f \left(x _ {i}\right), \quad n = 2, 3, \dots , \tag {*} *

只要 $\alpha_{1} \geqslant 0, \alpha_{1} + \cdots + \alpha_{n} = 1$ ，且所有 $x_{i}$ 都在区间内.

应用 $(\ast \ast)$ 于区间 $(0, \infty)$ 上的严格凸函数 $f(x) = -\log x$ ，便导出加权算术—几何平均值不等式

\sum_ {i = 1} ^ {n} \alpha_ {i} x _ {i} \geqslant \prod_ {i = 1} ^ {n} x _ {i} ^ {\sigma_ {i}}, \quad x _ {i} \geqslant 0,

当所有 $\alpha_{i} = 1 / n$ 时，它就是算术一几何平均值不等式

\frac {1}{n} \sum_ {i = 1} ^ {n} x _ {i} \geqslant \left(\prod_ {i = 1} ^ {n} x _ {i}\right) ^ {1 n}, \quad x _ {i} \geqslant 0,

等式成立，当且仅当所有 $x_{i}$ 都相等.

把 $(\ast \ast)$ 应用于定义在区间 $(0, \infty)$ 上的 $f(x) = x^p$ ， $p > 1$ ，便导出 Hölder 不等式

\sum_ {i = 1} ^ {n} x _ {i} y _ {i} \leqslant \left(\sum_ {i = 1} ^ {n} x _ {i} ^ {p}\right) ^ {1, p} \left(\sum_ {i = 1} ^ {n} y _ {i} ^ {q}\right) ^ {1, q},

其中 $x_{i}, y_{i} > 0, p > 1$ ，且 $1/p + 1/q = 1$ 。等式成立，当且仅当向量 $[x_i^p]$ 和 $[y_i^q]$ 相关。如果取 $p = q = 2$ ，我们便得到 Cauchy-Schwarz 不等式的另一种形式

\sum_ {i = 1} ^ {n} x _ {i} y _ {i} \leqslant \left(\sum_ {i = 1} ^ {n} x _ {i} ^ {2}\right) ^ {1 / 2} \left(\sum_ {i = 1} ^ {n} y _ {i} ^ {2}\right) ^ {1 / 2}.

等式成立，当且仅当向量 $[x_i]$ 和 $[y_i]$ 是相关的。我们可以从Holder不等式推出Minkowski不等式

\left[ \sum_ {i = 1} ^ {n} \left(x _ {i} + y _ {i}\right) ^ {p} \right] ^ {1 / p} \leqslant \left(\sum_ {i = 1} ^ {n} x _ {i} ^ {p}\right) ^ {1 / p} + \left(\sum_ {i - 1} ^ {n} y _ {i} ^ {p}\right) ^ {1 / p},

其中 $x_{i}, y_{i} > 0$ 且 $p \geqslant 1$ 。等式成立，当且仅当向量 $[x_i]$ 和 $[y_i]$ 是相关的。

进一步阅读关于凸集与几何的其他资料可参看[Val]. 关于凸函数与不等式的其他资料可参看[Boa]和[BB].

535

README

附录B 凸集和凸函数