Linear Programming Note

2016-12-25 17:51 Mathematics

之前在上家公司处理一个产品上的算法策略时，无意上发现问题在一定近似转化下，可用线性规划来做。于是某次周例行分享中给组里简单讲了下线性规划的东西。单纯形之类的算法运筹课上讲过，即使忘了，按部就班复习一遍倒也不算难事，更何况有各种现成软件包可供调用，并不必手动去写。反倒是推理的过程之前运筹和数学建模课上并没有太理清，自己整理的时候发现还挺有意思；而且也不难，都是最基本的分析和代数技巧。这里顺便记录一下。

1. 例子

我们讲一个小例子来引入线性规划可以做什么。假设你现在有 10 万块钱想要做理财，可选的方案包括存定期、买货币基金、p2p 借贷以及投资黄金，每种方案有着不同的收益期望和风险。同时假设你给自己定了一些投资原则，比如希望定期和货基占到某个数额（随便说，例如 5 万）同时货基比存款多；又或者更看好黄金，希望其份额比 p2p 多至少 50%，等等。

我们用 $x_{1}, \dots, x_{4}$ 依次表示上述四种投资的数量，于是可以把问题形式化为如下形式：

$max z = c_{1} x_{1} + c_{2} x_{2} + c_{3} x_{3} + c_{4} x_{4} s . t . {\begin{aligned} x_{1} + x_{2} + x_{3} + x_{4} & = 100000 \\ x_{1} - x_{2} & \leq 0 \\ x_{1} + x_{2} & \geq 50000 \\ x_{3} - 1.5 x_{4} & \leq 0 \end{aligned} x_{i} \geq 0, i = 1, \dots, 4$

其中 $c_{1}, \dots, c_{4}$ 是几种方法对应的单位时间收益率。（当然这只是演示例子，真的投资显然不是每种都有稳定线性收益的。）

2. 问题的一般形式

现实中有大量的问题最终会转化为求解一个线性函数的最值，而其中的决策变量（比如上例中的 $x_{i}$ ）需要满足线性约束条件。

我们希望问题的形式能更整齐一点，不要一会大于一会小于，于是一般会进行如下一些正规化步骤。

变量非负

有时变量可能取负值，或没有明确约束条件，一般的处理技巧是：

$x \geq a, a \neq 0$ ：引入 $u = x - a$
$x \leq a$ ：令 $u = - x$
$x \in [a, b]$ ：令 $u_{1} \geq a, u_{2} \leq b$ ，同时在方程组中添加 $u_{1} - u_{2} = 0$ 并把所有 $x$ 替换为 $u_{1}$
$x \in R$ ：引入 $u_{1} \geq 0, u_{2} \geq 0$ ，同时令 $x = u 1 - u 2$

这些引入的新变量 $u$ 一般也称为松弛变量（slack variable）。

对于严格不等号的情形（比如 $x > 0$ ）很多书中并未明确说，但严格来讲是需要讨论的。这时也可以通过引入松弛变量来完成非负转化，比如 $u = x - x^{+} \geq 0, x^{+} \geq 0$ ，但此时的问题是等号不能同时成立。因此或者我们需要在最后求解完成后进行验证；或者我们需要放宽最值条件到上/下确界，因为此时有可能最值是不存在的，即实际求得的是 $sup z$ （或 $inf z$ ）。

总之通过上述转化，我们可以将所有变量转化为非负变量。

约束不等号

类似的，对于约束条件，也可通过上述技巧转化为等式。记 $f = a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n}$ ， $b \in R$ ：

$f \geq b$ ， $f > b$ ：等式两边取负号
$f \leq b$ ， $f < b$ ：添加松弛变量 $f + u = b, u \geq 0$
$min z$ ：取 $z^{'} = - z$ ，转化为 $max z^{'}$

一般形式

于是，经过转化，我们可以得到线性规划（linear programming）问题的一般形式：

$max z = c^{T} x s . t . A x = b, x \geq 0$

其中， $A \in R^{m \times n}$ ， $x, c \in R^{n}, b \in R^{m}$ 。在上下文没有歧义的情况下，当 $x$ 是向量时， $x \geq 0$ 表示 $x$ 各分量非负。

3. 理论证明

