凸几何 · 纠缠理论的数学基础

在凸几何中，我们常常在 $n$ 维Euclidean空间内处理问题，因此本章讨论的向量空间仅限于 $R^{n}$ 。尽管凸性本身是纯代数性质，不过凸集本身不具有代数封闭的良好性质；在凸集上讨论更多的是一些特有的代数性质与拓扑性质，例如极值表示、支撑与分离，其中前者与高维Bell不等式的违背密切相关。

10.1代数性质

定义 10.1 （凸集）

对于集合 $A \subseteq R^{n}$ ，若对于 $x, y \in A$ 和 $α \in [0, 1]$ 均有 $(1 - α) x + α y \in A$ ，则称其为凸的（convex）。

例 10.1

对于不同的 $x, y \in R^{n}$ ，最简单的非平凡凸集是开线段（open segment） $(x, y) = {(1 - α) x + α y ∣ α \in (0, 1)}$ 和闭线段（close segment） $[x, y] = {(1 - α) + α y ∣ α \in [0, 1]}$ 。类似可定义半开线段 $(x, y]$ 和 $[x, y)$ ；
$R^{n}$ 中的平坦也是凸集。更具体地，给定线性形式 $f \neq = 0$ 和某个 $α \in R$ ，则 ${f = α}$ 是凸的。若 ${f = α}$ 表示超平面，则开半空间（open halfspace） ${f < α}, {f > α}$ 和闭半空间（close halfspace）也是凸集；
定义 1.19中的开球与闭球也是凸的，并且在 $B (x, r)$ 的边界上添加任意子集得到的集合仍是凸的。

定义 10.2 （凸组合）

设 $k \in N$ ， $x_{1}, \dots, x_{k} \in R^{n}$ ，并且 $α_{1}, \dots, α_{k} \in [0, 1]$ ，满足 $α_{1} + \dots + α_{k} = 1$ ，则 $α_{1} x_{1} + \dots + α_{k} x_{k}$ 称为点 $x_{1}, \dots, x_{k}$ 的凸组合（convex combination）。

定理 10.1

集合 $A \subseteq R^{n}$ 是凸集当且仅当 $A$ 中所有凸组合均在 $A$ 内。

证明

充分性是显然的；必要性可通过归纳法采用与命题 9.2类似的讨论直接证明。

根据先前的经验，代数结构的“生成”是一个极其重要的概念，例如闭包、生成向量空间（可以视为一种“线性包”）、仿射包。采用类似的思路，在这里我们希望定义“凸包”。对于 $R^{n}$ 中的任意凸集族 ${A_{k} ∣ k \in K}$ ，对于其交集 $\cap_{k \in K} A_{k}$ 内的任意两点 $x$ 和 $y$ ，由于 $(1 - α) x + α y \in A_{k}$ 对所有 $α \in [0, 1]$ 和所有 $k \in K$ 成立，因此 $\cap_{k \in K} A_{k}$ 也是凸集。特别地，对于给定的 $A \subseteq R^{n}$ ，所有包含 $A$ 的凸集的交集是凸的。由此可以引出如下定义。

定义 10.3 （凸包）

对于 $A \subseteq R^{n}$ ，集合

conv (A) = ⋂ {C \subseteq R^{n} ∣ A \subseteq C, C is convex}

(10.1.1)

称为 $A$ 的凸包（convex hull）。

注

若 $A, B \subseteq R^{n}$ 且 $A \subseteq B$ ，由于 $conv (A)$ 是包含 $A$ 的最小凸包，因此 $A \subseteq B \subseteq conv (B)$ 意味着 $conv (A) \subseteq conv (B)$ ；以后我们经常会用到此结论。此外还有 $conv (\emptyset) = \emptyset$ 和 $conv (R^{n}) = R^{n}$ 。

类似定理 9.2，凸包不出意外地可由凸组合刻画。

定理 10.2

对于 $A \subseteq R^{n}$ ， $conv (A)$ 是 $A$ 中向量的所有凸组合构成的集合。

证明

记 $A$ 中向量的所有凸组合构成的集合为 $B$ 。根据定理 10.1， $A$ 的凸包含有 $A$ 中向量的所有凸组合，因此 $B \subseteq conv (A)$ 。现在我们希望证明 $B$ 是包含 $A$ 的一个凸集，那么作为包含 $A$ 的最小凸集， $conv (A) \subseteq B$ 。设 $A = {x_{i} ∣ i \in I}$ ，则对于任意 $y_{i} \in B$ ，存在 $β_{i, j} \in [0, 1]$ 满足 $\sum_{j} β_{i, j} = 1$ ，同时使得 $y_{i} = \sum_{j} s_{i, j} x_{j}$ ，因此凸组合

i = 1 \sum n α_{i} y_{i} = i, j \sum α_{i} β_{i, j} x_{j} \in B, where α_{i} β_{i, j} \in [0, 1] and i, j \sum α_{i} β_{i, j} = i \sum α_{i} j \sum β_{i, j} = i \sum α_{i} = 1,

(10.1.2)

因此 $B$ 也是凸集，从而 $conv (A) \subseteq B$ ，结论得证。

注

该定理的一个平凡结论是， $A$ 为凸集当且仅当 $conv (A) = A$ ，这实际上就是定理 10.1的内容。

定义 10.4 （Minkowski组合）

对于集合 $A, B \subseteq R^{n}$ 和 $α, β \in R$ ，定义

α A + β B = {α x + β y ∣ x \in A, y \in B} .

(10.1.3)

集合 $α A + β B$ 称为集合 $A, B$ 的Minkowski组合（Minkowski combination），运算 $+$ 称为Minkowski加法（Minkowski addition）。 $A$ 与 $B$ 的差集（difference） $A - B$ 定义为 $A + (- B)$ 。

命题 10.1

若 $A, B \subseteq R^{n}$ 是凸集且 $α, β \in R$ ，则 $α A + β B$ 是凸集。

证明

任取 $α A + β B$ 中的元素 $α x_{1} + β y_{1}$ 和 $α x_{2} + β y_{2}$ ，其中 $x_{1}, x_{2} \in A$ 且 $y_{1}, y_{2} \in B$ 。那么对于任意 $λ \in [0, 1]$ ， $λ (α x_{1} + β y_{1}) + (1 - λ) (α x_{2} + β y_{2}) = α [λ x_{1} + (1 - λ) x_{2}] + β [λ y_{1} + (1 - λ) y_{2}] \in α A + β B$ 。可见 $α A + β B$ 为凸集。

命题 10.2

设集合 $A \subseteq R^{n}$ 。

$(α + β) A \subseteq α A + β A$ 对所有 $α, β \in R$ 成立；
若 $A$ 为凸集，则 $α A + β A = (α + β) A$ 对所有 $α, β \geq 0$ 成立；
若 $(1 - λ) A + λ A = A$ 对所有 $λ \in [0, 1]$ 成立，则 $A$ 为凸集。

证明

对于任意 $a \in A$ ， $(α + β) a = α a + β a \in α A + β A$ ，即 $(α + β) A \subseteq α A + β A$ ；
这里仅需证明反向包含成立。当 $A$ 为凸集时，对于任意 $α x + β y \in α A + β A$ ，容易看出 $(α x + β y) / (α + β) \in A$ ，故 $α A + β A \subseteq (α + β) A$ ；
对于任意 $x, y \in A$ ， $(1 - λ) x + λ y \in (1 - λ) A + λ A = A$ ，因此 $A$ 为凸集。

虽然上一章中我们未对仿射变换作过多讨论，但还是有必要介绍，因为其具有保凸的良好性质。

定理 10.3

设 $A \subseteq R^{n}$ 和 $B \subseteq R^{n}$ 均为凸集， $f : R^{n} \to R^{m}$ 为仿射变换，则

f (A) = {f (x) ∣ x \in A} and f^{- 1} (B) = {x \in R^{n} ∣ f (x) \in B}

(10.1.4)

均为凸集。

证明

对于 $f (A)$ 中的任意两个元素，存在 $x, y \in A$ 使其分别等于 $f (x)$ 和 $f (y)$ 。由于 $A$ 为凸集， $(1 - λ) x + λ y \in A$ 对所有 $λ \in [0, 1]$ 成立，从而 $(1 - λ) f (x) + λ f (y) = f ((1 - λ) x + λ y) \in f (A)$ ，故 $f (A)$ 为凸集； $f^{- 1} (B)$ 类似。

定义 10.5

有限多个闭半空间的交集称为多面体集（polyhedral set）；
有限多个点 $x_{1}, \dots, x_{k} \in R^{n}$ 的凸包称为（凸）多胞形（polytype）；
仿射无关点集的凸包称为单纯形（simplex）。 $r$ -单纯形为 $(r + 1)$ 个仿射无关点的凸包。

注

空集和全空间均为多面体集。根据Heine-Borel定理 1.10，多胞形总是紧致集；多面体集是闭集，但可能无界。

定义 10.6 （顶点）

若多胞形 $P$ 内的点 $x$ 使得 $P \ {x}$ 仍为凸集，则称其为顶点（vertex）。 $P$ 的顶点构成的集合记为 $vert (P)$ 。

定理 10.4

