一、凸集相关的定义

1. 凸集的定义

【凸集的定义】对于集合 $D \subseteq \R^N$，如果 $\forall \, \boldsymbol x, \boldsymbol y \in D$ 都满足下式，称 $D$ 为凸集：

$$ \forall \lambda \in [0, 1], \ \ (\lambda \boldsymbol x + (1 - \lambda) \boldsymbol y) \in D $$
- 换句话说，$\boldsymbol x, \boldsymbol y$ 两点连成线段上所有点也都在 $D$ 内。
- 这里说一下凸集定义和向量空间定义的区别。凸集对「凸组合 $C(\boldsymbol x, \boldsymbol y, \lambda) = \lambda \boldsymbol x + (1 - \lambda) \boldsymbol y$」（即两点线段上的点）这一操作具备封闭性。向量空间对线性组合（即数乘与加法）这一操作具备封闭性。凸集是能不包括零向量的，也能不包括无限远的向量。

2. 其他相关概念的定义

【仿射集的定义】对于集合 $C \subseteq \R^N$，如果 $\forall \, \boldsymbol x, \boldsymbol y \in C$ 都满足下式，称 $C$ 为仿射集（仿射空间）：

$$ \forall \theta \in \R, \ \ (\theta \boldsymbol x + (1 - \theta) \boldsymbol y) \in C $$
- 换句话说，$\boldsymbol x, \boldsymbol y$ 两点连成直线上所有点也都在 $C$ 内。
- 例子：三维空间中的任何平面（无论过不过原点）都是个仿射集。
- 仿射集显然都是凸集。
- 与线性方程组解集的联系：
  - 线性方程组 $\boldsymbol A \boldsymbol x = \boldsymbol b$ 的解的集合 $S$ 是仿射集。留意到这种解具有「齐次解+特解」的形式。
  - 反过来，任何仿射集也可以表示为某一个线性方程组的解集。
**【凸包的定义】**任意集合 $S \subseteq \R^n$ 的凸包定义为所有包含 $S$ 的凸集的交集，记为 ${\rm conv} \, S$。
- 请区别凸包和闭包。
**【多胞形 (polytope) 的定义】**有限点集的凸包称为多胞形。
- 比如，下面是点集 $\{ \boldsymbol x_1, \boldsymbol x_2, \cdots, \boldsymbol x_5 \}$ 对应的凸包。
**【单纯形的定义】**当构成多胞形的 $n$ 个点是仿射无关的时候，对应构成的凸包称为 $n$ 维单纯形。
- 一组点仿射无关的判断方法：选择其中任意一个点（比如 $\boldsymbol x_1$）作为基准点，考虑其余点与它的差向量 $\boldsymbol x_2 - \boldsymbol x_1, \, \boldsymbol x_3 - \boldsymbol x_1, \, \cdots, \, \boldsymbol x_n - \boldsymbol x_1$，如果它们线性无关，那么就说原来的点集是仿射无关的。
- 空间中的单纯形
  - 0-单纯形：单个点。
  - 1-单纯形：线段（两个端点的凸组合）。
  - 2-单纯形：三角形（三个顶点的凸组合）。
  - 3-单纯形：四面体（四个顶点的凸组合）。
- 在单纯形中，可以直接用重心坐标来描述任意点。

二、常见的凸集

1. 线性空间

线性空间显然是凸集。
- 所以任意齐次（过原点）超平面是凸集。

2. 一般超平面

任意一般超平面 $H = \{ \boldsymbol x \, | \, \boldsymbol p^{\rm T} \boldsymbol x = \alpha \}$（其中非零向量 $\boldsymbol p$ 是法向量，证略）是凸集。
证明
- $\forall \boldsymbol x , \boldsymbol y \in D$，有 $\boldsymbol p^{\rm T} \boldsymbol x = \alpha, \, \boldsymbol p^{\rm T} \boldsymbol y = \alpha$。作 $\forall \lambda \in [0, 1]$：
  
  $$ \boldsymbol p^{\rm T} (\lambda \boldsymbol x + (1-\lambda) \boldsymbol y) = \lambda \boldsymbol p^{\rm T} \boldsymbol x+ (1-\lambda) \boldsymbol p^{\rm T} \boldsymbol y = \alpha $$
  - 故 $(\lambda \boldsymbol x + (1 - \lambda) \boldsymbol y) \in D$ 成立。