问题定义好了，接下来就是要把它解决掉。当然，暴力的办法是行不通的，我们不可能穷举所有满足约束条件的 $x$ 然后计算 $z$ 值再来看哪个最大。为方便叙述需要引入一些基本概念，然后来看问题是如何一步步转化为可解决的。

可行域的凸性

记 $Ω = {x ∣ A x = b, x \geq 0}$ ，称为可行域（Fesible region）。 $\forall x^{(1)}, x^{(2)} \in Ω$ ， $\forall λ \in (0, 1)$ ，很容易证明 $λ x^{(1)} + (1 - λ) x^{(2)} \in Ω$ ，因此 $Ω$ 是凸集。

引入极点（extreme point）的概念：设 $x \in X$ 为凸集中一点，若不存在 $x^{(1)}, x^{(2)} \in X$ ， $x^{(1)} \neq x^{(2)}$ 及 $λ \in (0, 1)$ ，使得 $x = λ x^{(1)} + (1 - λ) x^{(2)}$ （或从几何角度说， $x$ 不在 $x^{(1)}, x^{(2)}$ 的连接线段上），则称 $x$ 为 $X$ 的一个极点。有时也说顶点，因为从几何直观上看，极点可以粗略看作 $X$ 在空间中所表示的几何体的「顶点」。

因为我们就在性质良好的 $R^{n}$ 中，所以由 Krein-Milman 定理可以很容易的得到¹：

推论 1：设 $V$ 是有界凸集 $Ω$ 中所有极点的集合²，记

$H u l l (V) = {\sum_{i} λ_{i} y^{(i)} ∣ \sum_{i} λ_{i} = 1, λ_{i} \geq 0, y^{(i)} \in V}$

为 $V$ 中所有点的凸组合组成的集合，则 $H u l l (V)$ 是 $V$ 的凸包，且 $Ω = H u l l (V)$ 。

由此推论我们可知 $Ω$ 中任意一点可表示成其极点的凸组合。正是利用这个性质，我们可以把在 $Ω$ 内寻找最大值的问题限制到只在极点集合 $V$ 上寻找最大值。因为若记

$M = max_{y \in V} c^{T} y$

则

$z = c^{T} x = \sum_{i} λ_{i} c^{T} y^{(i)} \leq \sum_{i} λ_{i} M = M$

基础可行解

那么怎么寻找这些极点呢？我们需要暂时先回到问题的代数形式上，引入一些必要的概念。

首先我们不妨假定上述标准形式已经过必要的行变换，且 $r a n k (A) = m < n$ （否则的话可行域是零维空间，可直接通过线性方程组解得，不在讨论范围内）。设 $A = (p_{1}, p_{2}, \dots, p_{n})$ ，其中 $p_{i} \in R^{m \times 1}$ 为 $A$ 的列向量； $x = (x_{1}, x_{2}, \dots, x_{n})^{T}$ ，于是 $A x = \sum_{j = 1}^{n} x_{j} p_{j} = b$

设 $x$ 的非零分量下标为 $S = {j_{1}, j_{2}, \dots, j_{m}}$ ，若这些下标对应的列向量 $p_{j_{1}}, p_{j_{1}}, \dots, p_{j_{m}}$ 线性无关，则称该 $x$ 为基础可行解（Basic Feasible Solution）。为方便，有时也将非负向量 $x$ 用其非零分量表示，即 $x_{S}$ ；相应的列向量组为 $A_{S}$ 。此时可简记 $A x = A_{S} x_{S} = b$ 。

主要定理结论

Theorem 1: $x \in Ω$ is a basic feasible solution $⟺$ $x$ is an extreme point of $Ω$ .

定理 1： $x \in Ω$ 是上述线性规划问题一般形式的基础可行解当且仅当 $x$ 为 $Ω$ 的极点。

证明：

