参见

A1-2a 凸集相关的性质 (Part. 1)

这一部分，我们集中讨论具有多面体形态的凸集所具有的几何特征。具体而言，我们重点偏好如下两种形态：

1. 由半空间或者超平面相交所得的多面体 $P = \{\boldsymbol x \in \R^n \, | \, \boldsymbol A \boldsymbol x \, (\le, =) \, \boldsymbol b \}$。

   • 我们可以只考虑 $\le$ 的情况，因为 $=$ 时相当于这样的接长的不等式约束：

     $$ \begin{bmatrix}

     \boldsymbol A \\ - \boldsymbol A

     \end{bmatrix} \boldsymbol x \le \begin{bmatrix}

     \boldsymbol b \\ - \boldsymbol b

     \end{bmatrix} $$

2. 具有标准线性规划 (LP) 问题可行域形式的凸集 $P = \{\boldsymbol x \in \R^n \, | \, \boldsymbol A \boldsymbol x = \boldsymbol b, \, \boldsymbol x \ge \boldsymbol 0 \}$ 。

   • 它仍然可以等价地变成上面的形式：

     $$ \begin{bmatrix}

     -\boldsymbol I \\ \boldsymbol A \\ -\boldsymbol A

     \end{bmatrix} \boldsymbol x \le \begin{bmatrix}

     \boldsymbol 0 \\ \boldsymbol b \\ -\boldsymbol b

     \end{bmatrix} $$

五、凸集的极点、极方向、表示定理

1. 凸集的极点

• **【极点的定义】**非空凸集 $D$ 中的点如果无法表示为 $D$ 中两个不同点的凸组合，那么被称为极点。

  • 比如下图中的顶点 $\boldsymbol x_1, \cdots, \boldsymbol x_5$ 就都是极点。

    

  • 对于抛物线的上图像、圆及其内部这类凸集，极点就有无穷多个，所以说极点理论更偏好的是由半空间或超平面切出来的空间。

• 【极点凸组合定理】（待证）任何有界闭凸集如果极点有限，其中任一点都可以表示为这些极点的凸组合。
• 【某个推论】（待证）任何 LP 可行域形式 $P = \{\boldsymbol x \in \R^n \, | \, \boldsymbol A \boldsymbol x = \boldsymbol b, \, \boldsymbol x \ge \boldsymbol 0 \}$ 如果非空，就一定有极点。

2. 凸集的方向、极方向、双方向、空间

• **【方向的定义】**对于非空凸集 $D \subseteq \R^n$，给出一个向量 $\boldsymbol d \in \R^n$（$\boldsymbol d \neq 0$），如果 $\forall \boldsymbol x \in D$ 都有 $\{ \boldsymbol x + \alpha \boldsymbol d \, | \, \alpha \ge 0 \} \subseteq D$，那么 $\boldsymbol d$ 称为 $D$ 的一个方向（也称无界方向、回收方向）。

  这个定义等价于 $\forall \boldsymbol x \in D, \, \forall \alpha \ge 0$ 都有 $\boldsymbol x + \alpha \boldsymbol d \in D$。下面类似的定义都可以这样换。

  • 换句话说，从这个凸集内任意点出发，沿着这个方向发出的射线上的所有点，都还在这个凸集内。
  • 比如，下面的图中给出的红色方向就是一个方向。我们留意到最顶上与最底下的边界不是平行的，因而方向是存在一个角度范围的。

• **【极方向的定义】**对于存在方向的非空凸集，对于它的一个方向，如果它不能被两个不同方向（不共线的方向）的非负线性组合（也称凸锥组合）表示出来，那么它是一个极方向。
  • 可以发现，这个定义类似于极点的定义。
  • 还是上面的例子，极方向有两个，就是与上面边界平行的方向，以及与下面边界平行的方向。
  • 考虑三维空间中 $\{ \boldsymbol x \in \R^3 \, | \, \boldsymbol x \ge 0 \}$ 这个凸锥，就有三个极方向。
