割平面法（行生成算法）与列生成算法以及它们的对偶性

#! https://zhuanlan.zhihu.com/p/598065618 # 割平面法（行生成算法）与列生成算法以及它们的对偶性

在线性规划中，我们把变量称为“列”，把约束称为“行”。行生成和列生成算法大思路是一致的，都是由于原问题规模过大，所以需要把原问题“简化”一部分，不过这就导致丢失了部分信息，失去了最优性。因此我们就要以某种方式迭代的把简化掉的部分再添加回去一部分，直到得到最优解。

割平面法

割平面法又叫行生成算法。对于一个线性规划问题

\[ \min c^T x \\ {s.t.} Ax \ge b \]

其中\(A\in R^{m\times n}\)，如果m特别大，也就是约束的数目特别多，我们有时就会考虑使用行生成算法。

由于m特别大，我们可以猜测绝大多数约束应该是不起作用的，那么我们可以丢掉一些约束，也就是把A丢掉一些行，组成新的系数矩阵\(\tilde{A}\)，对应的也得到\(\tilde{b}\)，这样就得到一个简化后的问题

\[ \min c^T x \\ {s.t.} \begin{array}{l} \tilde{A}x \ge \tilde{b} \end{array} \]

由于丢掉了一些约束，这个简化后问题的最优解应该是小于等于原问题最优解的。并且这个解不一定在原问题可行域内。实际上如果这个解在原问题可行域内，说明我们已经求得原问题最优解了，迭代可以结束。而如果不是，那么我们需要在被丢掉的约束中取一些重新加入简化后问题。

显然，如何选择加入的约束是一个重要的任务，因为加入的约束好就更可能快的求得最优解。一种常用的方式是找到违背程度最大的约束加入原问题，也就是找到

\[ \min_j A_j x^* -b \]

然后把第j个约束加入简化后问题。

列生成算法

对于一个线性规划问题

\[ \min c^T x \\ {s.t.}\left \{ \begin{array}{l} Ax = b\\ x\ge 0 \end{array} \right. \ (MP) \]

其中\(A\in R^{m\times n}\)，如果n特别大，也就是变量的数目特别多，那么求解这样一个问题是很困难的。但是从单纯形法中我们知道，绝大多数变量其实是没有用的。其中\(n-m\)个非基变量都是0。因此这就提示我们可能有某种方式可以简化计算。

把一部分变量暂时丢掉，也就是强制它们为非基变量，相当于在A中取一些列，组成新的系数矩阵\(\tilde{A}\)，对应的也得到\(\tilde{c}\)。这样就得到如下restrict main problem（RMP）

\[ \min \tilde{c}^T x \\ {s.t.}\left \{ \begin{array}{l} \tilde{A}x = b\\ x\ge 0 \end{array} \right. \ (RMP) \]

考虑RMP和MP的关系，由于RMP是强制MP中一部分变量为0，所以一定有\(RMP^* \ge MP^*\)。接下来考虑将一些变量添加回RMP，来迭代出更优的解。选择的依据就是检验数（reduce cost）。

\[ \sigma_j = c_j - c_B^TB^{-1}A_j \]

检验数表示添加该变量后的目标函数单位变化量，因此我们会选择检验数为负且最小的变量添加。考虑计算\(c_B^TB^{-1}\)并不是一件轻松的事情。直接计算是困难的，因为计算矩阵的逆是一件代价很大的事情。我们可以构造子问题来进行计算。取RMP的对偶问题

\[ \max -b^Tv \\ {s.t.} \begin{array}{l} \tilde{A}^Tv+\tilde{c}\ge0 \\ \end{array} \]

利用强对偶理论\(p^*=d^*\)就能得到\(v^T = -c_B^TB^{-1}\)。具体推导过程可以看上一篇文章。

列生成算法和行生成算法（割平面法）的对偶关系

列生成算法简化掉了部分变量，导致失去了最优性，得到的是次优的解，在迭代的过程中逐渐加入变量来优化原解；行生成算法丢掉了部分约束，导致得到的解不一定可行，在迭代的过程中逐渐加入约束使解逐渐可行。它们一个是从可行的方向，一个是从不可行的方向来逼近最优解。

我们知道在对偶问题中，进行对偶变换时约束会变成变量、而变量会到约束中。因此行生成和列生成的过程在直觉上好像存在某种对偶性，我们下面来具体验证这种直觉。

考虑RMP的对偶问题RD

\[ \max -b^Tv \\ {s.t.} \begin{array}{l} \tilde{A}^Tv+\tilde{c}\ge0 \ (RD) \\ \end{array} \]

我们也写出原问题MP的对偶问题D

\[ \max -b^Tv \\ {s.t.} \begin{array}{l} A^Tv+c\ge0 \ (D) \\ \end{array} \]

记\(d^*\)是RD的最优解，\(p^*\)是RMP的最优解；\(d^*\)。如果\(d^*\)不是D的最优解，这意味着这样几个事实

1. \(p^*\)也不是MP的最优解，所以迭代还要继续。
2. \(d^*\)比D的最优解大，因为D的可行域是RD的子集。

根据事实2，依据行生成算法的思路，这就意味着我们需要找到违背的约束把它添加到RD中。当然，我们希望添加违背程度最严重的约束，也就是找到

\[ \min_j A^T_jd^* + c_j \]

我们知道\(v^T = -c_B^TB^{-1}\)，上式的\(d^*\)实际上就是最优的\(v\)，带入得子问题为

\[ \min_j c_j-c_B^TB^{-1}A^T_j \]

不难发现，这和列生成算法中找到最小化检验数的子问题是一模一样的。另一方面，把违背的约束添加到RD中，对偶回RMP也就相当于是添加了一个新的变量。因此，行生成和列生成其实就是对偶的关系。