Chapter 2 凸集
2.1 仿射集和凸集
2.1.1 直线和线段
假设 \(x_1\neq x_2\) 是 \(\mathbb{R}^n\) 上的两个点。那么如下形式的点
\[ y=\theta x_1+(1-\theta)x_2 \]
其中 \(\theta\in\mathbb{R}\)，构成了 \(x_1\) 和 \(x_2\) 之间的一条直线。假如 \(\theta=0\)，那么 \(y=x_2\)；如果 \(\theta=1\)，就有 \(y=x_1\)。
如果用另外一种方法表示 \(y\)
\[ y=x_2+\theta(x_1-x_2) \]
则有另外一种理解方式：\(y\) 是基点 \(x_2\) 和方向向量 \(x_1-x_2\)（从 \(x_2\) 指向 \(x_1\)）的 \(\theta\) 倍的加和。因此，\(\theta\) 反映了 \(y\) 在 \(x_1\) 和 \(x_2\) 之间的位置。随着 \(\theta\) 从 \(0\) 到 \(1\) 变化，\(y\) 从 \(x_2\) 逐渐向 \(x_1\) 移动；对于 \(\theta > 1\) 的情况，\(y\) 会在 \(x_1\) 外边的射线上。（如图）
2.1.2 仿射集
如果通过集合 \(C\) 中任意两点的直线都在 \(C\) 中，那么集合 \(C\) 就是仿射集，也就是说，对于任意 \(x_1,x_2\in C\) 和 \(\theta\in\mathbb{R}\)，都有 \(y=\theta x_1+(1-\theta)x_2\in C\)。换句话说，\(C\) 包含了 \(C\) 中任意两点的线性组合，且线性系数之和为 \(1\)。
这种想法可以推广到多个点上。比如我们有一个点，满足 \(\sum_{i=1}^k \theta_ix_i\)，其中 \(\sum_{i=1}^k \theta_i=1\)。这个点就是 \(x_1,\cdots,x_k\) 的仿射组合。从仿射集的定义归纳下来的话（即仿射集包括其中任意两点的仿射组合），一个仿射集包含每个其中点的仿射组合：如果 \(C\) 是一个仿射集，那么对于任意 \(x_1,\cdots,x_k\in C\)，都有 \(\sum_{i=1}^k \theta_ix_i\in C\)，其中 \(\sum_{i=1}^k \theta_i=1\)。
如果 \(C\) 是一个仿射集，且 \(x_0\in C\)，则集合
\[ V=C-x_0=\{x-x_0\mid x\in C\} \]
是一个子空间（即加法和数乘封闭）。为了证明这一点，假设 \(v_1,v_2\in V\)，\(\alpha,\beta\in\mathbb{R}\)。那么我们有 \(v_1+x_0\in C\)，\(v_2+x_0\in C\)，因此
\[ \alpha v_1+\beta v_2+x_0=\alpha v_1+\beta v_2+(1-\alpha-\beta)x_0=\alpha(v_1+x_0)+\beta(v_2+x_0)+(1-\alpha-\beta)x_0\in C \]
因为 \(C\) 是仿射集，并且 \(\alpha+\beta+(1-\alpha-\beta)=1\)。因此，我们得到了 \(\alpha v_1+\beta v_2\in V\)，因为 \(\alpha v_1+\beta v_2+x_0\in C\)。
因此，仿射集 \(C\) 可以表达成
\[ C=V+x_0=\{v+x_0\mid v\in V\} \]
即一个子空间加上一个偏差量的形式。子空间 \(V\) 以不取决于 \(x_0\) 取值的情况与仿射集 \(C\) 产生关联，因此 \(x_0\) 可以选取为 \(C\) 中的任意点。因此，我们可以定义仿射集 \(C\) 的维度为子空间 \(V=C-x_0\) 的维度，其中 \(x_0\) 是 \(C\) 中的任意元素。
Example 2.1 (线性方程组的解集) 线性方程组的解集 \(C=\{x\mid Ax=b\}\)（其中 \(A \in \mathbb{R}^{m\times n}\)，\(b \in \mathbb{R}^m\)）是一个仿射集，为了证明，假设 \(x_1,x_2\in C\)，那么 \(Ax_1=b\)，\(Ax_2=b\)。对于任意 \(\theta\)，我们有
\[ \begin{align} A(\theta x_1+(1-\theta)x_2)&=\theta Ax_1+(1-\theta)Ax_2 \\ &=\theta b+(1-\theta)b \\ &=b \end{align} \]
这表明了仿射组合 \(\theta x_1+(1-\theta)x_2\) 也是 \(C\) 的一个元素。和仿射集 \(C\) 相关联的子空间 \(V\) 是 \(A\) 的零空间。
总之我们可以说，每个仿射集都可以表达成线性方程组的解集。
包括一个 \(C \subseteq \mathbb{R}\) 的所有点的仿射组合的集合称为 \(C\) 的仿射包，记作 \(\operatorname{aff}C\)：
\[ \operatorname{aff}C=\{\sum_{i=1}^k \theta_ix_i\mid x_1,\ldots,x_k\in C,\sum_{i=1}^k\theta_i=1\} \]
\(C\) 的仿射包是包含 \(C\) 的最小仿射集。如果 \(S\) 是一个仿射集，且 \(C\subseteq S\)，那么 \(\operatorname{aff}C\subseteq S\)。
2.1.3 仿射维数和相对内部
我们定义一个集合 \(C\) 的仿射维数为 \(\operatorname{aff}C\) 的维数。仿射维数在凸分析和凸优化中比较有用，但是它和其他领域中维数的定义并不一样。例如，考虑一个 \(\mathbb{R}^2\) 上的单位圆，即 \(\{x\in\mathbb{R}^2\mid x_1^2+x_2^2=1\}\)。它的仿射包为 \(\mathbb{R}^2\)，因此它的仿射维数为 2。但是在通常意义上，一个 \(\mathbb{R}^2\) 上的圆的维数为 1。
如果一个集合 \(C\subseteq\mathbb{R}^n\) 的仿射维数小于 \(n\)，那么这个集合的仿射集 \(\operatorname{aff}C\neq \mathbb{R}^n\)。因此，我们可以定义一个集合 \(C\) 的相对内部（记作 \(\operatorname{relint}C\)，表示相对 \(\operatorname{aff}C\) 的内部）为：
\[ \operatorname{relint}C=\{x\in\mathbb{R}^n\mid B(x,r)\cap\operatorname{aff}C\subseteq C \mathrm{\;for\,some\,} r>0\} \]
其中 \(B(x,r)=\{y\in\mathbb{R}^n\mid \Vert y-x\Vert\leq r\}\) 是在范数 \(\Vert\cdot\Vert\)（这里 \(\Vert\cdot\Vert\) 为任意范数，所有范数都会定义相同的相对内部）下以 \(x\) 为中心半径为 \(r\) 的球体。进而我们定义 \(C\) 的相对边界为 \(\operatorname{cl}C \setminus \operatorname{relint}C\)，其中 \(\operatorname{cl}C\) 为 \(C\) 的闭包。
Example 2.2 考虑到一个 \(\mathbb{R}^3\) 上 \((x_1, x_2)\) 平面的一个正方形，如下定义：
\[ C=\{x\in\mathbb{R}^3\mid -1\leq x_1\leq 1,-1\leq x_2\leq 1, x_3=0\} \]
其仿射包为整个 \((x_1, x_2)\) 平面，即 \(\operatorname{aff}C=\{x\in\mathbb{R}^3\mid x_3=0\}\)。因此 \(C\) 的相对内部为 \(\operatorname{relint}C=\{x\in\mathbb{R}^3\mid x_3=0\}\)，而相对边界为 \(\operatorname{cl}C \setminus \operatorname{relint}C=\{x\in\mathbb{R}^3\mid x_3\neq 0\}\)。\(C\) 的内部为空集，但是其相对内部为
\[ \operatorname{relint}C=\{x\in\mathbb{R}^3\mid -1< x_1 < 1, -1 < x_2 < 1, x_3=0\} \]
其在 \(\mathbb{R}^3\) 上的边界为其自身其相对边界为
\[ \{x\in\mathbb{R}^3\mid \max\{|x_1|,|x_2|\}=1, x_3=0\} \]
2.1.4 凸集
如果连接一个集合 \(C\) 中任意两点的线段仍在 \(C\) 中，那么我们称 \(C\) 是凸集，也就是说，对于任意的 \(x_1, x_2\in C\) 以及任意 \(0\leq\theta\leq 1\)，都有
\[ \theta x_1+(1-\theta)x_2\in C \]
通俗地说，如果一个集合中任意一点都能被另外任意一点“看见”（光沿直线传播？），这个集合就是凸集。所有仿射集都是凸集，因为仿射集一定包含了连接其中任意两点的线段。如图。
我们将 \(\sum_{i=1}^k \theta_ix_i, \sum_{i=1}^k\theta_i=1, \theta_i\geq 0\) 称为 \(C\) 的凸组合。和仿射集一样，一个集合为凸集当且仅当其所有凸组合都在集合中。凸组合其实可以被看作为几个点的混合或加权平均。
一个集合 \(C\) 的凸包（记作 \(\operatorname{conv}C\)）是集合 \(C\) 的所有点的凸组合组成的集合：
\[ \operatorname{conv}C=\{\sum_{i=1}^k \theta_ix_i\mid \sum_{i=1}^k\theta_i=1, \theta_i\geq 0, x_i\in C\} \]
顾名思义，凸包永远是凸的。它是包含集合 \(C\) 的最小凸集。如果集合 \(B\) 是包含集合 \(C\) 的凸集，那么 \(\operatorname{conv}C\subseteq B\)。如图。
凸组合的概念可以推广到级数、积分或者概率分布等等。假设 \(\theta_1, \theta_2\) 满足：
\[ \theta_i\geq0,\quad i=1,2\cdots,\quad\sum_{i=1}^\infty\theta_i=1 \]
并且 \(x_1, x_2, \cdots \in C\) 且 \(C\subseteq \mathbb{R}^n\) 是凸集，那么（如果级数收敛的话）
\[ \sum_{i=1}^\infty\theta_ix_i\in C \]
更广义地来讲，假设映射 \(p: \mathbb{R}^n\to\mathbb{R}\) 满足对于 \(\forall x\in C\) 且 \(\int_C p(x)\mathrm{d}x=1\)，其中 \(C\subseteq\mathbb{R}^n\) 是凸集，那么（如果积分存在的话）
\[ \int_C p(x)x\mathrm{d}x\in C \]
更通常的情况下，假设 \(C\subseteq\mathbb{R}^n\) 是凸集且 \(x\in C\) 是一个随机向量，则有 \(\boldsymbol{E}x\in C\)。当然有一些特殊情况，比如 \(x\) 服从 Bernoulli 分布，即 \(P(x=x_1)=\theta, P(x=x_2)=1-\theta\)，我们就回到了最开始的两点问题。
2.1.5 锥
如果一个集合 \(C\) 对于 \(\forall x\in C,\theta\geq 0\) 都有 \(\theta x\in C\)，则称 \(C\) 为一个锥。而如果集合 \(C\) 既是凸集又是一个锥，则称集合 \(C\) 为凸锥，意味着对于 \(\forall x_1, x_2\in C, \theta_1, \theta_2\geq 0\)，我们有：
\[ \theta_1x_1+\theta_2x_2\in C \]
通过这种形式表出的点在几何上可以描述为形成顶点为 \(0\)，边界穿过 \(x_1, x_2\) 的二维饼片。（如图）
满足形式 \(\sum_{i=1}^k \theta_i x_i, \theta_i\geq 0\) 的点称作 \(x_1, \cdots, x_k\) 的锥组合（或非负线性组合）。如果一个点 \(x_i\) 在凸集 \(C\) 中，那么 \(x_i\) 的所有锥组合都在 \(C\) 中。相反地，一个集合 \(C\) 为一个凸锥当且仅当其包含其元素所有的锥组合。类似凸组合，锥组合的思想也可以推广到级数和积分上。
集合 \(C\) 的锥包是 \(C\) 所有元素的凸组合，即
\[ \{\sum_{i=1}^k\theta_ix_i\mid x_i\in c,\theta_i\geq0,i=1,\ldots,k\} \]
其也是包含集合 \(C\) 的最小凸锥。（如图）
2.2 一些重要的例子
在这一节中，我们将会讲述本书中我们会遇到的几种重要的凸集。我们先从几个简单容易理解的例子开始。
- 空集 \(\emptyset\)、任意一个孤立的点 \(\{x_0\}\)、整个 \(\mathbb{R}^n\) 空间都是 \(\mathbb{R}^n\) 的仿射（都仿射了，肯定是凸的）子集。
- 任意一条直线一定是仿射的。如果它穿过零点，它就是一个子空间，也是一个凸锥。
- 一条线段一定是凸的，但是除非它缩小到一个点，否则它不仿射。
- 一条射线，拥有 \(\{x_0+\theta v\mid\theta\geq 0, v\neq 0\}\) 的形式，是凸的，但是不仿射。如果它穿过零点，它就是一个凸锥。
- 所有子空间既仿射又是凸锥。
2.2.1 超平面和半空间
一个超平面具有如下形式：
\[ \{x\in\mathbb{R}^n\mid a^Tx=b\} \]
其中 \(a\in\mathbb{R}, a\neq 0, b\in\mathbb{R}\)。从代数上来讲，这是非奇异线性方程组 \(a^Tx=b\) 的解集，因此是一个仿射集。从几何上来讲，超平面 \(\{x\mid a^Tx=b\}\) 可以表达成一个常量和给定向量 \(a\) 的内积组成的点集；常量 \(b\in\mathbb{R}\) 表示了和原超平面的偏差。这种几何表达法可以通过这种形式方便理解：
\[ \{x\mid a^T(x-x_0)=0\} \]
其中 \(x_0\) 是超平面上任意一个点（即任意一个满足 \(a^Tx_0=b\) 的点）。这种形式可以写成：
\[ \{x\mid a^T(x-x_0)=0\}=x_0+a^\perp \]
其中 \(a^\perp\) 是 \(a\) 的正交补（即其中所有的向量都与 \(a\) 正交）：
\[ a^\perp=\{v\mid a^Tv=0\} \]
这种几何的表达形式（如图所示）：
超平面将 \(\mathbb{R}^n\) 空间分成两个半空间。一个（闭）半空间是一种满足如下形式的集合：
\[ \{x\mid a^Tx\leq b\} \]
其中 \(a\neq 0\)，即非奇异线性不等式组的解集。半空间是凸的，但是不仿射。（如图）
半空间同样可以表达成这样的形式：
\[ \{x\mid a^T(x-x_0)\leq 0\} \]
其中 \(x_0\) 是相关超平面上任意一个点（即任意一个满足 \(a^Tx_0=b\) 的点）。（？）
半空间（哪个？）的边界为超平面 \(\{x\mid a^Tx=b\}\)。半空间 \(\{x\mid a^Tx\leq b\}\) 的内部 \(\{x\mid a^Tx< b\}\) 被称作开半空间。
2.2.2 Euclidean 球和椭球
在 \(\mathbb{R}^n\) 空间中 Euclidean 球（或者简而言之地称作球）是一种满足如下形式的集合：
\[ B(x_c, r)=\{x\mid \Vert x-x_c\Vert_2\leq r\}=\{x\mid(x-x_c)^T(x-x_c)\leq r^2\}, \]
其中 \(r>0\)，\(\Vert\cdot\Vert_2\) 代表 Euclidean 范数，即 \(\Vert x\Vert_2=(x^Tx)^{1/2}\)。向量 \(x_c\) 代表球心，标量 \(r\) 是其半径；\(B(x_c, r)\) 包含了所有距离球心 \(x_c\) 不超过 \(r\) 的点。Euclidean 的另外一种常用表达形式是：
\[ B(x_c, r)=\{x_c+ru\mid \Vert u\Vert_2\leq 1\} \]
Euclidean 球是一个凸集：
如果 \(\Vert x_1-x_c\Vert_2\leq r\)，\(\Vert x_2-x_c\Vert_2\leq r\) 以及 \(0\leq\theta\leq 1\)，则有：
\[ \begin{align} \Vert\theta x_1+(1-\theta)x_2-x_c\Vert_2&=\Vert\theta(x_1-x_c)+(1-\theta)(x_2-x_c)\Vert_2\\ &\leq\theta\Vert x_1-x_c\Vert_2+(1-\theta)\Vert x_2-x_c\Vert_2\\ &\leq r. \end{align} \]
（这里我们用到了 \(\Vert\cdot\Vert_2\) 的齐次性和三角不等式）
还有一种类似的凸集是椭球，它是一种满足如下形式的集合：
$$