[笔记] 最优化方法 - 凸集

凸集的定义、性质

设$S \subseteq E^n$，若对$\forall x^{(1)}, x^{(2)} \in S$及$\forall \lambda \in [0, 1]$，都有$\lambda x^{(1)} + (1 - \lambda) x^{(2)} \in S$，则称$S$为凸集。

设$S_1$和$S_2$是两个凸集，$\beta$实数，则
- $\beta S_1 = \{ \beta x \mid x \in S_1 \}$是凸集
- $S_1 + S_2 = \{ x^{(1)} + x^{(2)} \mid x^{(1)} \in S_1, x^{(2)} \in S_2 \}$是凸集
- $S_1 - S_2 = \{ x^{(1)} - x^{(2)} \mid x^{(1)} \in S_1, x^{(2)} \in S_2 \}$是凸集
- $S_1 \bigcap S_2$是凸集

极点和极方向的定义

• 极点

  设$S$是非空集合，$x \in S$，若$x$不能表示成$S$中两个不同点的凸组合，即若假设$x = \lambda x^{(1)} + (1 - \lambda)x^{(2)}$，必推出$x = x^{(1)} = x^{(2)}$，则称$x$是凸集$S$的极点。

• 方向

  设$S$是闭凸集，$d$为非零向量，如果对$S$中的每一个$x$，有$\{ x + \lambda d \mid \lambda \ge 0 \} \subset S$，则称$d$是$S$的方向。

  设$d^{(1)}$和$d^{(2)}$是$S$的两个方向，若对任何正数$\lambda$，有$d^{(1)} \neq \lambda d^{(2)}$，则称$d^{(1)}$和$d^{(2)}$是两个不同的方向。

  设$S = \{ x \mid Ax = b, x \ge 0 \} \neq \emptyset$，$d$是非零向量，则$d$是$S$的方向 $\iff$ $d \ge 0$且$Ad = 0$。

• 极方向

  若$S$的方向$d$不能表示成该集合的两个不同方向的正的线性组合，则称$d$为$S$的极方向。

例：设$S = \{ (x_1, x_2)^T \mid x_2 \ge \lvert x_1 \rvert \}, d^{(1)} = (1, 1)^T, d^{(2)} = (-1, 1)^T$，则$d^{(1)}, d^{(2)}$是$S$的极方向。

解：对$\forall x \in S, \forall \lambda \ge 0$，有
$x + \lambda d^{(1)} = (x_1, x_2)^T + \lambda (1, 1)^T = (x_1 + \lambda, x_2 + \lambda)^T$
$x \in S \implies x_2 \ge \lvert x_1 \rvert$
而$x_2 + \lambda \ge \lvert x_1 \rvert + \lambda \ge \lvert x_1 + \lambda \rvert$，
$\implies \{ x + \lambda d^{(1)} \mid \lambda \ge 0 \} \subset S$
故$d^{(1)}$是$S$的方向。

