Datawhale 202208 GitModel | 线性规划 下

2.3.4 向最佳顶点出发$!$ --单纯形迭代搜索

把基可行解都枚举出来是比较笨的——那样子不够"数学".

我们更希望的是$,$ 能向登山一样$,$ 设计出一条爬山路线$,$ 不断逼近"山顶"——而具有这种性质的数学算法应该是迭代的: 一步步搜索顶点$,$ 每搜索到的一个顶点 ${\mathbf{x}}_n$ 都要比上一次搜索到的顶点 ${\mathbf{x}}_{n-1}$ 要"好"$,$ 由于我们求解的是最小值$,$ 这样的算法统称为下降算法

梯度下降——“下山”( 引用自网络)

下降算法由以下几步构成:

1. 确定初始的迭代点 ${\mathbf{x}}_0$.

2. 确定迭代步骤$,$ 即 ${\mathbf{x}}_{n-1}$ 与 ${\mathbf{x}}_n$ 之间的递推关系 ${\mathbf{x}}_n=F({\mathbf{x}}_{n-1})$ 且保证"下降" $f({\mathbf{x}}_n)-f({\mathbf{x}}_{n-1})⩽0$.

3. 确定如何迭代到什么时候能找到最优解$,$ 即终止准则.

1.3.4 节中我们已经知道了线性规划问题 $1,2$ 的最优解必定在顶点 (基可行解) 处取得$,$ 故我们的搜索迭代范围仅限于顶点 (基可行解) 之间$,$ 依照下降算法的步骤$,$ 我们需要先找到一个顶点 (基可行解) 作为初始解 ${\mathbf{x}}_0$ 再从 ${\mathbf{x}}_0$ 出发寻找函数值 $f$ 不大于 $f({\mathbf{x}}_0)$ 的顶点 (基可行解) ${\mathbf{x}}_1,$ 接着重复此步骤直到找到无法再下降的顶点 (基可行解) ${\mathbf{x}}_N$.

第一部分:初始可行解(人工变量)

在最开始的时候$,$ 我们需要找到一个顶点 (基可行解) 作为算法的"启动资金"——初始解. 由 1.3.4 我们知道需要计算约束方程 $A\mathbf{x}=\mathbf{b}$ 中的一个基可行解$,$ 这要求我们找到 $A$ 中一个基 $B,$ 枚举基是有一定难度的$,$ 特别是当决策变量个数 $n$ 以及约束矩阵 $A$ 的秩 $m$ 都比较大的时候 (大规模计算的情形)$,$ 我们更希望有一种简单的方式去找到一个基 $B,$ 因为线性规划问题 $2$ 是经过引入松弛变量松弛化不等式约束的$,$ 如 $1,$ 这相当于在矩阵 $A$ 中增广了如 $(1,0,\cdots ,0)$ 的列向量$,$ 假设 $A$ 的前 $k$ 行都是不等式约束$,$ 那么加入松弛变量后 $A$ 增广为