设 $P$ 为 $R^{n}$ 中的多胞形， $x_{1}, \dots, x_{k} \in R^{n}$ 为不同的点。

若 $P = conv {x_{1}, \dots, x_{k}}$ ，则 $x_{1}$ 是 $P$ 的顶点当且仅当 $x_{1} \in / conv {x_{2}, \dots, x_{k}}$ ；
$P$ 为其顶点的凸包。

证明

若 $x_{1}$ 为 $P$ 的顶点，则 $P \ {x_{1}}$ 是凸集且 $x_{1} \in / P \ {x_{1}}$ 。根据凸包的定义， ${x_{2}, \dots, x_{k}} \subseteq P \ {x_{1}}$ 意味着 $conv {x_{2}, \dots, x_{k}} \subseteq P \ {x_{1}}$ ，因此 $x_{1} = P \ (P \ {x_{1}}) \in P \ conv {x_{2}, \dots, x_{k}}$ ，即 $x_{1} \in / conv {x_{2}, \dots, x_{k}}$ ；反之，若 $x_{1}$ 不是 $P$ 的顶点，那么存在 $a, b \in P \ {x_{1}}$ 和 $λ (0, 1)$ 使得 $x_{1} = (1 - λ) a + λb$ （否则 $P \ {x_{1}}$ 为凸集，矛盾）。设凸组合 $a = \sum_{i = 1}^{k} α_{i}, b = \sum_{i = 1}^{k} β_{i} x_{i}$ ，那么 $x_{1} = (1 - λ) a + λb = \sum_{i = 1}^{k} [(1 - λ) α_{i} + λ β_{i}] x_{i}$ ，其中 $0 \leq (1 - λ) α_{i} + λ β_{i} \leq (1 - λ) + λ = 1$ 对所有 $i$ 成立。当 $α_{1} = β_{1} = 1$ 时上式恒等，但此时 $a = b = x_{1}$ ，矛盾；因此 $(1 - λ) α_{1} + λ β_{1} \in [0, 1)$ ，将其改写为 $x_{1} = [1 - (1 - λ) α_{1} - λ β_{1}]^{- 1} \sum_{i = 2}^{k} [(1 - λ) α_{i} + λ β_{i}] x_{i} \in conv {x_{2}, \dots, x_{k}}$ ，结论得证；
根据定义，设存在有点点集 $A = {x_{1}, \dots, x_{n}} \in P$ 使得 $P = conv (A)$ 。若存在 $x_{i} \in P$ 使其可表示为其余向量的凸组合，即 $x_{i} = \sum_{j \neq = i} β_{j} x_{j}$ 。那么对于任意 $x \in P$ ，设其凸组合为 $x = \sum_{i = 1}^{k} α_{i} x_{i}$ ，我们有

$x = α_{i} j \neq = i \sum β_{j} x_{j} + j \neq = i \sum α_{j} x_{j} = j \neq = i \sum (α_{j} + α_{i} β_{j}) x_{j} \in conv (A \ {x_{i}}),$
(10.1.5)

从而 $P \subseteq conv (A \ {x_{i}}) \subseteq conv (A) = P$ ，即 $P$ 为 $A \ {x_{i}}$ 的凸包。如此操作至多有限次，最终剩余点均为 $P$ 的顶点，并且 $P = conv (vert (P))$ 。

推论 10.1

设 $M \subseteq R^{n}$ 是一个集合， $x \in R^{n} \ M$ 。记 $A = conv ({x} \cup M)$ ，则 $A \ {x}$ 是凸的当且仅当 $x \in / conv (M)$ 。

多胞形的性质在集合的基本运算下保持，即有如下结果。

命题 10.3

若 $P, Q$ 为 $R^{n}$ 中的多胞形，则以下集合也是多胞形：

$conv (P \cup Q)$ 和 $P \cap Q$ ；
$α P + β Q$ 对任意 $α, β \in R$ ；
$f (P)$ 对任意仿射变换 $f : R^{n} \to R^{m}$ 。

证明

由于 $vert (P) \cup vert (Q) \subseteq P \cup Q$ ， $conv (vert (P) \cup vert (Q)) \subseteq conv (P \cup Q)$ ；另一方面，对于任意 $x \in P \cup Q$ ，根据定理 10.4， $x$ 可表示为 $vert (P)$ 或 $vert (Q)$ 的凸组合，进而可表示为 $vert (P) \cup vert (Q)$ 的凸组合（多余的向量补足系数0），因此 $P \cup Q \subseteq conv (vert (P) \cup vert (Q))$ ，进而 $conv (P \cup Q) \subseteq conv (vert (P) \cup vert (Q))$ 。综上， $conv (P \cup Q) = conv (vert (P) \cup vert (Q))$ 。多胞形的定义保证了 $∣ vert (P) \cup vert (Q) ∣ < \infty$ ，故 $conv (P \cup Q)$ 也是多胞形。至于 $P \cap Q$ ，在第第 10.4 节节证明了多胞形与多面体集的等价性后该结论自然成立；
由于 $α vert (P) + β vert (Q) \subseteq α P + β Q$ ，因此根据命题 10.1， $conv (α vert (P) + β vert (Q)) \subseteq α P + β Q$ ；另一方面，对于任意 $α x + β y \in α P + β Q$ ，设 $vert (P) = {x_{1}, \dots, x_{k}}, vert (Q) = {y_{1}, \dots, y_{l}}$ ，则存在凸组合 $x = \sum_{i = 1}^{k} α_{i} x_{i}$ 和 $y = \sum_{j = 1}^{l} β_{j} y_{j}$ ，使得

$α x + β y = α (j = 1 \sum l β_{j}) (i = 1 \sum k α_{i} x_{i}) + β (i = 1 \sum k α_{i}) (j = 1 \sum l β_{j} y_{j}) = i, j \sum α_{i} β_{j} (α x_{i} + β y_{j}) \in conv (α vert (P) + β vert (Q)),$
(10.1.6)

即 $α P + β Q \subseteq conv (α vert (P) + β vert (Q))$ ，反向包含成立。此时 $∣ α vert (P) + β vert (Q) ∣ \leq ∣ vert (P) ∣ ∣ vert (Q) ∣ < \infty$ ，即 $α vert (P) + β vert (Q)$ 为有限集，故 $α P + β Q$ 为多胞形；
由于 $f (vert (P)) \subseteq f (P)$ ，根据定理 10.3， $conv (f (vert (P))) \subseteq f (P)$ ；另一方面，设 $vert (P) = {x_{1}, \dots, x_{k}}$ ，则对于任意 $x \in P$ ，存在凸组合 $x = \sum_{i = 1}^{k} α_{i} x_{i}$ ，使得 $f (x) = \sum_{i = 1}^{k} α_{i} f (x_{i}) \in conv (f (vert (P)))$ ，即 $f (P) \subseteq conv (f (vert (P)))$ ，反向包含成立。此时 $f (vert (P))$ 为有限集，故 $f (P)$ 为多胞形。

命题 10.4

若 $P$ 是仿射无关点 $x_{0}, \dots, x_{r}$ 的凸包，则 $P$ 是 $r$ -单纯形，并且每个点 $x_{i}$ 都是 $P$ 的顶点。 $r$ -单纯形具有维数 $dim (P) = r$ ，这里维数定义为将该集合嵌入其仿射包后该仿射包的维数。

证明

根据定义， $P$ 是 $r$ -单纯形，因此必然为多胞形。记 $X = {x_{0}, \dots, x_{r}}$ ，根据定理 9.4， $X$ 仿射无关意味着 $x_{i} \in / aff (X \ {x_{i}})$ ，显然有 $x_{i} \in / conv (X \ {x_{i}})$ ；因此利用定理 10.4，所有 $x_{i}$ 均为 $P$ 的顶点，且 $dim (P) = r$ 。

单纯形可通过凸组合的唯一性刻画。

定理 10.5

凸集 $A \subseteq R^{n}$ 是单纯形当且仅当存在 $x_{0}, \dots, x_{k} \in A$ ，使得每个 $x \in A$ 具有作为 $x_{0}, \dots, x_{k}$ 的凸组合的唯一表示。

证明

若 $A$ 为单纯形，那么存在仿射无关集 $X = {x_{0}, \dots, x_{k}} \subseteq A$ 使得 $A = conv (X)$ 。根据定理 9.4， $A$ 内任意点的关于 $X$ 的仿射组合唯一，进而关于 $X$ 的凸组合唯一；反之当该表示存在时，首先利用 $X \subseteq A$ 可知 $A \subseteq conv (X) \subseteq A$ ，即 $A = conv (X)$ ；现在利用该表示的唯一性，假设存在 $x_{i} \in X$ 使得 $x_{i} \in aff (X \ {x_{i}})$ ，即存在仿射组合 $x_{i} = \sum_{j \neq = i} r_{j} x_{j}$ 。分别记指标集 $J_{+} = {j \neq = i ∣ r_{j} > 0}$ 和 $J_{-} = {j \neq = i ∣ r_{j} < 0}$ ，并记 $λ^{- 1} = \sum_{j \in J^{+}} r_{j} > 0$ ，那么 $1 - \sum_{j \in J^{-}} r_{j} = 1 - (1 - \sum_{j \in J^{+}} r_{j}) = λ^{- 1}$ ，同时唯一性要求以下的凸组合

