|
|
Farkas' lemma — 设$\mathbf {A} \in \mathbb {R} ^{m\times n}$, $\mathbf {b} \in \mathbb {R} ^{m}$. 那么以下两个断言恰好有一个为真：
• 存在 $\mathbf {x} \in \mathbb {R} ^{n}$ 使 $\mathbf {Ax} =\mathbf {b}$ 和 $x ≥ 0$.
• 存在 $\mathbf {y} \in \mathbb {R} ^{m}$ 使 $\mathbf {A} ^{\mathsf {T}}\mathbf {y} \geq 0$ 和 $\mathbf {b} ^\mathsf {T}\mathbf y<0$.
几何意义
$\mathbf{A}$ 的列的非负线性组合的集合是一个闭凸锥 $C(\mathbf{A})$
$$
C(\mathbf{A}) = \{\mathbf{A}\mathbf{x} \mid \mathbf{x} \geq 0 \}
$$
$C(\mathbf{A})$ 是这些向量$\mathbf{b}$的集合：存在$x_1, \dots, x_n\ge0$ 使得 $\mathbf{b} =x _1 \mathbf{a}_1 + \dots + x_n \mathbf{a}_n$。
| 观察：$\mathbf{b}\notin C(\mathbf{A})$，图中红色虚线将它与 $C(\mathbf{A})$ 分开。它的一侧为向量 $\mathbf{a}_i$，另一侧为向量 $\mathbf{b}$。它的法向量 $\mathbf{y}$ 满足 $\mathbf{y}$ 与向量 $\mathbf{a}_i$ 的夹角≤90°，而 $\mathbf{y} $ 与向量 $\mathbf{b}$ 的夹角>90°。所以$\mathbf{a}_i^{\mathsf{T}} \mathbf{y} \geq 0(i = 1, \dots, n)$, 且$\mathbf{b}^{\mathsf{T}} \mathbf{y} < 0$。 | |
例如，设 $n, m = 2$, $a_1 = (1, 0)^{\sf T}$, $a_2 = (1, 1)^{\sf T}$。$a_1$ 和 $a_2$ 张成的凸锥是 $\{(x,y)\in\Bbb R^2\mid x\ge y\ge0\}$。假设 $b=(0, 1)$。当然，$b$ 不在凸锥 $a_1x_1 + a_2x_2$ 中。因此，必须有一个分离超平面。设 $y=(1, −1)^{\sf T}$。我们可以看到 $a_1 · y= 1$，$a_2 · y= 0$，$b ·y = -1$。因此，具有法向量 $y$ 的超平面确实将凸锥 $a_1x_1 + a_2x_2$ 与 $b$ 分开。
Wikipedia |
|