{ a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n ⩽ b 1 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n ⩽ b 2 ⋮ a k 1 x 1 + a k 2 x 2 + ⋯ + a k n x n ⩽ b k a k + 1 , 1 x 1 + a k + 1 , 2 x 2 + ⋯ + a k + 1 , n x n = b k + 1 ⋮ a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n = b m ⟶ { a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n + s 1 = b 1 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n + s 2 = b 2 ⋮ a k 1 x 1 + a k 2 x 2 + ⋯ + a k n x n + s k = b k a k + 1 , 1 x 1 + a k + 1 , 2 x 2 + ⋯ + a k + 1 , n x n = b k + 1 ⋮ a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n = b m ⇕ ⇕ [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a m 1 a m 2 ⋯ a m n ] ⟶ [ a 11 a 12 ⋯ a 1 n 1 0 ⋯ 0 ⋯ 0 a 21 a 22 ⋯ a 2 n 0 1 ⋯ 0 ⋯ 0 ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋱ ⋮ ⋱ ⋮ a k 1 a k 2 ⋯ a k n 0 0 ⋯ 1 ⋯ 0 a k + 1 , 1 a k + 1 , 2 ⋯ a k + 1 , n 0 0 ⋯ 0 ⋯ 0 ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋱ ⋮ ⋱ ⋮ a m 1 a m 2 ⋯ a m n 0 0 ⋯ 0 ⋯ 0 ]

⎩ ⎨ ⎧​a11​x1​+a12​x2​+⋯+a1n​xn​⩽b1​a21​x1​+a22​x2​+⋯+a2n​xn​⩽b2​⋮ak1​x1​+ak2​x2​+⋯+akn​xn​⩽bk​ak+1,1​x1​+ak+1,2​x2​+⋯+ak+1,n​xn​=bk+1​⋮am1​x1​+am2​x2​+⋯+amn​xn​=bm​​⇕⎣ ⎡​a11​a21​⋮am1​​a12​a22​⋮am2​​⋯⋯⋱⋯​a1n​a2n​⋮amn​​⎦ ⎤​​⟶⟶​⎩ ⎨ ⎧​a11​x1​+a12​x2​+⋯+a1n​xn​+s1​=b1​a21​x1​+a22​x2​+⋯+a2n​xn​+s2​=b2​⋮ak1​x1​+ak2​x2​+⋯+akn​xn​+sk​=bk​ak+1,1​x1​+ak+1,2​x2​+⋯+ak+1,n​xn​=bk+1​⋮am1​x1​+am2​x2​+⋯+amn​xn​=bm​​⇕⎣ ⎡​a11​a21​⋮ak1​ak+1,1​⋮am1​​a12​a22​⋮ak2​ak+1,2​⋮am2​​⋯⋯⋱⋯⋯⋱⋯​a1n​a2n​⋮akn​ak+1,n​⋮amn​​10⋮00⋮0​01⋮00⋮0​⋯⋯⋱⋯⋯⋱⋯​00⋮10⋮0​⋯⋯⋱⋯⋯⋱⋯​00⋮00⋮0​⎦ ⎤​​

当 $m$ 行约束全是不等式约束即加入了 $m$ 个松弛变量时$,A$ 的后 $m$ 列自然构成了一个 $m$ 阶的单位阵 $I_m,$ 必定可逆$,$ 这不就是我们所想要的最简单的基吗$?$

单纯形表结构

命题 1.1.5 当线性规划问题 $2$ 中只含有不等式约束时$,$ 标准化后的约束矩阵 $A$ 后 $m$ 列 $I_m$ 是 $A$ 的基.

当松弛变量个数小于 $m$ 时$,$ 我们可以耍一耍小学生解题的"有借有还"伎俩$,$ 先借几个松弛变量凑到 $m$ 个$,$ 最后求解的时候再还回去$,$
min ⁡ c 1 x 1 + c 2 x 2 + ⋯ + c n x n min ⁡ c 1 x 1 + c 2 x 2 + ⋯ + c n x n + M ( s k + 1 + s k + 2 + ⋯ + s m ) { a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n ⩽ b 1 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n ⩽ b 2 ⋮ a k 1 x 1 + a k 2 x 2 + ⋯ + a k n x n ⩽ b k a k + 1 , 1 x 1 + a k + 1 , 2 x 2 + ⋯ + a k + 1 , n x n = b k + 1 ⋮ a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n = b m ⟶ { a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n + s 1 = b 1 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n + s 2 = b 2 ⋮ a k 1 x 1 + a k 2 x 2 + ⋯ + a k n x n + s k = b k a k + 1 , 1 x 1 + a k + 1 , 2 x 2 + ⋯ + a k + 1 , n x n + s k + 1 = b k + 1 ⋮ a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n + s m = b m ⇕ ⇕ [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a m 1 a m 2 ⋯ a m n ] ⟶ [ a 11 a 12 ⋯ a 1 n 1 0 ⋯ 0 0 ⋯ 0 a 21 a 22 ⋯ a 2 n 0 1 ⋯ 0 0 ⋯ 0 ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋱ ⋮ a k 1 a k 2 ⋯ a k n 0 0 ⋯ 1 0 ⋯ 0 a k + 1 , 1 a k + 1 , 2 ⋯ a k + 1 , n 0 0 ⋯ 0 1 ⋯ 0 ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋱ ⋮ a m 1 a m 2 ⋯ a m n 0 0 ⋯ 0 0 ⋯ 1 ]

minc1​x1​+c2​x2​+⋯+cn​xn​⎩ ⎨ ⎧​a11​x1​+a12​x2​+⋯+a1n​xn​⩽b1​a21​x1​+a22​x2​+⋯+a2n​xn​⩽b2​⋮ak1​x1​+ak2​x2​+⋯+akn​xn​⩽bk​ak+1,1​x1​+ak+1,2​x2​+⋯+ak+1,n​xn​=bk+1​⋮am1​x1​+am2​x2​+⋯+amn​xn​=bm​​⇕⎣ ⎡​a11​a21​⋮am1​​a12​a22​⋮am2​​⋯⋯⋱⋯​a1n​a2n​⋮amn​​⎦ ⎤​​⟶⟶​minc1​x1​+c2​x2​+⋯+cn​xn​+M(sk+1​+sk+2​+⋯+sm​)⎩ ⎨ ⎧​a11​x1​+a12​x2​+⋯+a1n​xn​+s1​=b1​a21​x1​+a22​x2​+⋯+a2n​xn​+s2​=b2​⋮ak1​x1​+ak2​x2​+⋯+akn​xn​+sk​=bk​ak+1,1​x1​+ak+1,2​x2​+⋯+ak+1,n​xn​+sk+1​=bk+1​⋮am1​x1​+am2​x2​+⋯+amn​xn​+sm​=bm​​⇕⎣ ⎡​a11​a21​⋮ak1​ak+1,1​⋮am1​​a12​a22​⋮ak2​ak+1,2​⋮am2​​⋯⋯⋱⋯⋯⋱⋯​a1n​a2n​⋮akn​ak+1,n​⋮amn​​10⋮00⋮0​01⋮00⋮0​⋯⋯⋱⋯⋯⋱⋯​00⋮10⋮0​00⋮01⋮0​⋯⋯⋱⋯⋯⋱⋯​00⋮00⋮1​⎦ ⎤​​
增加的松弛变量 $s_i,i=k+1,\cdots ,m$ 我们称为人工变量$,$ 其中 $M$ 是充分大的数 ($M>>c_i,i=1,2,\cdots ,n$)$,$ 用于保证增加人工变量后与原问题的等效性 (这是因为借的人工变量 $s_i,i=k+1,\cdots ,m$ 必须为 $0$ 即"还"回去$,$ 不会改变原问题的最优解).

综上$,$ 单纯形法寻找初始解步骤是

(增加人工变量后)求解松弛变量对应构成的基方程 $I_m{\mathbf{x}}^{\prime }=\mathbf{b}$ 即取 $(0,0,\cdots ,\stackrel{n}{0},b_1,b_2,\cdots ,b_m)$作为初始解 ${\mathbf{x}}_0$ 迭代.

第二部分:迭代步骤

由 1.3.4 节的命题 1.1.3 我们可知线性规划问题 KaTeX parse error: Undefined control sequence: \eqref at position 1: \̲e̲q̲r̲e̲f̲{eq 1},\eqref{e… 中可行域中的解作为顶点 (基可行解) 的必要条件是至少有 $n-m$ 个分量为 $0,$ 换言之$,$ 基可行解都是由 $m$ 个坐标分量就能决定的$,$ 那么从原来的基可行解 ${\mathbf{x}}_n$ 出发$,$ 我们就可以通过替换坐标的方式$,$ 不改变非 $0$ 分量数 $m，$ 找到新的基可行解 ${\mathbf{x}}_{n+1}^j$ ! 先斩后奏$,$ 我们给出基可行解的迭代方式如下: 不妨设 $\boldsymbol{x}n= (x{1},x_{2},\cdots,x_{m},0,\cdots,0) $ 是第 $n$ 步迭代得到的基可行解$,$ 若用第 $j$ 个坐标分量 ($j>m$) 替换 $1\sim m$ 中某一个坐标分量$,$ 则第 $n+1$ 步的基可行解为
$${\mathbf{x}}_{n+1}^j=(x_1-\theta a_{1j},x_2-\theta a_{2j},\cdots ,x_m-\theta a_{mj},0,\cdots ,\stackrel{j}{\theta },\cdots ,0),$$
其中$,$
$$\theta =\min \left\{\frac{x_i}{a_{ij}}|a_{ij}>0\right\},$$
而设最小的 $\frac{x_i}{a_{ij}}$ 对应的坐标分量是 $l,$ 那么 ${\mathbf{x}}_{n+1}^j$ 的第 $l$ 个分量 $x_l-\theta a_{lj}=0,$ 这便实现了第 $j$ 个分量到第 $l$ 个分量的替换. 而 $\theta$ 取最小值的构造保证了 $x_i-\theta a_{ij}⩾0,$ 此外$,a_{ij}⩽0$ 的分量会使得 $x_i-\theta a_{ij}⩾x_i⩾0,$ 即替换后所有分量非负$,$ 保证了 ${\mathbf{x}}_{n+1}^j$ 是基可行解.

而用来替换的坐标分量 $j$ 需要满足

$$c_j-\sum _{i=1}^m{c}_i{a}_{ij}<0,$$

因为 ${\mathbf{x}}_n$ 与 ${\mathbf{x}}_{n+1}^j$ 的目标函数值需满足单调递减性

KaTeX parse error: No such environment: at position 7: \begin{̲}̲ &f (\boldsymbo…

而基于贪心的想法$,$ 我们希望函数值能下降的越快越好即 $f({\mathbf{x}}_{n+1}^j)-f({\mathbf{x}}_n)$ 越小越好$,$ 从而我们每一步都选取如下的分量 $j,$
$$j_0=\mathrm{argmin}\left\{f({\mathbf{x}}_{n+1}^j)-f({\mathbf{x}}_n)=c_j-\sum _{i=1}^m{c}_i{a}_{ij}|j=m+1,\cdots ,n\right\}.$$

所以$,$ 单纯形法的迭代步骤是
$${\mathbf{x}}_n=(x_1,x_2,\cdots ,x_m,0,\cdots ,0)\to {\mathbf{x}}_{n+1}={\mathbf{x}}_{n+1}^{j_0}=(x_1-\theta a_{1j_0},x_2-\theta a_{2j_0},\cdots ,\cdots ,\stackrel{l}{0},\cdots ,x_m-\theta a_{m{j}_0},0,\cdots ,\stackrel{j_0}{\theta },\cdots ,0),$$
$$\theta =\min \left\{\frac{x_i}{a_{i{j}_0}}|a_{i{j}_0}>0\right\}=\frac{x_l}{a_{l{j}_0}},j_0=\mathrm{argmin}\left\{f({\mathbf{x}}_{n+1}^j)-f({\mathbf{x}}_n)=c_j-\sum _{i=1}^m{c}_i{a}_{ij}|j=m+1,\cdots ,n\right\}.$$

第三部分:终止准则

顶点序列 { x n } \{\boldsymbol{x}_n\} {xn​} 的单调递减是容易满足的$,$ 但是$,$ 怎么判断经有限步找到的最终顶点 ${\mathbf{x}}_N$ 是局部最小值呢$?$

我们以下分情况把所有的 case 都讨论一遍:

1. 有唯一解: 直观的想法是$,$ 从 ${\mathbf{x}}_N$ 出发$,$ 无论替换那个分量 $j$ 都已经找不到比它函数值更小的顶点了$,$ 那么也就是
   $$f({\mathbf{x}}_{n+1}^j)-f({\mathbf{x}}_N)=c_j-\sum _{i=1}^m{c}_i{a}_{ij}>0,j=1,2,\cdots ,n.$$
2. 有无穷多解: 从线性规划 1.3.1 的图解例子来看$,$ 至少最小值会在一条线段 (一个平面等…) 取到$,$ 那么势必会存在至少两个顶点都取到函数最小值$,$ 从而
   $$f({\mathbf{x}}_{n+1}^j)-f({\mathbf{x}}_n)=c_j-\sum _{i=1}^m{c}_i{a}_{ij}⩾0\text{且}\exists j,f({\mathbf{x}}_{n+1}^j)-f({\mathbf{x}}_n)=0.$$
3. 有无界的解: 从线性规划 1.3.1 的图解例子来看$,$ 可行域更像是一个无界的"多边形"$,$ 我们可以当作存在无穷远处的顶点$,$ 并且在无穷远处的一个顶点是能满足单调递减条件的$,$ 从而首先会存在一个坐标分量 $j$ 使得 $f({\mathbf{x}}_{n+1}^j)-f({\mathbf{x}}_n)=c_j-\sum _{i=1}^m{c}_i{a}_{ij}<0$ 且沿该坐标分量 $j$ 去更新顶点$,$ 无法找到基可行解$,$ 结合命题 1.1.3$,$ 即任意 $\theta >0$ 都无法使得 ${\mathbf{x}}_{n+1}^j=(x_1-\theta a_{1j},x_2-\theta a_{2j},\cdots ,x_m-\theta a_{mj},0,\cdots ,\stackrel{j}{\theta },\cdots ,0)$ 中前 $m$ 个分量有下降为 $0$ 的$,$ 亦即 $x_i-\theta a_{ij}>0,i=1,2,\cdots ,m$ 对 $\theta >0$ 恒成立$,$ 容易推出 $a_{ij}<0,i=1,2,\cdots ,m$ 从而总结为
   $$\exists j,f({\mathbf{x}}_{n+1}^j)-f({\mathbf{x}}_n)=c_j-\sum _{i=1}^m{c}_i{a}_{ij}<0,a_{ij}<0,i=1,2,\cdots ,m.$$
4. 无可行解: 这事实上代表着可行域 $D$ 是空集$,$ 然而在高维的大规模问题面前我们很难在求解前发现$,$ 然而我们有另外的一种判别方式: 利用加入的人工变量 $s_i,$ 若已经出现有唯一解的判别准则 $f({\mathbf{x}}_{n+1}^j)-f({\mathbf{x}}_n)=c_j-\sum _{i=1}^m{c}_i{a}_{ij}>0,j=1,2,\cdots ,n$ 但此时有人工变量 $s_i>0,$ 这即借了人工变量还不回去$,$ 亦即原问题的找不到可行解$,$ 那么无可行解的判别准则即为
   $$f({\mathbf{x}}_{n+1}^j)-f({\mathbf{x}}_n)=c_j-\sum _{i=1}^m{c}_i{a}_{ij}>0,j=1,2,\cdots ,n,\exists s_i>0,s_i\text{是人工变量}.$$

注: 值得一提的是$,$ 线性规划问题无可行解是一个特殊但不少见的情况$,$ 因为现实生活中我们也经常会遇到各种要求冲突从而找不到两全其美的解$,$ 对于如何解决这样的现实问题我们会在 Task 3 讨论.

综上$,$ 我们分析清楚了线性规划问题中解的情况并得到了相应的判别准则$,$ 然而还剩下最后一个问题没有解决:

单纯形法生成的迭代点列 $\{\boldsymbol{x}_n\}$ 的终止项 $\boldsymbol{x}_N$ 只是对于 $\{\boldsymbol{x}_n\}$ 的局部最小值$,$ 能否保证全局最小值呢$?$

事实上$,$ 优化理论中$,$ 对于大多数的优化问题而言$,$ 局部最小值并非全局最小值$,$ 然而针对一类性质较好的问题: 凸问题——目标函数是凸的$,$ 约束可行域也是凸的$,$ 是满足局部最小值即是全局最小值的$,$ 而线性规划就是最典型的凸问题之一$!$

命题 1.1.6 线性规划问题 $2,3$ 中$,$ 单纯形法搜索到的局部最小值即是全局最小值.

从上述的讨论中$,$ 我们也发现单纯形法这种下降算法中判断其下降以及终止的标准便是 $f({\mathbf{x}}_{n+1}^j)-f({\mathbf{x}}_n),$ 我们称其为判别数$,$ 记为 ${\sigma }_j$.

综上$,$ 我们总结出单纯形法的终止准则:

参考内容

Github课程链接