λ x_{i} + λ j \in J_{-} \sum (- r_{j}) x_{j} = λ j \in J^{+} \sum r_{j} x_{j}

(10.1.7)

中 $x_{i}$ 同系数，但 $λ > 0$ 且 $i \in / J_{\pm}$ ，矛盾。因此 $x_{i} \in / aff (X \ {x_{i}})$ 。根据定理 9.4， $X$ 仿射无关，即 $A$ 是单纯形。

10.2组合性质

凸几何中这一部分称为组合几何（combinatorial geometry），我们仅介绍其中最重要的三个定理。

定理 10.6 （Radon定理）

设 $x_{1}, \dots, x_{m} \in R^{n}$ 为仿射相关的点，则存在划分 ${1, \dots, m} = I \cup J$ ，其中 $I \cap J = \emptyset$ ，使得

conv {x_{i} ∣ i \in I} \cap conv {x_{j} ∣ j \in J} \neq = \emptyset .

(10.2.1)

证明

设 $x_{1}, \dots, x_{m} \in R^{n}$ 仿射相关，那么根据定理 9.4，存在不全为零的 $α_{1}, \dots, α_{m} \in R$ 使得 $\sum_{i = 1}^{m} α_{i} x_{i} = 0$ 且 $\sum_{i = 1}^{m} α_{i} = 0$ 。定义指标集 $I = {i ∣ α_{i} \geq 0}$ 和 $J = {1, \dots, m} \ I$ ，显然 $I \cap J = \emptyset$ 。记 $λ^{- 1} = \sum_{j \in J} (- α_{j}) > 0$ ，那么 $\sum_{i \in I} α_{i} = - \sum_{j \in J} α_{j} = λ^{- 1}$ ，进而存在凸组合

λ i \in I \sum α_{i} = λ j \in J \sum (- r_{j}) α_{j} ⟹ conv {x_{i} ∣ i \in I} \cap conv {x_{j} ∣ j \in J} \neq = \emptyset .

(10.2.2)

Helly定理研究的是这样一类问题：若集族 ${A_{k} ∣ k \in K}$ 中任意有限多集合都共享某种性质，那么是否所有集合都共享这种性质？事实上，我们在第第 1 章章证明的闭区间套定理 1.11就是一例。下面我们仅针对特定性质讨论。

定理 10.7 （Helly定理）

设 $A_{1}, \dots, A_{m}$ 为 $R^{n}$ 中的凸集，其中 $m \geq n + 1$ 。若集合 $A_{1}, \dots, A_{m}$ 中任意 $(n + 1)$ 个均具有非空交集，则 $\cap_{i = 1}^{m} A_{i} \neq = \emptyset$ ；
设 $A = {A_{k} ∣ k \in K}$ 为 $R^{n}$ 中至少 $(n + 1)$ 个紧凸集构成的集族。若 $A$ 中任意 $(n + 1)$ 个集合均具有非空交集，则 $\cap_{k \in K} A_{k} \neq = \emptyset$ 。

证明

我们对 $m - n$ 进行归纳。当 $m - n = 1$ 时，结论显然成立。当 $m - n \geq 2$ 时，假设结论对于 $A_{1}, \dots, A_{m}$ 中任意 $m - 1$ 个集合成立，那么对于任意 $i = 1, \dots, m$ ，存在 $x_{i} \in \cap_{j \neq = i} A_{j}$ ，并记 $X = {x_{1}, \dots, x_{m}}$ 。若 $X$ 仿射无关，那么根据定理 9.4， $dim (aff (X)) = m - 1 \geq n + 1 > dim (R^{n})$ ，矛盾。因此 $X$ 仿射无关。根据Radon定理 10.6，存在指标集 $I, J$ 满足 $I \cup J = {1, \dots, m}$ 且 $I \cap J = \emptyset$ ，并使得交集 $conv {x_{i} ∣ i \in I} \cap conv {x_{j} ∣ j \in J}$ 非空。取该交集内的元素 $x$ 。注意到 $I \cap J = \emptyset$ ，则对于任意 $i \in I$ 和 $j \in J$ ， $x_{i} \in \cap_{k \neq = i} A_{k} = (\cap_{k \neq = i, j} A_{k}) \cap A_{j} \subseteq A_{j}$ ，进而 $x \in conv {x_{i} ∣ i \in I} \subseteq A_{j}$ 对所有 $j \in J$ 成立，因此 $x \in \cap_{j \in J} A_{j}$ 。类似地， $x \in \cap_{i \in I} A_{i}$ ，最后得到 $x \in (\cap_{i \in I} A_{i}) \cap (\cap_{j \in J} A_{j}) = \cap_{i = 1}^{m} A_{i}$ ，即 $\cap_{i = 1}^{m} A_{i} \neq = \emptyset$ ；
根据上一条结论，集族 $A$ 内任意有限多集合的交集非空。根据Heine-Borel定理 1.10， $A_{k}$ 是有界闭集。假设 $\cap_{k \in K} A_{k} = \emptyset$ ，那么 $\cup_{k \in K} A_{k}^{c} = R^{n}$ 构成 $R^{n}$ 的一个开覆盖。由于任意集合 $A \in A$ 紧致，存在有限指标集 $K_{0}$ 使得 $A \subseteq \cup_{k \in K_{0}} A_{k}^{c}$ 对所有 $k \in K$ 成立，即 $\cap_{k \in K_{0}} A_{k} \subseteq A^{c}$ 。但此时有限交集 $(\cap_{k \in K_{0}} A_{k}) \cap A = \emptyset$ ，矛盾。因此 $\cap_{k \in K} A_{k} \neq = \emptyset$ ，结论得证。

注

上述第二条结论中紧致性是必要的。考虑 $R$ 上的开线段 $A_{n} = (- 1/ n, 1 - 1/ n)$ 。那么对于任意两条不同的开线段 $A_{n}$ 和 $A_{m}$ ，不妨设 $n < m$ ，那么 $A_{n} \cap A_{m} = (- 1/ m, 1 - 1/ n) \neq = \emptyset$ ；但是 $\cap_{k = 1}^{n} A_{k} = (- 1/ n, 0)$ 。对于任意正数 $ϵ$ ，由Archimedean性质命题 1.19，存在自然数 $n_{0}$ 使得 $- ϵ < - 1/ n_{0}$ ，即 $- ϵ \in / \cap_{n = n_{0}}^{\infty} A_{n}$ ，进而 $\cap_{n = 1}^{\infty} A_{n} = \emptyset$ 。

定理 10.8 （Carathéodory定理）

对于集合 $A \subseteq R^{n}$ 和 $x \in R^{n}$ ，以下两种表述等价：

$x \in conv (A)$ ；
对于某个 $r \in {0, \dots, n}$ ，存在一个顶点在 $A$ 上的 $r$ -单纯形 $P$ ，使得 $x \in P$ 。

证明

对于必要性， $vert (P) \subseteq A$ 意味着 $x \in P = conv (vert (P)) \subseteq conv (A)$ ；对于充分性，存在 $x_{1}, \dots, x_{k} \in A$ 使得 $x$ 可表示为凸组合 $\sum_{i = 1}^{k} α_{i} x_{i}$ 。对于满足上述条件的全体自然数构成的集合，根据定理 1.7，其中必然存在一个最小自然数 $k$ ，此时任意 $(k - 1)$ 个点的凸包不包含 $x$ ，希望证明这 $k$ 个点仿射无关。假设其仿射相关，即存在不全为零的 $β_{1}, \dots, β_{k} \in R$ 使得 $\sum_{i = 1}^{k} β_{k} x_{i} = 0$ 且 $\sum_{i = 1}^{k} β_{i} = 0$ 。那么存在非空指标集 $J = {i ∣ β_{i} > 0}$ ，从中选择指标 $j_{0}$ 使得 $α_{j_{0}} / β_{j_{0}} = min_{j \in J} (α_{j} / β_{j})$ ，进而可构造

x = x - \frac{α _{j_{0}}}{β _{j_{0}}} i = 1 \sum k β_{i} x_{i} = i \neq = j_{0} \sum (α_{i} - \frac{α _{j_{0}}}{β _{j_{0}}} β_{i}) x_{i},

(10.2.3)

其中 $α_{i} - α_{j_{0}} β_{i} / β_{j_{0}} \geq 0$ 对任意 $i$ 成立，并且 $\sum_{i = 1}^{k} (α_{i} - α_{j_{0}} β_{i} / β_{j_{0}}) = 1 - 0 = 1$ ，因此 $x$ 可由 $(k - 1)$ 个非零向表示，这与 $k$ 的极小性矛盾。因此 $x_{1}, \dots, x_{k}$ 仿射无关，此时 $P = conv {x_{1}, \dots, x_{k}}$ 是包含 $x$ 的一个单纯形。

注

上述定理表明，若 $x$ 是仿射相关点 $x_{1}, \dots, x_{k}$ 的凸组合，则至少有一个点是冗余的。重复此操作有限次，我们可得到 $x$ 作为 ${x_{1}, \dots, x_{k}}$ 的仿射无关子集的凸组合表示。特别地， $A \subseteq R^{n}$ 的凸包内任一点是 $A$ 中至多 $(n + 1)$ 个点的凸组合。显然，这些点的选择依赖于 $x$ 。