设$d^{(1)} = \lambda _1 (x_1, x_2)^T + \lambda _2 (y_1, y_2)^T$，其中$\lambda _1, \lambda _2 \gt 0$, $(x_1, x_2)^T, (y_1, y_2)^T$是$S$的方向，则有
$\left\{ \begin{array}{c} 1 = \lambda _1 x_1 + \lambda _2 y_1 \\ 1 = \lambda _1 x_2 + \lambda _2 y_2 \end{array} \right. \implies \lambda _1 x_1 + \lambda _2 y_1 = \lambda _1 x_2 + \lambda _2 y_2$
$\implies x_1 = \frac{\lambda _2}{\lambda _1} (y_2 - y_1) + x_2$
$(x_1, x_2)^T, (y_1, y_2)^T$是$S$的方向，
$\implies x_2 \ge \lvert x_1 \rvert, y_2 \ge \lvert y_1 \rvert, (x_1, x_2)^T \neq 0, (y_1, y_2)^T \neq 0$
$\implies x_2 \ge \lvert x_1 \rvert = \left \lvert \frac{\lambda _2}{\lambda _1} (y_2 - y_1) + x_2 \right \rvert \implies y_2 \le y_1$
$y_2 \ge \lvert y_1 \rvert \implies y_2 = y_1 \implies x_2 = x_1 \implies (x_1, x_2)^T = \frac{x_1}{y_1} (y_1, y_2)^T$
故$d^{(1)}$是$S$的极方向。

• 多面集的表示定理

  设$S = \{ x \mid Ax = b, x \ge 0 \}$为非空多面集，则有

  • 极点集非空，且存在有限个极点$x^{(1)}, \cdots, x^{(k)}$
  • 极方向集合为空集 $\iff$ $S$有界。若$S$无界，则存在有限个极方向$d^{(1)}, d^{(2)}, \cdots, d^{(l)}$
  • $x \in S \iff x = \sum _{j = 1}^k \lambda _j x^{(j)} + \sum _{j = 1}^l \mu _j d^{(j)}$
    其中$\lambda _j \ge 0, j = 1, 2, \cdots, k, \sum _{j = 1}^k \lambda _j = 1$
    $\mu _j \ge 0, j = 1, 2, \cdots, l$

  凸集分离定理

  设$S_1$和$S_2$是$E^n$中两个非空集合，
  $H = \{ x \mid p^T x = \alpha \}$为超平面，
  如果对$\forall x \in S_1$，都有$p^T x \ge \alpha$，
  对$\forall x \in S_2$，都有$p^x \le \alpha$，
  则称超平面$H$分离集合$S_1$和$S_2$。

  • Farkas定理

    设$A$为$m \times n$矩阵，$c$为$n$维列向量，
    则$Ax \le 0, c^T x \gt 0$有解，
    $\iff$ $A^T y = c, y \ge 0$无解。

    证：$\implies$
    设存在$y \ge 0$，使得$A^T y = c$
    则$y^T A = c^T$
    设$\overline{x}$为$Ax \le 0, c^T x \gt 0$的一个解，
    则有$A \overline{x} \le 0, c^T \overline{x} \gt 0$
    $\implies y^T A \overline{x} = c^T \overline{x} \gt 0 \quad (1)$
    $y \ge 0, A \overline{x} \le 0 \implies y^T A \overline{x} \le 0$与$(1)$矛盾。

    $\impliedby$
    设$A^T y = c, y \ge 0$无解，令$S = \{ z \mid z = A^T y, y \ge 0 \}$，则$c \notin S$
    可以证明$S$为闭凸集，由凸集分离定理知，
    $\exists x \neq 0, \varepsilon \gt 0$，使得对
    $\forall z \in S$，有$x^T c \ge \varepsilon + x^T z$
    $\varepsilon \gt 0 \implies x^T c \gt x^T z$
    $\implies c^T x \gt z^T x = y^T Ax$
    即对任意的$y \ge 0$，有$c^T x \gt y^T Ax \quad (2)$
    令$y = 0$，得$c^T x \gt 0$
    $c^T x$为一定数，$y$的分量可取任意大
    $\implies$由$(2)$，必有$Ax \le 0$
    故非零向量$x$是$Ax \le 0, c^T x \gt 0$的解。

  例：设$A$是$m \times n$矩阵，$B$是$l \times n$矩阵，$c \in E^n$，证明下列两个系统恰有一个有解：
  系1 $Ax \le 0, Bx = 0, c^T x \gt 0$，对某些$x \in E^n$。
  系2 $A^T y + B^T z = c, y \ge 0$，对某些$y \in E^n$和$z \in E^l$。

  证：$Bx = 0$等价于$\left\{ \begin{array}{c} Bx \le 0 \\ Bx \ge 0 \end{array} \right.$
  故系统1有解，即
  $\begin{bmatrix} A \\ B \\ -B \end{bmatrix} x \le 0, c^T x \gt 0$有解。
  由Farkas定理知，
  $\begin{pmatrix} A^T & B^T & -B^T \end{pmatrix} \begin{bmatrix} y \\ u \\ v \end{bmatrix} = c, \begin{bmatrix} y \\ u \\ v \end{bmatrix} \ge 0$无解。
  令$z = u - v$，则
  $A^T y + B^T z = c, y \ge 0$无解。
  即系统2无解。

  反之，若系统2有解。即
  $\begin{pmatrix} A^T & B^T & -B^T \end{pmatrix} \begin{bmatrix} y \\ u \\ v \end{bmatrix} = c, \begin{bmatrix} y \\ u \\ v \end{bmatrix} \ge 0$有解。
  由Farkas定理，知
  $\begin{bmatrix} A \\ B \\ -B \end{bmatrix} x \le 0, c^T x \gt 0$无解。
  即$Ax \le 0, Bx = 0, c^T x \gt 0$无解，亦即系统1无解。
  综上可得，两个系统恰有一个有解。

  • Gordan定理

    设$A$为$m \times n$矩阵，
    则$Ax \lt 0$有解，
    $\iff$ $A^T y = 0, y \ge 0 (y \neq 0)$无解。

    证：$\implies$
    设存在$\overline{x}$，使得$A \overline{x} \lt 0$
    若存在非零向量$y \ge 0$，使得$A^T y = 0$
    则有$y^T A = 0$，$\implies y^T A \overline{x} = 0$
    $A \overline{x} \lt 0 \implies$ $y$的各分量不可能为非负数，与$y \ge 0$矛盾。

    $\impliedby$
    （证等价命题）即若$Ax \lt 0$无解，则存在非零向量$y \ge 0$，使得$A^T y = 0$
    设$Ax \lt 0$无解，令$S_1 = \{ z \mid z = Ax, x \in E^n \}, S_2 = \{ z \mid z \lt 0 \}$
    $Ax \lt 0$无解 $\implies$ $S_1 \bigcap S_2 = \emptyset$
    由分离定理知，存在非零向量$y$，使得对$\forall x \in E^n, \forall z \in S_2$，有$y^T Ax \ge y^T z \quad (1)$
    特别地，当$x = 0$时，有$y^T z \le 0$。
    $z \lt 0$，它的分量可取任意负数 $\implies$ $y \ge 0$
    在$(1)$中令$z \to 0$，则对$\forall x \in E^n$，有
    $y^T Ax \ge 0 \quad (2)$
    令$x = -A^T y$，代入$(2)$，得$-y^T A A^T y \ge 0$
    即$-\lVert A^T y \rVert \ge 0$ $\implies$ $A^T y = 0$
    故存在非零向量$y \ge 0$，使得$A^T y = 0$