• **【双方向的定义】**对于非空凸集 $D \subseteq \R^n$，给出一个向量 $\boldsymbol d \in \R^n$（$\boldsymbol d \neq 0$），如果 $\forall \boldsymbol x \in D$ 都有 $\{ \boldsymbol x + \alpha \boldsymbol d \, | \, \alpha \in \R \} \subseteq D$，那么 $\boldsymbol d$ 称为 $D$ 的一个双方向。

  • **【双方向的充要条件】**给出非空凸集 $D \subseteq \R^n$ 和一个向量 $\boldsymbol d \in \R^n$（$\boldsymbol d \neq 0$）：$\boldsymbol d$ 是 $D$ 的一个双方向 $\Leftrightarrow$ $\boldsymbol d$ 和 $-\boldsymbol d$ 都是 $D$ 的方向。

    证：很容易推导的。

• **【空间的定义】**对于非空凸集 $D \subseteq \R^n$，给出一个线性(子)空间 $V \subseteq \R^n$，如果 $\forall \boldsymbol x \in D$ 都有 $\{ \boldsymbol x + \boldsymbol \alpha \, | \, \boldsymbol \alpha \in V \} \subseteq D$，那么 $V$ 称为 $D$ 的一个空间（也称仿射子空间）。显然 $\{ 0 \}$ 是任意非空凸集的一个平凡空间。

  • **【空间的可组合性】**如果 $V_1$，$V_2$ 都是 $D$ 的空间，那么它们的和空间 $V_1 + V_2 = \{ \boldsymbol \alpha + \boldsymbol \beta \ | \ \boldsymbol \alpha \in V_1, \boldsymbol \beta \in V_2 \}$ 也是 $D$ 的空间。

    **证：**记任意 $\boldsymbol x \in D, \, \boldsymbol \alpha \in V_1, \, \boldsymbol \beta \in V_2$ ， $\boldsymbol x + \boldsymbol \alpha \in D$，因而 $\boldsymbol x + \boldsymbol \alpha + \boldsymbol \beta \in D$。

  • **【最大空间的定义】**对于 $D$ 的空间 $V$，如果对于所有 $D$ 的空间 $U$ 都有 $U \subseteq V$，称 $V$ 是 $D$ 的最大空间。

  • **【双方向的张成空间是空间】**如果我们有一组多个非空凸集 $D$ 的双方向，这些双方向（不一定线性无关）的生成空间是 $D$ 的空间。

    证明

    • 如果向量 $\boldsymbol d_1, \boldsymbol d_2, \cdots, \boldsymbol d_K$ 都是 $D$ 的双方向，它们的生成空间为 $\{ \boldsymbol \alpha = \lambda_1 \boldsymbol d_1 + \lambda_2 \boldsymbol d_2 + \cdots + \lambda_K \boldsymbol d_K \, | \, \lambda_1, \lambda_2, \cdots, \lambda_K \in \R \}$。
    • 对于 $\boldsymbol x \in D$，$\boldsymbol \alpha \in {\rm span}(\boldsymbol d_1, \boldsymbol d_2, \cdots, \boldsymbol d_K)$ 即 $\boldsymbol \alpha = \lambda_1 \boldsymbol d_1 + \lambda_2 \boldsymbol d_2 + \cdots + \lambda_K \boldsymbol d_K$：
      • 根据 $\boldsymbol d_1$ 是双方向，有 $\boldsymbol x_1 = \boldsymbol x + \lambda_1 \boldsymbol d_1 \in D$。
      • 根据 $\boldsymbol d_2$ 是双方向，继续有 $\boldsymbol x_2 = \boldsymbol x_1 + \lambda_2 \boldsymbol d_2 \in D$。
      • 重复过程……最后得到 $K$ 次平移完的结果 $\boldsymbol x + \boldsymbol \alpha$ 都仍在 $D$ 内，得证。

  • **【多面体的空间】**对于多面体 $P = \{\boldsymbol x \in \R^n \, | \, \boldsymbol A \boldsymbol x \, (\le, =) \, \boldsymbol b \} \neq \emptyset$，有：$\boldsymbol A$ 的零空间（核空间）是 $P$ 的最大空间。

    证明

    • 证明 ${\rm nul} (A)$ 是 $P$ 的空间。

      • 称 $\boldsymbol A$ 的零空间中任意成员 $\boldsymbol \alpha$，有：$\boldsymbol A \boldsymbol \alpha = \boldsymbol 0$。

      • 那么对于 $\boldsymbol x \in P$，已经有 $\boldsymbol A \boldsymbol x \, (\le, = ) \, \boldsymbol b$，当然就有

        $$ \boldsymbol A (\boldsymbol x + \boldsymbol \alpha) = (\boldsymbol A \boldsymbol x + \boldsymbol A \boldsymbol \alpha) = \boldsymbol A \boldsymbol x \, (\le, = ) \, \boldsymbol b $$

      • 整理一下就是 $\forall \boldsymbol x \in D, \, \forall \boldsymbol \alpha \in {\rm nul} (A)$ 都有 $\boldsymbol x + \boldsymbol \alpha \in P$，满足空间的定义。

    • 证明 ${\rm nul} (A)$ 是 $P$ 的最大空间，也就是 $P$ 的任意空间 $U$ 一定有 $U \subseteq {\rm nul} (\boldsymbol A)$。
      • 对于任意 $P$ 的空间 $U$，可知对任意 $\boldsymbol x \in P$ 和 $\boldsymbol u \in U$，都有 $\boldsymbol x + \boldsymbol u \in P$，想证得 $\boldsymbol A \boldsymbol u =\boldsymbol 0$ 总成立。
      • 视 $\boldsymbol A$ 为行向量拼接 $\boldsymbol A = [\boldsymbol a_1^{\rm T}, \boldsymbol a_2^{\rm T}, \cdots, \boldsymbol a_N^{\rm T}]^{\rm T}$，那么根据 $\boldsymbol x \in P$，第 $i \in \{ 1, 2, \cdots, N \}$ 行约束是 $\boldsymbol a_i^{\rm T} \boldsymbol x \, (\le, = ) \, b_i$。
      • 因为 $U$ 是线性(子)空间，取任意 $\boldsymbol u \in U$ 也有 $- \boldsymbol u \in U$，故 $\boldsymbol x + \boldsymbol u, \boldsymbol x - \boldsymbol u \in P$，也就是每一行：
        • $\boldsymbol a_i^{\rm T} (\boldsymbol x + \boldsymbol u) = \boldsymbol a_i^{\rm T} \boldsymbol x + \boldsymbol a_i^{\rm T} \boldsymbol u \, (\le, = ) \, b_i$。
        • $\boldsymbol a_i^{\rm T} (\boldsymbol x - \boldsymbol u) = \boldsymbol a_i^{\rm T} \boldsymbol x - \boldsymbol a_i^{\rm T} \boldsymbol u \, (\le, = ) \, b_i$。
      • 如果约束是等号，二式作差即得到 $2\boldsymbol a_i^{\rm T} \boldsymbol u = 0$，即 $\boldsymbol a_i^{\rm T} \boldsymbol u = 0$。
      • 如果约束是不等号，对于各行的 $\boldsymbol a_i^{\rm T}$ 都进行分类讨论：
        1. $\boldsymbol a_i^{\rm T} = \boldsymbol 0^{\rm T}$ 时，$\boldsymbol a_i^{\rm T} \boldsymbol u = 0$ 显然成立。
        2. 存在某列 $a_{ij} \neq 0$ 时，$\boldsymbol a_i^{\rm T} \boldsymbol x$ 是一个超平面函数，总能找到一个 $\boldsymbol x^$ 使得 $\boldsymbol a_i^{\rm T} \boldsymbol x^ = b_i$ 取等号，这时让对应的二式 $\boldsymbol a_i^{\rm T} \boldsymbol x^* + \boldsymbol a_i^{\rm T} \boldsymbol u \le b_i$ 和 $\boldsymbol a_i^{\rm T} \boldsymbol x^* - \boldsymbol a_i^{\rm T} \boldsymbol u \le b_i$ 分别减去此式导出 $\boldsymbol a_i^{\rm T} \boldsymbol u \le 0$ 和 $\boldsymbol a_i^{\rm T} \boldsymbol u \ge 0$，即 $\boldsymbol a_i^{\rm T} \boldsymbol u = 0$。
      • 综上，$\boldsymbol a_i^{\rm T} \boldsymbol u = 0$ 对所有的行都成立，因而 $\boldsymbol A \boldsymbol u = \boldsymbol 0$ 总成立。

