Linear Programming Note
之前在上家公司处理一个产品上的算法策略时，无意上发现问题在一定近似转化下，可用线性规划来做。于是某次周例行分享中给组里简单讲了下线性规划的东西。单纯形之类的算法运筹课上讲过，即使忘了，按部就班复习一遍倒也不算难事，更何况有各种现成软件包可供调用，并不必手动去写。反倒是推理的过程之前运筹和数学建模课上并没有太理清，自己整理的时候发现还挺有意思；而且也不难，都是最基本的分析和代数技巧。这里顺便记录一下。
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. \left\{ \begin{aligned} x_1 + x_2 + x_3 + x_4 & = 100000 \\ x_1 - x_2 & \le 0 \\ x_1 + x_2 & \ge 50000 \\ x_3 - 1.5 x_4 & \le 0 \end{aligned} \right.\\ x_i \ge 0, i = 1, \dots, 4 \]
其中 \(c_1, \dots, c_4\) 是几种方法对应的单位时间收益率。 （当然这只是演示例子，真的投资显然不是每种都有稳定线性收益的。）
2. 问题的一般形式
现实中有大量的问题最终会转化为求解一个线性函数的最值，而其中的决策变量（比如上例中的 \(x_i\)）需要满足线性约束条件。
我们希望问题的形式能更整齐一点，不要一会大于一会小于，于是一般会进行如下一些正规化步骤。
变量非负
有时变量可能取负值，或没有明确约束条件，一般的处理技巧是：
- \(x \ge a, a \ne 0\)：引入 \(u = x - a\)
- \(x \le a\)：令 \(u = -x\)
- \(x \in [a, b]\)：令 \(u_1 \ge a, u_2 \le b\)，同时在方程组中添加 $ u_1 - u_2 = 0$ 并把所有 \(x\) 替换为 $ u_1$
- \(x \in \mathbb{R}\)：引入 \(u_1 \ge 0, u_2 \ge 0\)，同时令 \(x = u1 - u2\)
这些引入的新变量 \(u\) 一般也称为松弛变量（slack variable）。
对于严格不等号的情形（比如 \(x > 0\)）很多书中并未明确说，但严格来讲是需要讨论的。这时也可以通过引入松弛变量来完成非负转化，比如 \(u = x - x^{+} \ge 0, x^{+} \ge 0\)，但此时的问题是等号不能同时成立。因此或者我们需要在最后求解完成后进行验证；或者我们需要放宽最值条件到上/下确界，因为此时有可能最值是不存在的，即实际求得的是 \(\sup z\)（或 \(\inf z\)）。
总之通过上述转化，我们可以将所有变量转化为非负变量。
约束不等号
类似的，对于约束条件，也可通过上述技巧转化为等式。记 \(f = a_1 x_1 + a_2 x_2 + \cdots + a_n x_n\)，\(b \in \mathbb{R}\)：
- \(f \ge b\)，\(f > b\)：等式两边取负号
- \(f \le b\)，\(f < b\)：添加松弛变量 \(f + u = b, u \ge 0\)
- \(\min z\)：取 \(z^{\prime} = -z\)，转化为 \(\max z^{\prime}\)
一般形式
于是，经过转化，我们可以得到线性规划（linear programming）问题的一般形式：
\[ \max z = c^{T}x \\ s.t. Ax = b, x \ge 0 \]
其中，\(A \in \mathbb{R}^{m\times n}\)，\(x, c \in \mathbb{R}^{n}, b \in \mathbb{R}^{m}\)。在上下文没有歧义的情况下，当 \(x\) 是向量时，\(x \ge 0\) 表示 \(x\) 各分量非负。
3. 理论证明
问题定义好了，接下来就是要把它解决掉。当然，暴力的办法是行不通的，我们不可能穷举所有满足约束条件的 \(x\) 然后计算 \(z\) 值再来看哪个最大。为方便叙述需要引入一些基本概念，然后来看问题是如何一步步转化为可解决的。
可行域的凸性
记 \[ \Omega = \{x \mid Ax = b, x\ge 0\} \]，称为可行域（Fesible region）。\(\forall x^{(1)}, x^{(2)} \in \Omega\)，\(\forall \lambda \in (0, 1)\)，很容易证明 \(\lambda x^{(1)} + (1 - \lambda)x^{(2)} \in \Omega\)，因此 \(\Omega\) 是凸集。
引入极点（extreme point）的概念：设 \(x \in X\) 为凸集中一点，若不存在 \(x^{(1)}, x^{(2)} \in X\)，\(x^{(1)} \ne x^{(2)}\) 及 \(\lambda \in (0, 1)\)，使得 \(x = \lambda x^{(1)} + (1 - \lambda)x^{(2)}\)（或从几何角度说，\(x\) 不在 \(x^{(1)}, x^{(2)}\) 的连接线段上），则称 \(x\) 为 \(X\) 的一个极点。有时也说顶点，因为从几何直观上看，极点可以粗略看作 \(X\) 在空间中所表示的几何体的「顶点」。
因为我们就在性质良好的 \(\mathbb{R}^n\) 中，所以由 Krein-Milman 定理可以很容易的得到1：
推论 1：设 \(V\) 是有界凸集 \(\Omega\) 中所有极点的集合2，记
\[ Hull(V) = \{ \sum_{i}\lambda_{i} y^{(i)} \mid \sum_{i}\lambda_i = 1, \lambda_i \ge 0, y^{(i)} \in V\} \]
为 \(V\) 中所有点的凸组合组成的集合，则 \(Hull(V)\) 是 \(V\) 的凸包，且 \(\Omega = Hull(V)\)。
由此推论我们可知 \(\Omega\) 中任意一点可表示成其极点的凸组合。正是利用这个性质，我们可以把在 \(\Omega\) 内寻找最大值的问题限制到只在极点集合 \(V\) 上寻找最大值。因为若记
\[M = \max_{y \in V} c^{T}y\]
则
\[ z = c^{T}x = \sum_{i}\lambda_{i}c^{T}y^{(i)} \le \sum_{i}\lambda_i M = M \]
基础可行解
那么怎么寻找这些极点呢？我们需要暂时先回到问题的代数形式上，引入一些必要的概念。
首先我们不妨假定上述标准形式已经过必要的行变换，且 \(rank(A) = m < n\)（否则的话可行域是零维空间，可直接通过线性方程组解得，不在讨论范围内）。设 \(A = (p_1, p_2, \dots, p_n)\)，其中 \(p_i \in \mathbb{R}^{m\times 1}\) 为 \(A\) 的列向量；\(x = (x_1, x_2, \dots, x_n)^{T}\)，于是 \[ Ax = \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\)。此时可简记 \(Ax = A_S x_S = b\)。
主要定理结论
Theorem 1: \(x \in \Omega\) is a basic feasible solution \(\iff\) \(x\) is an extreme point of \(\Omega\).
定理 1：\(x \in \Omega\) 是上述线性规划问题一般形式的基础可行解当且仅当 \(x\) 为 \(\Omega\) 的极点。
证明：
“\(\Rightarrow\)”：若 \(x\) 不是极点，则存在 \(x^{(1)}, x^{(2)} \in \Omega\)，\(x^{(1)} \ne x^{(2)}\)，及 \(\lambda \in (0, 1)\)，使得 \(x = \lambda x^{(1)} + (1 - \lambda)x^{(2)}\)。令 \[ S^{\prime} = \{1, \dots, n\} - S \] 为 \(x\) 的零分量下标集合，则
\[ 0 = x_{S^{\prime}} = \lambda x_{S^{\prime}}^{(1)} + (1-\lambda) x_{S^{\prime}}^{(2)} \]
因为 $x^{(1)}, x^{(2)} $ 在可行域内，本身非负，所以由上式可知 $ x_{S{}}{(1)} = 0 $ 且 $ x_{S{}}{(2)} = 0 $。又由于 \(x^{(1)} \ne x^{(2)}\)，所以 \(x_{S}^{(1)} \ne x_{S}^{(2)}\)。
而 $ x^{(1)} $，所以 $ Ax^{(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 \mathbb{R}^{m\times m}\) 满秩，估逆矩阵存在，所以 $ x_{S}^{(1)} = A_{S}^{-1} b = x_{S}^{(2)}$，同 \(x_{S}^{(1)} \ne 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} \ne 0, A_{S} y_{S} = 0\)。
构造 \(y \in \mathbb{R}^{n}\) 使其在 \(S\) 上的分量跟 \(y_S\) 一致，而在其他分量上为零，即 $y_{S^{}} = 0 $。由于 \(x_S > 0\)，可取足够小的 \(\epsilon > 0\)，使得 $ x + y $。又因为
\[ \begin{aligned} A(x + \epsilon y) &= (p_1, \dots, p_n)(x + \epsilon y) \\ &= \sum_{j = 1}^{n}x_j p_j + \epsilon \sum_{j \in S} y_j p_j + \epsilon \sum_{j \in S^{\prime}} y_j p_j \\ &= b + \epsilon A_{S}y_{S} + \epsilon A_{S^{\prime}} y_{S^{\prime}} \\ &= b + \epsilon \cdot 0 + \epsilon \cdot 0 \\ &= b \end{aligned} \]
所以，\(x + \epsilon y \in \Omega\)，同理，可取到足够小的 $^{} > 0 $ 使得 $x - ^{} y $，为简便仍然用 \(\epsilon\) 表示 $ (, ^{})$。
则由 \(y \ne 0\) 知 \(x + \epsilon y \ne x - \epsilon y\)，但
\[ x = \frac{1}{2}(x + \epsilon y) + \frac{1}{2}(x - \epsilon y) \]
这与 \(x\) 是极点矛盾。\(\Box\)
有了这个定理，我们可以发现问题归结为只需要在 \(A\) 的列向量组 \((p_1, \dots, p_n)\) 中找出所有极大线性无关组就好了。而这是一个通过最基本线性代数就可以完成的任务。
当然你并不需要去穷举所有可能的线性无关组（$ $ 种可能还是很多的），这就是单纯形法（simplex algorithm）发挥作用的地方了，不过这里限于篇幅（太懒了）就不再详细描述这个著名算法的具体操作了。
4. 小结
我们可以看到对于这样一个看似「古老」的问题，其实在细节上依然有很多需要小心证明的地方。而我个人觉得比较有意思的一个点，就是主要定理之所以对问题的解决有着很重要的一步非平凡推进，原因在于，其把一个完全是几何味道的极点（顶点）概念，同完全是代数味道的基础可行解（线性无关）结合了起来。而其证明过程没有用到高阶的理论，全部是很工整的基础代数和分析技巧。所以这里特意详细梳理了一下理论的流程，算是一篇简单的笔记。3