“ $\Rightarrow$ ”：若 $x$ 不是极点，则存在 $x^{(1)}, x^{(2)} \in Ω$ ， $x^{(1)} \neq x^{(2)}$ ，及 $λ \in (0, 1)$ ，使得 $x = λ x^{(1)} + (1 - λ) x^{(2)}$ 。令 $S^{'} = {1, \dots, n} - S$ 为 $x$ 的零分量下标集合，则

$0 = x_{S^{'}} = λ x_{S^{'}}^{(1)} + (1 - λ) x_{S^{'}}^{(2)}$

因为 $x^{(1)}, x^{(2)}$ 在可行域内，本身非负，所以由上式可知 $ x_{S^{}}{(1)} = 0 $且$ x_{S^{}}{(2)} = 0 $。又由于 $x^{(1)} \neq x^{(2)}$ ，所以 $x_{S}^{(1)} \neq x_{S}^{(2)}$ 。

而 $x^{(1)}$ ，所以 $A x^{(1)} = A_{S} x_{S}^{(1)} = b$ ，同理 $A_{S} x_{S}^{(2)} = b$ 。由 $x$ 是基础可行解知 $A_{S} = (p_{j_{1}}, p_{j_{1}},, p_{j_{m}})$ 列向量线性无关，即 $A_{S} \in R^{m \times m}$ 满秩，估逆矩阵存在，所以 $x_{S}^{(1)} = A_{S}^{- 1} b = x_{S}^{(2)}$ ，同 $x_{S}^{(1)} \neq x_{S}^{(2)}$ 矛盾。

“ $\Leftarrow$ ”：若 $x$ 不是基础可行解，则 $A_{S} = (p_{j_{1}}, p_{j_{1}},, p_{j_{m}})$ 线性相关，所以方程 $A_{S} x_{S} = 0$ 有非零解，不妨记为 $y_{S}$ ，即 $y_{S} \neq 0, A_{S} y_{S} = 0$ 。

构造 $y \in R^{n}$ 使其在 $S$ 上的分量跟 $y_{S}$ 一致，而在其他分量上为零，即 $y_{S^{}} = 0$ 。由于 $x_{S} > 0$ ，可取足够小的 $ϵ > 0$ ，使得 $x + y$ 。又因为

$\begin{aligned} A (x + ϵ y) & = (p_{1}, \dots, p_{n}) (x + ϵ y) \\ = \sum_{j = 1}^{n} x_{j} p_{j} + ϵ \sum_{j \in S} y_{j} p_{j} + ϵ \sum_{j \in S^{'}} y_{j} p_{j} \\ = b + ϵ A_{S} y_{S} + ϵ A_{S^{'}} y_{S^{'}} \\ = b + ϵ \cdot 0 + ϵ \cdot 0 \\ = b \end{aligned}$

所以， $x + ϵ y \in Ω$ ，同理，可取到足够小的 $^{} > 0$ 使得 $x -^{} y$ ，为简便仍然用 $ϵ$ 表示 $(,^{})$ 。

则由 $y \neq 0$ 知 $x + ϵ y \neq x - ϵ y$ ，但

$x = \frac{1}{2} (x + ϵ y) + \frac{1}{2} (x - ϵ y)$

这与 $x$ 是极点矛盾。 $◻$

有了这个定理，我们可以发现问题归结为只需要在 $A$ 的列向量组 $(p_{1}, \dots, p_{n})$ 中找出所有极大线性无关组就好了。而这是一个通过最基本线性代数就可以完成的任务。

当然你并不需要去穷举所有可能的线性无关组（种可能还是很多的），这就是单纯形法（simplex algorithm）发挥作用的地方了，不过这里~~限于篇幅~~（太懒了）就不再详细描述这个著名算法的具体操作了。

4. 小结

我们可以看到对于这样一个看似「古老」的问题，其实在细节上依然有很多需要小心证明的地方。而我个人觉得比较有意思的一个点，就是主要定理之所以对问题的解决有着很重要的一步非平凡推进，原因在于，其把一个完全是几何味道的极点（顶点）概念，同完全是代数味道的基础可行解（线性无关）结合了起来。而其证明过程没有用到高阶的理论，全部是很工整的基础代数和分析技巧。所以这里特意详细梳理了一下理论的流程，算是一篇简单的笔记。³

声明，我并没有严格验证 Krein-Milman 定理的细节，但在 $R^{n}$ 中结论应该是没问题的。↩︎
严格证明中这里需要先说明 $V$ 非空且有限。↩︎
其实主要是重新开了博客，总不能空着，于是随手先写一点占个位置。↩︎

optimization linear programming

F. Shen

Algorithm Engineer

Be an informed citizen, life hacker, and sincere creator.