10.3拓扑性质

尽管凸性是纯代数性质，但该性质仍然带来了一些特别的拓扑结果。

命题 10.5

若对于整数 $k \in {1, \dots, n}$ ， $P = conv {x_{0}, \dots, x_{k}}$ 是 $R^{n}$ 中的一个 $k$ -单纯形，则其相对内部¹

relint (P) = {α_{0} x_{0} + \dots + α_{k} x_{k} \in R^{n} ∣ α_{i} \in (0, 1), α_{0} + \dots + α_{k} = 1} .

(10.3.1)

特别地， $(x_{0} + \dots + x_{k}) / (k + 1) \in relint (P)$ 。

证明

记 $P$ 的基底子空间为 $S = aff (P) - x_{0}$ ， $s_{i} = x_{i} - x_{0}$ 对所有 $1 \leq i \leq k$ 成立。根据定理 9.4， ${x_{0}, \dots, x_{k}}$ 的仿射无关性要求 $B = {s_{1}, \dots, s_{k}}$ 线性无关，那么 $B$ 构成 $S$ 的一组基，此时等价于证明

relint (P) = {α_{1} s_{1} + \dots + α_{k} s_{k} \in S ∣ α_{i} \in (0, 1), α_{1} + \dots + α_{k} \in (0, 1)} .

(10.3.2)

考虑(2.3.2)式定义的坐标映射 $ϕ_{B}$ ，其为向量空间之间的同构。对于任意 $x = \sum_{i = 1}^{k} α_{i} s_{i}, y = \sum_{i = 1}^{k} β_{i} s_{i} \in S$ 以及正数 $ϵ$ ，当 $\sum_{i = 1}^{k} ∣ α_{i} - β_{i} ∣^{2} < ϵ^{2} / (\sum_{i = 1}^{k} ∥ s_{i} ∥^{2})$ 时，由Cauchy-Schwarz不等式，

∥ x - y ∥ = i = 1 \sum k (α_{i} - β_{i}) s_{i} \leq i = 1 \sum k ∣ α_{i} - β_{i} ∣ ∥ s_{i} ∥ \leq (i = 1 \sum k ∣ α_{i} - β_{i} ∣^{2})^{1/2} (i = 1 \sum k ∥ s_{i} ∥^{2})^{1/2} < ϵ .

(10.3.3)

根据命题 1.16， $ϕ_{B}^{- 1} : R^{k} \to S$ 是连续的，从而 $ϕ_{B}$ 是同胚（参见定义 A.9）。对于任意 $x \in ϕ_{B} (relint (P))$ ，存在 $S$ 内的开球 $B (ϕ_{B}^{- 1} (x), r) \subseteq P - x_{0}$ ，根据命题 1.17，存在 $x$ 的邻域 $U \subseteq ϕ_{B} (B (ϕ^{- 1} (x), r)) \subseteq ϕ_{B} (P - x_{0})$ ，即 $x \in relint (ϕ_{B} (P - x_{0}))$ ，从而 $ϕ_{B} (relint (P)) \subseteq relint (ϕ_{B} (P - x_{0}))$ ；反之对于任意 $x \in relint (ϕ_{B} (P - x_{0}))$ ，存在开球 $B^{'} (x, r) \subseteq ϕ_{B} (P - x_{0})$ ，根据命题 1.17，存在包含 $ϕ_{B}^{- 1} (x)$ 的邻域 $V \subseteq ϕ_{B}^{- 1} (B^{'} (ϕ_{B}^{- 1}, r)) \subseteq P - x_{0}$ ，即 $ϕ_{B}^{- 1} (x) \in relint (P)$ ，从而 $relint (ϕ_{B} (P - x_{0})) \subseteq ϕ_{B} (relint (P))$ 。因此

ϕ_{B} (relint (P)) = relint (ϕ_{B} (P - x_{0})) = relint {(α_{1}, \dots, α_{k}) \in R^{k} ∣ α_{i} \in [0, 1], α_{1} + \dots + α_{k} \in [0, 1]} .

(10.3.4)

记集合 $U = {(α_{1}, \dots, α_{k}) \in R^{k} ∣ α_{i} \in (0, 1), α_{1} + \dots + α_{k} \in (0, 1)}$ 。对于任意 $x = (α_{1}, \dots, α_{k}) \in U$ ，取正数 $ϵ$ 为 $min_{i} α_{i}$ 和 $(1 - \sum_{i} α_{i}) / k$ 中的较小值。那么对于任意 $y = (β_{1}, \dots, β_{k}) \in B (x, ϵ)$ ，首先有 $∣ β_{i} - α_{i} ∣ \leq (\sum_{i} ∣ β_{i} - α_{i} ∣^{2})^{1/2} = ∥ x - y ∥ < ϵ$ 对所有 $i$ 成立，因此 $β_{i} > α_{i} - ϵ \geq α_{i} - min_{i} α_{i} \geq 0$ ，同时 $\sum_{i} β_{i} < \sum_{i} (α_{i} + ϵ) \leq \sum_{i} α_{i} + (1 - \sum_{i} α_{i}) = 1$ ，因此 $B (x, ϵ) \subseteq relint (ϕ_{B} (P - x_{0}))$ ；对于反向包含，设 $x = (α_{1}, \dots, α_{k}) \in relint (ϕ_{B} (P - x_{0}))$ ，即存在开球 $B (x, r) \subseteq ϕ_{B} (P - x_{0})$ 。我们希望证明 $α_{i} > 0$ 对所有 $i$ 成立，并且 $\sum_{i} α_{i} < 1$ 。假设存在 $α_{i} = 0$ ，那么 $y = (α_{1}, \dots, α_{i - 1}, - r /2, α_{i + 1}, \dots, α_{k}) \in B (x, r)$ ，但显然 $y \in / ϕ_{B} (P - x_{0})$ ，矛盾，因此 $α_{i} > 0$ 对所有 $i$ 成立；假设 $\sum_{i} α_{i} = 1$ ，那么 $y = (α_{1} + r /2 k, \dots, α_{k} + r /2 k) \in B (x, r)$ ，但显然 $\sum_{i} (α_{i} + r /2 k) = 1 + r k /2 > 1$ ，矛盾，因此 $\sum_{i} α_{i} < 1$ 。因此 $α_{i} \in (0, 1)$ 对所有 $i$ 成立，并且 $\sum_{i} α_{i} \in (0, 1)$ ，即 $relint (ϕ_{B} (P - x_{0})) \subseteq U$ 。结合(10.3.2)式， $ϕ_{B} (relint (P)) = relint (ϕ_{B} (P - x_{0})) = U$ ，即

relint (P) = ϕ^{- 1} (U) = {\sum_{i} α_{i} s_{i} \in S ∣ α_{i} \in (0, 1), \sum_{i} α_{i} \in (0, 1)} .

(10.3.5)

定理 10.9

若非空子集 $A \subseteq R^{n}$ 是凸的，则 $relint (A) \neq = \emptyset$ 。

证明

根据Carathéodory定理 10.8，对于任意 $x \in A$ ，存在顶点在 $A$ 上的单纯形 $P$ 使得 $x \in P$ ，其中 $P = conv (vert (P)) \subseteq conv (A) = A$ 。再根据命题 10.5， $relint (P)$ 非空，考虑 $y \in relint (P)$ ，那么存在包含 $y$ 的邻域 $U \subseteq P \subseteq A$ ，故 $y \in relint (A)$ ，即 $relint (A) \neq = \emptyset$ 。

上述定理说明，在研究给定凸集 $A$ 时，将其仿射包作为基底空间是有用的：尽管 $A$ 在全空间内未必具有内点（例如 $R^{3}$ 中 $x O y$ 平面上的圆），但其在仿射包中必然具有内点。因此，后文我们会不失一般性地假定 $A$ （在 $R^{n}$ 的某个子空间 $R^{k}$ 中）内部非空。

命题 10.6

若 $A \subseteq R^{n}$ 是凸的，并且 $x \in cl (A), y \in relint (A)$ ，则 $[y, x) \in relint (A)$ 。

证明

设 $z = (1 - λ) x + λ y$ ，其中 $λ \in (0, 1]$ 。由于 $x \in cl (A)$ ，对于每个自然数 $k$ ，均存在 $x_{k} \in B (x, 1/ k) \cap A$ ，那么 $(x_{k}) \to x$ 。由于 $y \in relint (A)$ ，存在 $aff (A)$ 上的开球 $B (y, r) \subseteq A$ 。定义 $R^{n}$ 内的序列 $(y_{k})$ 中每个元素为 $y_{k} = [z - (1 - λ) x_{k}] / λ$ ，则 $(y_{k}) \to y$ 。因此存在 $k_{0} \in N$ 使得 $y_{k} \in B (y, r) \subseteq A$ 对所有 $k \geq k_{0}$ 成立。根据命题 10.2， $z = (1 - λ) x_{k} + λ y_{k} \in (1 - λ) x_{k} + λ B (x, 1/ k) \subseteq (1 - λ) A + λ A = A$ ，因此 $z \in relint (A)$ ，即 $[y, x) \subseteq relint (A)$ 。