- 请注意这里将 $H = \{ \boldsymbol x \, | \, \boldsymbol p^{\rm T} \boldsymbol x = \alpha \}$ 称为一般超平面，其由齐次（过原点）超平面 $H = \{ \boldsymbol x \, | \, \boldsymbol p^{\rm T} \boldsymbol x = 0 \}$ 施加位移而来（$\boldsymbol p \neq \boldsymbol 0$）。记沿法向量 $\boldsymbol p$ 方向位移的长度为 $d$，有：
  
  $$ d = \frac {|\alpha|}{\| \boldsymbol p \|} $$
  推导（不严谨，只是思路）
  - 考察函数 $f(\boldsymbol x) = \boldsymbol p^{\rm T} \boldsymbol x$。
  - 将 $\boldsymbol x$ 分解为平行于 $\boldsymbol p$ 和正交于 $\boldsymbol p$ 的分量 $\boldsymbol x = \boldsymbol x_p + \boldsymbol x_\perp$。
  - 有 $f(\boldsymbol x) = \boldsymbol p^{\rm T} \boldsymbol x_p = \| \boldsymbol p \| \| \boldsymbol x_p \| \lambda(\boldsymbol x_p, \boldsymbol p)$（$\lambda(\boldsymbol x_p, \boldsymbol p)$ 在两向量同向时取 1，反向时取 -1）。
  - 因而给定 $f(\boldsymbol x) = \alpha$ 时，有 $\| \boldsymbol x_p \| = \frac {|\alpha|}{\| \boldsymbol p \|}$ 即为沿法向量 $\boldsymbol p$ 方向位移长度。

3. 一般半空间

任意一般超平面指定的半空间（包括闭半空间与开半空间）即 $H = \{ \boldsymbol x \, | \, \boldsymbol p^{\rm T} \boldsymbol x \, (\le, <, \ge, >) \, \alpha \}$ 是凸集。

证明与上类似，故省略。
- 这里用 L 侧闭(开)半空间和 G 侧闭(开)半空间分别指代 $(\le, <, \ge, >)$ 四者。留意到几何上，G 侧指代的是沿着法向量 $\boldsymbol p$ 方向的那侧；L 侧是逆着法向量 $\boldsymbol p$ 方向的那侧。
  
  推导：假设有一个与 $\boldsymbol p$ 同向平行的超长向量 $\alpha \boldsymbol p \ (\alpha \to +\infin)$，$\boldsymbol p^{\rm T} \alpha \boldsymbol p \to +\infin$为 G 侧；反之 $\beta \boldsymbol p \ (\beta \to -\infin)$，$\boldsymbol p^{\rm T} \beta \boldsymbol p \to -\infin$为 L 侧。
<aside> 💡

值得留意的是，因为凸集之交仍是凸集（见「凸集的性质」部分），因而 $\{ \boldsymbol x | \boldsymbol A \boldsymbol x \, (\le, <, \ge, >) \, \boldsymbol b \}$ 是凸集。也能继续推出 $\{ \boldsymbol x | \boldsymbol A \boldsymbol x = \boldsymbol b \}$ 和 $\{ \boldsymbol x \in \R^N \, | \, \boldsymbol a \le \boldsymbol x \le \boldsymbol b \}$ 也都是凸集。

</aside>

4. 射线

任意射线 $L = \{ \boldsymbol a + \lambda \boldsymbol d \, | \, \lambda \ge 0 \}$ 是凸集。这里常量 $\boldsymbol a$ 指示了起点；非零常向量 $\boldsymbol d$ 指示了方向。

5. 范数球

任意范数球 (norm ball) $S= \{ \boldsymbol x \, | \, \| \boldsymbol x - \boldsymbol x_c \|_a \le r \}$ 是凸集，其中 $r$ 为半径，$\| \cdot \|_a$ 是满足向量范数要求（非负性、数乘、三角不等式）的任意范数。
证明
- $\forall \, \boldsymbol x_1, \boldsymbol x_2 \in S$，有 $\| \boldsymbol x_1 - \boldsymbol x_c \|_a \le r$，$\| \boldsymbol x_2 - \boldsymbol x_c \|_a \le r$。
- 作 $\forall \lambda \in [0, 1]$ 有：
  
  $$ \begin{align*}
  
  \| \lambda \boldsymbol x_1 + (1-\lambda) \boldsymbol x_2 - \boldsymbol x_c \|_a
  
  &= \| \lambda (\boldsymbol x_1 - \boldsymbol x_c) + (1-\lambda) (\boldsymbol x_2 - \boldsymbol x_c) \|_a \\
  
  &\le \lambda \| \boldsymbol x_1 - \boldsymbol x_c \|_a + (1-\lambda) \| \boldsymbol x_2 - \boldsymbol x_c \|_a \\
  
  &\le r
  
  \end{align*} $$
- 因而 $\lambda \boldsymbol x_1 + (1-\lambda) \boldsymbol x_2 \in S$。