3. 多面体的表示定理

• **【多面体的表示定理（Minkowski–Weyl 表示定理）①】**对于 ${\rm r} (\boldsymbol A) = n$（列满秩）的多面体 $P = \{\boldsymbol x \in \R^n \, | \, \boldsymbol A \boldsymbol x \le \boldsymbol b \} \neq \emptyset$，有：

  1. $P$ 的极点数目非零且有限，记个数为 $K$，并记各个极点为 $\{ \boldsymbol p^{(k)} \}$（$k \in [1, K] \cap \Z$）。

  2. $P$ 的极方向数目有限，记个数为 $J$（可能为 0），并记各个极方向为 $\{ \boldsymbol d^{(j)} \}$（$j \in [1, J] \cap \Z$）。

  3. 有：

     $$ P = \left \{ \boldsymbol x \in \R^n \left|

     \begin{cases}

     \boldsymbol x = \sum_{k=1}^K \lambda_k \boldsymbol p^{(k)} + \sum_{j=1}^J \mu_{j} \boldsymbol d^{(j)}; \\

     \forall k, \lambda_k \ge 0; \ \ \sum_{k=1}^K \lambda_k=1; \\

     \forall j, \mu_j \ge 0 \\

     \end{cases}

     \right. \right \} $$

     • 也就是说，$\boldsymbol x \in P$ $\Leftrightarrow$ $\boldsymbol x$ 能表为「极点的凸组合」与「极方向的非负线性组合（凸锥组合）」之组合。

       也被记为：$P = {\rm conv} \{ \boldsymbol p^{(1)}, \boldsymbol p^{(2)}, \cdots , \boldsymbol p^{(K)} \} + {\rm cone} \{ \boldsymbol d^{(1)}, \boldsymbol d^{(2)}, \cdots , \boldsymbol d^{(K)} \}$。

  4. $P$ 有界 $\Leftrightarrow$ $J=0$，这时 $P$ 为多胞形。