定理 10.10

若 $A \subseteq R^{n}$ 是（相对）开的，则 $conv (A)$ 是（相对）开的；若 $A \subseteq R^{n}$ 是紧致的，则 $conv (A)$ 是紧致的。

证明

对于任意 $x \in conv (A)$ ，根据Carathéodory定理 10.8，存在仿射无关的点集 ${x_{0}, \dots, x_{r}} \subseteq A$ 使得 $x$ 可表示为凸组合 $\sum_{i = 0}^{r} α_{i} x_{i}$ ，其中 $r \leq n$ 。由于 $A$ 在 $aff (A)$ 上是开集，故对于每个点 $x_{i}$ ，存在开球 $B (x_{i}, r_{i}) \subseteq A$ 。取 $r = min_{i} r_{i}$ ，那么 $x_{i} + B (0, r) \subseteq A$ 对所有 $i$ 成立。对于任意 $y \in B (0, r)$ ，利用 $conv (A)$ 的凸性可知

$x + y = i = 0 \sum r α_{i} x_{i} + y = i = 0 \sum r α_{i} (x_{i} + y) \in conv (A),$
(10.3.6)

因此 $x \in x + B (0, r) \subseteq conv (A)$ ，因此 $conv (A)$ 在 $aff (A)$ 上是开集；
根据Heine-Borel定理 1.10， $A$ 是有界闭集，即存在开球 $B (x, r)$ 使得 $A \subseteq B (x, r)$ ，根据定义有 $conv (A) \subseteq B (x, r)$ ，因此 $conv (A)$ 有界；设 $dim (aff (A)) = m$ ，考虑 $conv (A)$ 内一组收敛到 $x$ 的序列 $(x_{k})$ ，根据Carathéodory定理 10.8，对于每个 $k \in N$ ，存在 $A$ 中一组点 $x_{k, 0}, \dots, x_{k, m}$ 使得

$x_{k} = α_{k, 0} x_{k, 0} + \dots + α_{k, n} x_{k, m}, where α_{k, i} \in [0, 1] and i = 0 \sum n α_{k, i} = 1.$
(10.3.7)

由于 $A \subseteq R^{n}$ 和 $[0, 1]$ 均紧致，根据Bolzano-Weierstrass定理 1.13，存在 ${α_{k, 0}}_{k \in N}$ 的一个子列收敛；在该子列中，继续寻找 ${x_{k, 0}}$ 的收敛子列；重复这样的操作 $(2 k + 2)$ 次，最后得到 $N$ 中的子列 $(k_{r})_{r \in N}$ 使得所有 ${α_{k_{r}, j}}_{r \in N}$ 和 ${x_{k_{r}, j}}_{r \in N}$ 分别收敛到 $β_{j} \in [0, 1]$ 和 $y_{j} \in A$ ，那么子列 ${\sum_{i = 0}^{m} α_{k_{r}, j} x_{k_{r}, j}}_{r \in N}$ 收敛到 $\sum_{j = 0}^{m} β_{j} y_{j}$ 。利用 $R$ 上极限的线性性和单调性（定理 1.15）， $β_{j} = lim_{r} α_{k_{r}, j} \in [0, 1]$ 对所有 $j$ 成立， $\sum_{j = 0}^{m} β_{j} = lim_{r} \sum_{j = 0}^{m} α_{k_{r}, j} = 1$ ；再利用极限的唯一性（命题 1.10）， $x = \sum_{j = 0}^{m} β_{j} y_{j} \in conv (A)$ ，因此 $conv (A)$ 也是有界闭集。根据Heine-Borel定理 1.10。

注

特别地，上述定理表明，凸多胞形 $P$ 是紧致的。

10.4支撑与分离

凸集是包含其内所有元素及其凸组合的集合。在本节中，我们考虑凸集另一种具有对偶性质的描述：凸集可从半空间的交集获得。为了得到这样的结果，所研究的凸集必须是闭集。

定理 10.11

设 $A \subseteq R^{n}$ 为非空闭凸集，那么对于每个 $x \in R^{n}$ ，存在唯一的点 $p (A, x) \in A$ 满足

∥ p (A, x) - x ∥ = y \in A in f ∥ y - x ∥ .

(10.4.1)

证明

该定理的证明思路与定理 8.1类似，区别在于定理 8.1中研究的集合同时还是子空间，因此天然是闭集。显然对于 $x \in A$ ，显然有 $p (A, x) = x$ ；对于 $x \in / A$ ，由于 $∥ y - x ∥ \geq 0$ 对任意 $y \in A$ 成立，完备性公理 1.4要求其下确界 $d = in f_{y \in A} ∥ y - x ∥$ 存在。另外，对于任意 $y \in A$ ，存在 $r > ∥ x - y ∥ > 0$ 使得 $A \cap B ˉ (x, r) \neq = \emptyset$ ，因此 $d \leq in f_{y \in A \cap B ˉ (x, r)} ∥ y - x ∥$ 。另一方面，对于任意 $ϵ > 0$ ，存在 $y_{ϵ} \in A \cap B ˉ (x, ϵ)$ 使得 $∥ y_{ϵ} - x ∥ < d + ϵ$ ，因此 $in f_{y \in A \cap B ˉ (x, r)} ∥ y - x ∥ \leq ∥ y_{ϵ} - x ∥ < d + ϵ$ 。综合上述结果， $d = in f_{y \in A \cap B ˉ (x, r)} ∥ y - x ∥$ 。根据命题 1.24， $A \cap B ˉ (x, r)$ 是有界闭集，因此根据Heine-Borel定理 1.10， $A \cap B ˉ (x, r)$ 是紧致的；再利用命题 1.18和命题 8.1， $R^{n}$ 上范数的像 $A \cap B ˉ (x, r)$ 也是紧致的。根据极值定理 1.5，存在 $y_{0} \in A \cap B ˉ (x, r)$ 使得

∥ y_{0} - x ∥ = y \in A \cap B ˉ (x, r) in f ∥ y - x ∥ = y \in A in f ∥ y - x ∥ .

(10.4.2)

最后，假设存在 $y_{1} \neq = y_{2}$ 达到该下确界 $d$ ，根据凸性有 $y_{0} = (y_{1} + y_{2}) /2 \in A$ ，那么

⟨ y_{2} - y_{0}, y_{0} - x ⟩ = \frac{1}{4} ⟨ (y_{2} - x) - (y_{1} - x), (y_{2} - x) + (y_{1} - x) ⟩ = \frac{1}{4} (∥ y_{2} - x ∥^{2} - ∥ y_{1} - x ∥^{2}) = 0.

(10.4.3)

由于 $y_{1} \neq = y_{2}$ ，我们有 $y_{2} \neq = y_{0}$ ，这意味着

∥ y_{2} - x ∥^{2} = ∥ (y_{2} - y_{0}) + (y_{0} - x) ∥^{2} = ∥ y_{2} - y_{0} ∥^{2} + ∥ y_{0} - x ∥^{2} \geq ∥ y_{0} - x ∥

(10.4.4)

与 $y_{2}$ 达到下确界矛盾，因此达到下确界的 $y_{0} = Δ p (A, x) \in A$ 唯一。

根据该定理，我们可引出度量投影的定义。

定义 10.7 （度量投影）

映射 $p (A, \cdot) : R^{n} \to A$ 称为到非空闭凸集 $A \subseteq R^{n}$ 上的度量投影（metric projection）。

注

事实上，最近邻点 $p (A, x)$ 的存在性关于所有闭集 $A$ 成立，而其唯一性则由 $A$ 的凸性保证。

定义 10.8

设 $A \subseteq R^{n}$ 是闭凸集， $E = {f = α}$ 为超平面，那么如果 $A \cap E \neq = \emptyset$ 且 $A$ 包含在两个闭半空间 ${f \leq α}$ 或 ${f \geq α}$ 之一，则称 $E$ 为 $A$ 的支撑超平面（supporting hyperplane）。包含 $A$ 且以 $A$ 的支撑超平面为边界的半空间称为 $A$ 的支撑半空间（supporting halfspace）；集合 $A \cap E$ 称为支撑集（supporting set），并且任意 $x \in A \cap E$ 称为支撑点（supporting point）。若 $E$ 是 $A$ 的支撑超平面，我们简称 $E$ 支撑 $A$ 。

例 10.2

集合 $A = {(a, b) \in R^{2} ∣ b \geq a^{- 1}, a > 0}$ 是闭凸集；直线 $g = {a + b = 2}$ 是支撑直线，但直线 ${a = 0}$ 和 ${b = 0}$ 不是。

定理 10.12

设 $A \subseteq R^{n}$ 为非空闭凸集， $x \in R^{n} \ A$ ，那么通过 $p (A, x)$ 且正交于 $x - p (A, x)$ 的超平面 $E$ 支撑 $A$ 。此外，以 $E$ 为边界且不包含 $x$ 的半空间 $H$ 是一个支撑半空间。

证明

若 $x \in E$ ，那么 $p (A, x) \in E$ 意味着其线性形式 $x - p (A, x) \in E$ ；另一方面，已知 $(x - p (A, x)) ⊥ E$ ，那么 $⟨ x - p (A, x), x - p (A, x) ⟩ = 0$ 意味着 $x = p (A, x) \in A \cap E \subseteq A$ ，矛盾。对于 $x \in / E$ ，通过内积定义线性泛函 $f : R^{n} \to R$ 为 $f (y) = ⟨ y, x - p (A, x) ⟩$ 。记 $α = ⟨ p (A, x), x - p (A, x) ⟩$ ，那么通过 $p (A, x)$ 且正交于 $x - p (A, x)$ 的向量集为 $E = {y \in R^{n} ∣ ⟨ y - p (A, x), x - p (A, x) ⟩ = 0} = {f = α}$ 。根据定理 9.1，容易验证 $E$ 是仿射封闭的，因此 $E$ 是平坦。通过Gram-Schmidt增广过程（定理 5.6），可在 $R^{n}$ 中得到一组与 $x$ 正交的标准正交集；根据定理 5.8，该集合基数为 $n - 1$ ，即 $dim (E) = n - 1$ ，因此 $E$ 是超平面。现在仅需证明 $A ⊊ H$ 。为了体现该结论的直观性，后续证明我们多通过几何图像进行说明，证明细节请读者自行补全。假设存在点 $y \in A$ 但 $y \in / H$ ，由于 $⟨ x - p (A, x), x - p (A, x) ⟩ > 0$ 且 $x \in / H$ ，可证明 $⟨ y - p (A, x), x - p (A, x) ⟩ > 0$ ；从几何上看， $x$ 与 $H$ 被 $E$ 分开，因此 $y \in / H$ 意味着 $x$ 与 $y$ 位于 $E$ 同侧，进而上述关于 $x$ 的投影点 $p (A, x)$ 的向量内积为正。设 $x$ 在通过 $p (A, x)$ 和 $y$ 上的闭线段投影为 $y ˉ$ ，当 $y ˉ$ 在 $p (A, x)$ 和 $y$ 之间时， $y ˉ \in A$ 且 $x, p (A, x)$ 与 $y ˉ$ 构成直角三角形的顶点，其中 $y ˉ$ 为垂足，因此 $∥ x - p (A, x) ∥ > ∥ x - y ˉ ∥$ ，但这与 $p (A, x)$ 的极小性矛盾；当 $y$ 在 $p (A, x)$ 与 $y ˉ$ 之间时，类似有 $∥ x - p (A, x) ∥ > ∥ x - y ∥$ ，而这同样与 $p (A, x)$ 的极小性矛盾。综上，只要 $y \in A$ 就有 $y \in H$ ，即 $A \subseteq H$ 。

推论 10.2

每个非空闭凸真子集 $A ⊊ R^{n}$ 都是所有包含 $A$ 的闭半空间的交集。更具体地， $A$ 是其所有支撑半空间的交集。

证明

由于 $A$ 包含在其任一支撑半空间内，因此其在支撑半空间的交集 $B$ 内。对于 $x \in / A$ ，根据定理 10.12，存在 $x$ 的支撑半空间 $H$ 使得 $x \in / H$ ，因此 $R^{n} \ A \subseteq R^{n} \ B$ ，即 $B \subseteq A$ 。

为了方便后续讨论，我们首先证明度量投影的连续性。

定理 10.13

设 $A \subseteq R^{n}$ 是非空凸集，那么对于任意 $x, y \in R^{n}$ ， $∥ p (A, x) - p (A, y) ∥ \leq ∥ x - y ∥$ 。

证明

若 $x \in A$ 或 $y \in A$ ，那么 $p (A, x) = x$ 或 $p (A, y) = y$ ，定理 10.12使得该不等式立即成立；若 $x \in / A$ 且 $y \in / A$ ，对于任意 $z \in R^{n}$ 定义线性泛函 $f_{x} (z) = ⟨ z - p (A, x), x - p (A, x) ⟩$ ，因此 $f_{x} (x) > 0$ ；由于 $x \in / H_{x}$ ，那么对于任意 $z \in H_{x}$ ， $f_{x} (z) \leq 0$ 。类似定义 $f_{y}$ ，从而 $p (A, x), p (A, y) \in A$ 意味着 $f_{x} (p (A, y)) \leq 0, f_{y} (p (A, x)) \leq 0$ ，因此

∥ x - y ∥^{2} = ∥ (x - p (A, x)) + (p (A, y) - y) ∥^{2} + ∥ p (A, x) - p (A, y) ∥^{2} - 2 f_{x} (p (A, y)) - 2 f_{y} (p (A, x)),

(10.4.5)

即 $∥ x - y ∥ \geq ∥ p (A, x) - p (A, y) ∥$ 对任意 $x, y \in / A$ 成立。综上，结论得证。

定理 10.14 （支撑定理）

设 $A \subseteq R^{n}$ 为闭凸集，那么通过 $A$ 的每个边界点均存在一个支撑超平面。

证明

对于任意给定的 $x \in \partial A$ 和任意自然数 $k$ ，存在 $x_{k} \in B (x, 1/ k)$ 满足 $x_{k} \in / A$ ，那么根据定理 10.13，

∥ x - p (A, x_{k}) ∥ = ∥ p (A, x) - p (A, x_{k}) ∥ \leq ∥ x - x_{k} ∥ < 1/ k,

(10.4.6)

即 $x_{k}, p (A, x_{k}) \in B (x, 1/ k) \subseteq B (x, 1)$ ，因此直观上看，存在唯一边界点 $y_{k} \in B (x, 1)$ （证明留给读者）使得 $x_{k}$ 介于 $p (A, x_{k})$ 和 $y_{k}$ 之间。对于过 $p (A, x_{k})$ 的支撑超平面 $E_{k}$ ，由于 $y_{k}$ 是 $p (A, x_{k})$ 与 $x_{k}$ 的仿射组合，根据定理 10.12， $(x - p (A, x_{k})) ⊥ E_{k}$ 等价于 $(y_{k} - p (A_{k})) ⊥ E_{k}$ 。对于超平面而言，与其正交的标准向量唯一（否则不构成极大标准正交集），因此 $p (A, y_{k}) = p (A, x_{k})$ 。根据Bolzano-Weierstrass定理 1.13，实数列 $(y_{k})$ 存在收敛到某个 $y$ 的子列 $(y_{k_{r}})_{r \in N}$ ；利用度量投影的连续性（定理 10.13）， $p (A, y_{k_{r}}) \to p (A, y)$ ，并且 $p (A, y_{k_{r}}) = p (A, x_{k_{r}}) \to p (A, x) = x$ ；由极限的唯一性（命题 1.10）， $x = p (A, y)$ 。结合范数的连续性（命题 8.1）， $∥ y - x ∥ = lim_{r} ∥ y_{k_{r}} - x ∥ = 1$ ，因此 $x \neq = y$ 。换言之，存在 $y \in / A$ 使得 $x = p (A, y)$ ，即过 $x$ 存在于 $y - p (A, y)$ 正交的支撑超平面，结论得证。

定义 10.9 （分离与真分离）

对于两个集合 $A, B \subseteq R^{n}$ 和超平面 $E = {f = α}$ ，若 $A \subseteq {f \leq α}, B \subseteq {f \geq α}$ 或 $A \subseteq {f \leq α}, B \subseteq {f \leq α}$ 两者之一成立，则称 $E$ 分离（seperate） $A$ 和 $B$ 。若存在分离超平面不同时包含 $A$ 和 $B$ ，则称凸集 $A$ 和 $B$ 可被真分离（properly seperate）。

定理定理 10.12说明闭凸集 $A$ 和点 $x \in / A$ 可被超平面分离（甚至存在一个与 $A$ 和 $x$ 都要正距离的分离超平面）。这一结果可推广到紧凸集 $B$ 而不仅仅是单点集 ${x}$ 上。此外，支撑定理 10.14表明对于 $A$ 的每个边界点，都存在一个超平面使其与 $A$ 分离。分离定理则提供了两个非空凸集真分离的充要条件。

定理 10.15 （分离定理）

设 $A, B \subseteq R^{n}$ 为 $R^{n}$ 中的非空凸集，则 $relint (A) \cap relint (B) = \emptyset$ 当且仅当 $A$ 和 $B$ 可被真分离。

结合该定理之前的一小段讨论，我们已经能接受该结论在直观上的正确性。有鉴于此，我们在这里仅给出结果，不再对其进行严格证明。如果对详细的推导有兴趣，请参见^[2]。以下推论同样仅给出结果

推论 10.3 （强分离）

设 $A, B \subseteq R^{n}$ 是凸集，此外 $A$ 是闭集、 $B$ 是紧致集，并且 $A \cap B = \emptyset$ ，则存在超平面 ${f = γ}$ 和 $ϵ > 0$ 使得 $A \subseteq {f \geq γ + ϵ}$ 且 $B \subseteq {f \leq γ - ϵ}$ 。此时称 $A$ 和 $B$ 被超平面 ${f = γ}$ 强分离（strongly seperate）。

注

注意这里紧致性的要求是必须的，这是为了防止 $A$ 和 $B$ 在渐近情形不可强分离。例如 $A = {(x, y) \in R^{2} : y ⩾ e^{x}}$ 和 $B = {(x, y) : y ⩽ 0}$ 均为非空闭凸集，但只存在分离直线 ${(x, y) : y = 0}$ ，不存在可强分离的直线。