• **【多面体的表示定理（Minkowski–Weyl 表示定理）②】**当列不一定满秩时，对多面体 $P = \{\boldsymbol x \in \R^n \, | \, \boldsymbol A \boldsymbol x \le \boldsymbol b \} \neq \emptyset$，有：

  • 记下 $P$ 的最大空间 $V$（根据之前的证明，$V$ 就是 $\boldsymbol A$ 的零空间），记录它的一组线性无关张成向量为 $\{ \boldsymbol q^{(r)} \}$（$r \in [1, R] \cap \Z$）。

  • $P$「分离」$V$ 后还是凸集，记为 $P \cap V^{\complement}$，对其应用前述全维情况，记录在 $P \cap V^{\complement}$ 上面的各个极点为 $\{ \boldsymbol p^{(k)} \}$（$k \in [1, K] \cap \Z$）、各个极方向为 $\{ \boldsymbol d^{(j)} \}$（$j \in [1, J] \cap \Z$）。

    • 请注意，这样对 $P \cap V^{\complement}$ 自然就能用表示定理①来表示了。

  • 有：

    $$ P = \left \{ \boldsymbol x \in \R^n \left|

    \begin{cases}

    \boldsymbol x = \sum_{k=1}^K \lambda_k \boldsymbol p^{(k)} + \sum_{j=1}^J \mu_{j} \boldsymbol d^{(j)} + \sum_{r=1}^R \theta_r \boldsymbol q^{(r)}; \\

    \forall k, \lambda_k \ge 0; \ \ \sum_{k=1}^K \lambda_k=1; \\

    \forall j, \mu_j \ge 0; \\

    \forall r, \theta_r \in \R

    \end{cases}

    \right. \right \} $$

    • 也就是说，$\boldsymbol x \in P$ $\Leftrightarrow$ $\boldsymbol x$ 能表为「极点的凸组合」与「极方向的非负线性组合（凸锥组合）」与「空间」之组合。

      也被记为：$P = {\rm conv} \{ \boldsymbol p^{(1)}, \boldsymbol p^{(2)}, \cdots , \boldsymbol p^{(K)} \} + {\rm cone} \{ \boldsymbol d^{(1)}, \boldsymbol d^{(2)}, \cdots , \boldsymbol d^{(K)} \} + V$。

六、具有 LP 可行域形式的凸集的方向和极方向性质

• 下面考察具有线性规划可行域形式 $S = \{ \boldsymbol x \, | \, \boldsymbol A \boldsymbol x = \boldsymbol b, \boldsymbol x \ge \boldsymbol 0 \} \neq \emptyset$ 的凸集的方向和极方向的充要条件。

1. $S$ 的方向的充要条件