在本节的最后，我们讨论凸多胞形与多面体集的等价性。我们先从支撑集的维数特征入手。

定义 10.10 （边和面）

若闭凸集 $A \subseteq R^{n}$ 的支撑集 $F$ 的维数 $dim (F) = k \in {0, \dots, n - 1}$ ，则称其为 $k$ -支撑集（ $k$ -support）。 $A$ 的1-支撑集称为边（edge）， $(n - 1)$ -支撑集称为（facet）；有时也称 $A$ 的 $(dim (A) - 1)$ -支撑集为 $A$ 的面。

定理 10.16

多胞形 $P \subseteq R^{n}$ 的0-支撑集恰好是单点集 ${x}$ ，其中 $x \in vert (P)$ 。

证明

对于充分性，存在支撑超平面 ${f = β}$ 使得 $P \subseteq {f \leq β}$ 且 $P \cap {f = β} = {x}$ 。由于开半平面是凸集，故 $P \ {x} = P \cap {f < β}$ 也是凸集，因此 $x \in ∣ (P)$ 。反之设 $vert (P) \ {x} = {x_{1}, \dots, x_{k}} (k \geq 1)$ 。那么根据定理 10.4， $x \in / conv {x_{1}, \dots, x_{k}} = Δ Q$ 。假设 $x_{1} \in conv {x_{2}, \dots, x_{k}}$ ，那么 $x_{1}$ 不是 $P$ 的顶点，矛盾。因此 ${x_{1}, \dots, x_{k}} \subseteq vert (Q)$ 。若存在 $x \in vert (Q) \ {x_{1}, \dots, x_{k}}$ ，则 $x \in / conv {x_{1}, \dots, x_{k}} = Q$ ，矛盾。综上， $vert (Q) = conv {x_{1}, \dots, x_{k}}$ ，进而 $Q$ 也是闭凸集。根据定理 1.14，存在通过 $p (Q, x)$ 且正交于 $x - p (Q, x)$ 的支撑超平面 ${f = α}$ 且 $Q \subseteq {f \leq α}$ ，同时记 $β = f (x) > α$ 。设 $y \in P$ ，那么存在 $α_{i} \in [0, 1]$ 满足 $\sum_{i = 1}^{k + 1} α_{i} = 1$ ，使得

y = i = 1 \sum k α_{i} x_{i} + α_{k + 1} x ⟹ f (y) = i = 1 \sum k α_{i} f (x_{i}) + α_{k + 1} f (x) \leq i = 1 \sum k α_{i} α + α_{k + 1} β \leq β,

(10.4.7)

等号成立当且仅当 $α_{k + 1} = 1$ ，即 $y = x$ 。因此 ${f \leq β}$ 是支撑半空间，且 $P \cap {f = β} = {x}$ ，可见 ${x}$ 是 $P$ 的一个0-支撑集。

注

出于这种考虑，后面我们不再严格区分0-支撑集和顶点，尽管前者是单点集、后者单纯是点。

定理 10.17

设 $P \subseteq R^{n}$ 是具有顶点 $vert (P) = {x_{1}, \dots, x_{k}}$ 的多胞形， $F$ 是 $P$ 的支撑集，则 $F = conv {x_{i} ∣ x_{i} \in F}$ 。

证明

设 $F = P \cap {f = α}$ 且 $P \subseteq {f \leq α}$ 。假设不存在 $x_{i} \in F$ ，即 $f (x_{i}) < α$ 对所有 $i$ 成立；那么对于任意 $x \in P$ ，其凸组合 $\sum_{i = 1}^{k} α_{i} x_{i}$ 满足 $f (x) = \sum_{i = 1}^{k} α_{i} f (x_{i}) < α$ ，即 $F = P \cap {f = α} = \emptyset$ ，这与支撑定理 10.14矛盾。因此恰当重排指标后，存在某个 $m \in {1, \dots, k}$ 使得 $x_{1}, \dots, x_{m} \in F$ ，并且 $x_{m + 1}, \dots, x_{k} \in / F$ 。不妨设 $f (x_{i}) = α - δ_{i} (i = m + 1, \dots, k)$ ，其中 $δ_{i} > 0$ 。对于任意 $x \in P$ ，其凸组合 $\sum_{i = 1}^{k} α_{i} x_{i}$ 满足 $f (x) = \sum_{i = 1}^{m} α_{i} f (x_{i}) = α - \sum_{i = m + 1}^{k} α_{i} δ_{i} \leq α$ ，等号成立当且仅当 $α_{i} = 0$ 对所有 $i = m + 1, \dots, k$ 成立。因此 $F = conv {x_{1}, \dots, x_{m}} = conv {x_{i} ∣ x_{i} \in F}$ 。

注

特别地，上述定理表明，多胞形 $P$ 的支撑集也是由 $vert (P)$ 组成的多胞形，因此 $P$ 只存在有限多支撑集。

综合以上分析，我们最终可以得到多胞形是多面体集这一重要结论。考虑到其严格推导较为冗杂，这里我们仅了解定理内容，对证明感兴趣的读者可参见^[2]。

定理 10.18

每个多胞形 $P \subseteq R^{n}$ 都是多面体集。

10.5极值表示

在先前的内容中，我们已经看到闭凸集 $A \subseteq R^{n}$ 存在一种平凡表示： $A$ 是所有包含 $A$ 的闭凸集的交集，即 $A = conv (A)$ ；该表示可改进为一种非平凡表示： $A$ 是所有 $A$ 的支撑半空间的交集。因此，讨论如何寻找一个尽可能小的真子集 $B \subseteq A$ 使得 $A = conv (B)$ 是很自然的，而这是一个非平凡问题。尽管存在一些关于一般闭凸集的普遍结果，我们还是仅将注意力放在紧致情形，此时我们可以得到该问题的一个简单解。

定义 10.11 （极值点）

设 $A \subseteq R^{n}$ 是闭凸集，若点 $x \in A$ 不能表示为 $A$ 中点的非平凡凸组合，即对于 $y, z \in A$ 和 $α (0, 1)$ ， $x = α y + (1 - α) z$ 必然给出 $x = y = z$ ，则称其为 $A$ 的极值点（extreme point）。 $A$ 中所有极值点的集合记为 $ext (A)$ 。

注

为了对极值点有直观理解，容易证明 $ext (A) \neq = \emptyset$ 当且仅当集合 $A \subseteq R^{n}$ 不包含任意直线（参见笔记《Convex Geometry》）。特别地，若 $A$ 是闭半空间且 $n \geq 2$ ，则 $ext (A) = \emptyset$ 。

命题 10.7

若 ${x}$ 是 $A$ 的一个支撑集，则 $x \in ext (A)$ 。

证明

设 ${x} = A \cap {f = β}$ 且 $A \subseteq {f \leq β}$ ，并且存在 $y, z \in A$ 使得 $x = α y + (1 - α) z$ 对某个 $α \in (0, 1)$ 成立。那么 $f (x) = α f (y) + (1 - α) f (z) \leq β$ ，等号成立当且仅当 $f (y) = f (z) = η$ ，即 $y, z \in A \cap {f = β} = {x}$ 。因此 $y = z = x$ ，这意味着 $x \in ext (A)$ 。

注

反之该结论并不成立。考虑类似400米跑道的图形围成的闭凸集，那么从“直道”到“弯道”的曲率变化点是极值点，但它不是支撑集。这引出了如下定义。

定义 10.12 （暴露点）

设 $A \subseteq R^{n}$ 为闭凸集，若点 $x \in A$ 构成的单点集 ${x}$ 是 $A$ 的一个0-支撑集，则称其为暴露点（exposed point）。 $A$ 的暴露点集合记为 $exp (A)$ 。

注

根据命题 10.7， $exp (A) \subseteq ext (A)$ 。

命题 10.8

对于凸集 $A$ 内的点 $x$ ， $x \in ext (A)$ 当且仅当 $A \ {x}$ 是凸集。

证明

对于充分性，考虑任意 $y, z \in A \ {x}$ ，假设存在 $α \in [0, 1]$ 使得 $x = α y + (1 - α) z$ 。根据定义， $α \in (0, 1)$ 时 $y = z = x$ ； $α = 0$ 和1时分别有 $z = x$ 和 $y = x$ 。以上情况均与 $y, z \in A \ {x}$ 矛盾，因此 $y, z$ 的任意凸组合在 $A \ {x}$ 内，即 $A \ {x}$ 为凸集；反之若存在 $y, z \in A$ 和 $α \in (0, 1)$ 使得 $x = α y + (1 - α) z$ ，假设 $y, z \in A \ {x}$ ，那么 $A \ {x}$ 的凸性要求 $x \in A \ {x}$ ，矛盾。因此 $y$ 和 $z$ 中至少有一个等于 $x$ ，进而 $y = z = x$ ，故 $x \in ext (A)$ 。

根据此结论，对于多胞形 $P$ ，其顶点恰好为极值点，即 $vert (P) = ext (P)$ 。因此根据定理 10.4， $P = conv (vert (P))$ $= conv (ext (P))$ 。尽管对于一般的凸紧集 $K$ ，前者通常不成立，但 $K = conv (K)$ 仍成立。

定理 10.19 （Minkowski定理）

设 $K \subseteq R^{n}$ 是凸紧集， $A \subseteq K$ ，则 $K = conv (A)$ 当且仅当 $ext (K) \subseteq A$ 。特别地， $K = conv (ext (K))$ 。

证明

首先 $A \subseteq K$ 自然给出 $conv (A) \subseteq K$ ，因此仅需证明反向包含。若 $K \subseteq conv (A)$ ，那么对于任意 $x \in ext (K) \subseteq K$ ，存在凸组合 $x = α y + (1 - α) z$ ，其中 $y, z \in A$ 。假设存在 $x \in / A$ ，那么 $α \in (0, 1)$ ，极值点的定义要求 $x = y = z \in A$ ，矛盾。因此 $ext (K) \subseteq A$ ；反之若 $ext (K) \subseteq A$ ，对 $n$ 采用归纳假设证明该结论。当 $n = 1$ 时，由于 $K$ 紧致，根据极值定理 1.5，存在 $a, b \in K$ 使得 $a = in f (K)$ 且 $b = sup (K)$ ，因此 $a \leq x \leq b$ 对任意 $x \in K$ 成立。容易证明 $a, b \in ext (K)$ ，因此 $K \subseteq [a, b] \subseteq ext (K) \subseteq A \subseteq conv (A)$ 。假设结论在 $R^{n - 1}$ 上成立，考虑 $x \in K$ 和任意过 $x$ 的直线 $g$ 。由于 $K$ 紧致，根据Heine-Borel定理 1.10， $K$ 为有界闭集，因此 $g \cap K$ 有界；对于 $g \cap K$ 内任意收敛到 $x$ 的序列 $(x_{n})$ ，首先 $x \in K$ ；利用收敛的线性性定理 1.15， $x \in g$ ，进而 $g \cap K$ 也是有界闭集。根据极值定理 1.5，存在 $y, z \in g \cap K$ 使其在 $g$ 上关于给定的 $x_{1}, x_{2} \in g$ 的仿射组合系数分别取最小值和最大值，因此 $g \cap K \subseteq [y, z]$ ； $g \cap K$ 的凸性要求 $[y, z] \subseteq g \cap K$ ，因此 $g \cap K = [y, z]$ ，并且容易证明 $y, z \in \partial K$ 。因此根据支撑定理 10.14， $y, z$ 为支撑点，相应的支撑超平面分别记为 $E_{y}$ 和 $E_{z}$ ，则 $y \in K \cap E_{y} = Δ K_{1}$ 且 $z \in K \cap E_{z} = Δ K_{2}$ ，其中 $dim (E_{y}) = dim (E_{z}) = n - 1$ 。根据归纳假设，凸紧集 $K_{1} = conv (ext (K_{1}))$ 且 $K_{2} = conv (ext (K_{2}))$ 。对于任意 $x^{'} \in ext (K_{1})$ ，若存在 $y^{'}, z^{'} \in K_{1}$ 和 $α \in (0, 1)$ 使得 $x^{'} = α y^{'} + (1 - α) z^{'}$ ，假设 $y^{'}$ 和 $z^{'}$ 至少有一个不在 $K \ K_{1}$ 内。不妨设 $y^{'} \in K \ K_{1} = K \cap E_{y}^{c}$ ，利用超平面的线性容易证明 $x^{'} \in K \cap E_{y}^{c}$ ，矛盾。因此 $y^{'}, z^{'} \in K_{1}$ ，进而极值点的定义要求 $x^{'} = y^{'} = z^{'}$ ，这意味着 $ext (K_{1}) \subseteq ext (K)$ ；类似地 $ext (K_{2}) \subseteq ext (K)$ 。注意到 $K_{1}$ 可表示为 $ext (K_{1})$ 的凸组合，因此可表示为 $ext (K_{1}) \cup ext (K_{2}) \subseteq ext (K)$ 的凸组合，即 $K_{1} \subseteq conv (ext (K))$ ；类似地 $K_{2} \subseteq conv (ext (K))$ ，进而

x \in [y, z] = conv {y, z} \subseteq conv (K_{1} \cup K_{2}) \subseteq conv (ext (K)) \subseteq conv (A) \subseteq conv (K) = K .

(10.5.1)

利用 $x \in K$ 的任意性，此时 $K = conv (A) = conv (ext (K))$ 。因此对于任意自然数 $n$ ，该结论成立。

推论 10.4

设 $P \subseteq R^{n}$ 是凸紧集，则 $P$ 是多胞形当且仅当 $ext (P)$ 有限。

证明

若 $P$ 为多胞形，根据命题 10.8后的讨论， $ext (P)$ 有限；反之若 $ext (P)$ 有限，根据定理 10.19， $K = conv (ext (P))$ 是有限多个点的凸包，因此 $K$ 为多胞形。

有了上述结果，现在我们可以补充定理 10.18的反向结论，从而证明多胞形与有界多面体集的等价性。

定理 10.20

设 $P \subseteq R^{n}$ 为有界多面体集，则 $P$ 是多胞形。

证明

显然 $P$ 是凸紧集，根据推论 10.4，此时仅需证明 $ext (P)$ 有限。设 $x \in ext (P)$ ，并且 $P = \cap_{i = 1}^{k} H_{i}$ ，其中 $H_{i}$ 是以超平面 $E_{i}$ 为边界的闭半空间。考虑凸集

D = i = 1 ⋂ k A_{i}, where A_{i} = {E_{i}, relint (H_{i}), if x \in E_{i}, if x \in / E_{i} .

(10.5.2)

若 $x \in \cap_{i = 1}^{k} E_{i}$ ，那么根据定理 9.3， $D$ 也是仿射子空间。假设存在不同于 $x$ 的点 $y \in D$ ，则其仿射组合也在 $D$ 内。结合极值点定义 10.11后的讨论，此时 $ext (P) = \emptyset$ ，矛盾。因此 $D = {x}$ ；若存在 $A_{i} = relint (H_{i})$ ，那么 $E_{i} \cap relint (H_{j})$ 与 $relint (H_{i}) \cap relint (H_{j})$ 是相对开的，进而 $D$ 是相对开的。假设 $dim (D) > 0$ ，则在 $aff (D)$ 上存在 $B (x, ϵ) \subseteq D$ ，设 $B ˉ (x, ϵ /2)$ 与通过 $x$ 的直线相交于 $y, z$ ，则 $x = (y + z) /2$ ，这与 $x \in ext (P)$ 矛盾。因此无论在上述何种情况下，均有 $D = {x}$ 。由于 $D$ 的可能数目有限（不超过 $2^{k}$ ）， $ext (P)$ 也有限，结论得证。

推论 10.5

有限多个多胞形的交集仍为多胞形。

最后，在Minkowski定理 10.19中，若将 $ext (K)$ 替换为 $exp (K)$ ，则结论通常不成立。即使在平面中，凸紧集的暴露点集的凸包也未必紧致；不过该凸包的闭包可还原为 $K$ 。

定理 10.21

设 $K \subseteq R^{n}$ 是凸紧集，则 $K = cl (conv (exp (K)))$ 。

证明

假设 $K$ 不是单点集。由于 $K$ 紧致，根据极值定理 1.5和命题 8.1，对于每个 $x \in R^{n}$ ，存在 $y_{x} \in K$ 使得 $∥ y_{x} - x ∥ = sup_{y \in K} ∥ y - x ∥$ 。若 $y_{x} \in relint (K)$ ，则存在 $aff (K)$ 上的 $B (y, ϵ) \subseteq K$ 。那么存在不同于 $y$ 的 $y_{ϵ} \in B (x, ϵ)$ ，使得 $y_{x}$ 是 $y_{ε}$ 和 $x$ 的凸组合，从而 $∥ y_{ϵ} - x ∥ > ∥ y_{x} - x ∥$ ，这与 $y_{x}$ 的极大性矛盾。因此 $y_{x} \in \partial K$ 。对于通过 $y_{x}$ 且与 $y_{x} - x$ 正交的超平面 $E$ ，若存在其他的 $y \in E \cap K$ ，那么

∥ x - y ∥^{2} = ∥ (x - y_{x}) + (y_{x} - y) ∥^{2} = ∥ x - y_{x} ∥^{2} + ∥ y_{x} - y ∥^{2} > ∥ x - y_{x} ∥^{2},

(10.5.3)

这与 $y_{x}$ 的极大性矛盾，因此 $E \cap K = {y_{x}}$ ，进而 $E$ 是 $K$ 的支撑超平面，故 $y_{x} \in exp (K)$ 。根据前述分析， ${y_{x} ∣ x \in R^{n}} \subseteq exp (K) \subseteq K$ ，因此 $K^= Δ cl ({y_{x} ∣ x \in R^{n}}) \subseteq K$ 。由于 $K$ 紧致且 $K^$ 有界，根据Heine-Borel定理 1.10， $K^$ 紧致。后续证明稍微有些琐碎，易懂但书写较为麻烦，故再次略去，详见^[2]。

集合 $A$ 的相对内部 $relint (A)$ 定义为将 $aff (A)$ 的基底子空间视为整个向量空间时 $A$ 的内部