最优化2:线性规划及单纯形法

DomDomm

本文旨在介绍线性规划的基本概念、单纯形算法和分析单纯形法背后的原理，参考资料包括Convex Optimization(by Stephen Boyd)，《最优化理论与算法(第2版)》(陈宝林 编著)，维基百科以及其他在线资料等(详情见参考)。
1 线性规划

1.1 线性规划基本概念

线性规划(LP, Linear Programming)是指具有线性约束(包括等式约束和非等式约束)、线性目标函数的最优化问题。它是数学规划中极为特殊的一种形式。


其数学表达为


特点：

• 可行域是一个凸集(包括空集)。因为其可行域有限多个半空间和超平面的交集，因此是一个多面体（前文已经说明多面体是一个凸集）。
  
• 目标函数既是凸函数，又是凹函数(因为是线性函数或仿射函数)
  

定理：
解的存在性定理[1]。因为凸函数的最大值必在边界处取得，凹函数的最小值必在边界处取得。因此线性规划的目标函数的最小值和最大值都在边界处取得。因此线性规划的最优解(如果有的话)一定能在极点(vertices)处取得(当有多个最优解时，最优解的集合一定包含某个极点)。在两种情况下，LP无最优解：

• LP不可行。即LP的约束自相矛盾，也即LP的可行域为空集。因为无可行解，自然也就没有最优解。
  
• LP的可行域在目标函数梯度负方向无界(如果是最大化目标函数，则LP可行域在目标函数梯度方向无界)。在这种情况下，我们总能沿着负梯度方向找到更优的解，使得目标函数更小，因此无最优解。
  

多面体的极点和极方向。
定义(极点):
设  为非空凸集， ，若  不能表示为  中两个不同点的严格凸组合，即 ,则称  为凸集  中的极点。
从几何上看，极点是凸集的边界的一点，包含该点且不以该点为端点的任意线段都不在这个凸集中。多面体的极点就是构成该多面体的超平面的交点。而圆上的每一点都是极点。
可以看出，有界集中任意一点都可以表示为极点的凸组合。但是对无界集却不成立，这时需要引入极方向的概念。
定义(极方向)：
设  为闭凸集，  为非零向量，如果对  中的每一个  ，都有射线


则称  为  的方向。若  不能表示为  的两个不同方向的整的线性组合，则称  为  的极方向。
几何上，只有无界集才有方向。而极方向则是无界集的某个边界的方向向量。


加上极方向后，  内的任意点可以用极点和极方向表示出来：


即凸可行域中的任意一点都可以表示为极点的凸组合+极方向的锥组合。
1.2 标准形式

一般的线性规划总是可以写成如下标准形式(通过添加松弛变量，将不等式约束变为等式约束，同时提升可行域的维度等方法)：


其中 , ,
化成标准形式的目的是便于引出基本可行解的概念和性质，进而为单纯形方法做铺垫。
1.3 基本可行解

我们引入基本可行解的目的是为了便于缩小最优解的范围。通过前面的分析，我们已经知道线性规划的最优解一定在极点处取得，因此只需找出极点的集合，则最优解一定在这个集合中。但是极点是个很强的几何概念，虽有直观的优势，但是它对于数值计算来说不太方便。因此，我们从数值上引入基本可行解的概念，并证明它与极点等价。基本可行解的代数含义很明确，便于演算。于是，我们将求解线性规划问题转变为求解可行域的极点问题，进而转换为求解基本可行解的问题。
接下来先给出基本可行解的定义，然后给出定理说明基本可行解与极点等价。
1.3.1基本可行解的概念

设 ,已经假设矩阵  的秩为  ，则必存在 个线性无关的列向量。设这  个列向量的下标组成的集合为  ；又设 是  中以  的元素为下标的列向量构成的 方阵。设有点 ,它的以  中元素作为下标的分量构成的列向量为  。称  为基矩阵，  称为一组基，各分量为基变量，  中其他分量为非基变量。令非基变量全为  ，则显然有  。此时，  称为基本解(注意：基变量和非基变量在  中的对应位置不变)。又若  还满足不等式约束  ,称  为基本可行解。(这段话比较绕，多读几遍)
至于基本解为什么要叫这个名字。个人认为“基”和线性空间里的“基”是类似的。还记得前面说的，紧的凸集中任何一个点都可以由极点线性表出吗？那么这里极点就相当于一个空间里的基(不严谨，但可以这样理解)，于是极点对应的解就称为基本解。
下面举一个例子来帮助理解基本可行解的概念：
<hr/>例：设一个标准线性规划的等式约束为 ，其中 , ,求解该线性规划的基本可行解。
解   令 。

• 令 , 解出 ，则
  
• 令 , 解出 ，则
  
• 令 , 解出 ，则 ,  不满足不等式约束  ，因此不是基本可行解。
  

所以本题中线性规划的基本可行解为。
<hr/>几点发现：

• 根据基本可行解的概念，我们可以知道基本可行解最多可以有  个，因为从 个列向量中选取  个作为基的可能的选法有  个。
  
• 线性规划的基本可行解只与系数矩阵  和偏置  有关。
  
• 基本可行解中正分量的个数不超过系数矩阵的秩。
  

1.3.2 极点集与基本可行解集的等价性

定理：令 ,  是  矩阵，秩为  。则 的极点集与 的基本可行解等价。
这里不给出严格证明，只描述证明思路：分别证明充分性和必要性。

• 已知  是极点，证明  是基本可行解。设  有  个正分量，先证明  的正分量对应的  中的列向量线性无关，由此说明  的正分量个数  小于等于  。然后其他  个列向量与这  个列向量组成基矩阵  ，  相应的拆分为  和其他非基变量(都是0)。由此可得  ，因此  是基本可行解。
  
• 已知  是基本可行解，证明  是极点。设  分别为可行解，且  是它们的凸组合。因为  有  个分量为  ，则对应的分量也必须为0(因为正数的凸组合必大于0)。再根据得到,从而 。因此  是极点。
  

有了这个定理，我们可以将求解极点问题转换为求解基本可行解问题。然后再基本可行解集中寻找最优解。即，线性规划问题的求解，可归结为求最优基本可行解。这也正是单纯形方法的基本出发点。
1.3.3 基本可行解的存在问题

直接给出定理而不加证明。
定理：如果 有可行解，则一定存在基本可行解。
2 单纯形方法

2.1 单纯形方法的概念和原理

上文已经探讨了线性规划最优解与基本可行集的关系，即如果线性规划具有最优解，它一定能在基本可行解中找到。我们可以先找到所有的基本可行解，然后代入目标函数，寻找最大值。然而，一个  的系数矩阵可能有多达  个基本可行解，如果 ，那么时间复杂度会很高。所以应该改良这种暴力算法，采用一种更高效的方法。这就是成熟的单纯形法(Simplex Algorithm or Simplex Method)。
这部分内容不打算按照课本那样用定理和公式来解释单纯形法(但是重要的推导还是有必要的)，而是着重于剖析其原理。由于“基本可行解”和“极点”的定价性，下文可能将二者混用，以便更好地理解。
首先介绍单纯形法的思想：相对于暴力算法，单纯形法从一个基本可行解切换到另一个基本可行解时，不是盲目的切换。首先，它只会沿着边(edge)切换到与它相邻的极点。其次，它只会切换到能改良优化目标的极点。重复这样的做法，直到再也找不到能改良优化目标的相邻极点时，此刻所在的极点就是本次线性规划的最优解。这种做法的合理性基于以下事实：若一个极点不是线性规划的最优解，则它的一个相邻极点比它更优。


那什么样的相邻极点是更好的呢？不妨设此时所在的极点是  ，它的一个相邻极点是  。则如果 的方向与目标函数的负梯度方向成锐角，那么  一定比  更优(这是显然的)。用数学公式描述为 。
我们就以该不等式为出发点探究  应满足什么条件。
首先，规定一些符号。从 中抽取其所有基变量组成  维向量 ,剩余的非基变量组成 维向量 （基本可行解的非基变量都是零）。类似地，分别从 中抽取出 。然后从  中抽取与  相同位置的变量, 。
强调一下， 不是代表  的基变量组成的向量，它只是代表和 位置而已，同样也不是零向量(后面会说它的含义)。
下面正式开始推导。


注意  是任取的。也就是说，只要满足  就说明还有优化空间,即从  切换到  ；否则，意味着  就是该问题的最优解。
问题转变为我们从当前极点，挑选满足不等式的相邻极点，然后切换到该极点就完成了一次优化的迭代。那如果多个极点满足该条件呢？理论上我们应该取 最大的那个。可是，这要求要找出当前极点的所有相邻极点，也需要很大的计算量(虽然比暴力解法确实进步了)。所以，可以退而求其次，取使 最大的就行，因为这个是不需要其他极点就能计算的。
在继续讨论之前，我们给出  的含义。我们知道当从一个极点移动到另一个极点时，非基变量中有且仅有一个会从0增加到一个正值。由于 是相邻极点，是0向量，所以中有一个元素为正值，其余全是0。
现在来探究一下意味着什么。
将不等式写成分量形式： ，其中 是非基变量的下标集合。再设中不为0的元素下标为  ，则不等式可进一步化简为 。令 ,称为判别数。
所以这个不等式的意思其实是：如果当前所在极点存在某个属于非基变量下标集合的下标  ,它对应的各参数满足这个不等式，那么我们可以让  成为新的基矩阵的元素，这个基矩阵对应的基本可行解优于当前可行解。
那如果有多个下标  满足该不等式呢？当然是选取 。注意，我们没有计算所有的相邻极点，而是根据  的特殊结构，计算出所有的相邻极点对应的判别数 ，再取它们中最大的对应的下标，作为新入基列的下标。有列入基，就有列出基，因为基矩阵只容纳  个列。那应该怎么选择出基的那一列呢？
为了便于说明，先将问题作一个化简：我们令 。这总是可以通过行初等变换做到，相应的 也同时做一样的行初等变换以保持解不变。这样变换后的  的值就是基变量的取值（如果  经过行初等变换后有负的元素，那就说明这个基矩阵对应的基本解不可行，应该重新寻找基矩阵）。当有新列入基时，我们将该列变换为  中的某一列，即只有一个元素为1，其余元素都为0；然后，与新列重复的那一列出基。那么我们应该将新列的哪个元素(主元)变换为1呢？设新列的第  个元素为  ，取  对应的那个下标。因为只有这样才能保证在行初等变换时，不会把  中的元素消为负数。还有一个问题是，如果新入基列  中所有元素都小于等于0呢？这样的话，  是不存在的(因为 必定非负)。实际上，出现了这样情况说明该线性规划问题无最优解(目标函数可以任意小)。
2.2 单纯形方法的步骤

介绍完单纯形方法的原理，步骤也就呼之欲出了。这里简要做一个总结。

• 将线性规划问题转换为标准形式
  
• 在系数矩阵  中寻找一个基矩阵  ，并通过行初等变换将它转换为单位矩阵  。如果此时 ，则重新寻找基矩阵并转换为单位阵，直到 。
  
• 计算 中每一列对应的判别数 ，然后取 。如果 ，则当前基本可行解就是最优解，算法停止。否则，若 ，则说明线性规划无最优解，算法停止。否则，选择  作为入基列。
  
• 计算 对应的  ，将  作为主元，通过行初等变换将主元化为1，其余元素化为0，实际完成了入基。返回步骤3。
  

PS: 操作过程中，一定要注意各参数的对应。比如如果基矩阵 ，那么相应的 ，而不是简单得按照顺序取 等等。
2.3 两阶段法

上面给出了单纯形方法的原理和步骤，对线性规划问题给出了一个成熟优雅的方案。但是，还是有一点小瑕疵，那就是单纯形方法的第一步：寻找初始的基本可行解。如果系数矩阵  中存在能组成单位矩阵的列向量，那就很完美，我们已经找到了一个基本可行解。但若不存在单位矩阵呢？一般情况下，很难直接看出哪些列是线性无关的。因此 ，我们需要人为地构造出一个单位矩阵来提供初始的基本可行解。两阶段法和大M法提供了这样的功能。本小节简要介绍两阶段法；下一节简要介绍大M法。
2.3.1 两阶段法的思想

在一个标准线性规划问题中，一般不存在现成的单位矩阵，两阶段法通过引入人工变量 ，将  的每个元素添加到每个方程中，等价于在  右端增加了一个单位向量  。但是这个做法已经破坏了方程组的结构，没关系，后续的处理(即第一阶段)会讲人工变量逼出基变量，从而消除这个不好影响。
2.3.2 第一阶段

求解一下线性优化问题，以消除人工变量的影响：


其中 。
因为有初始基本可行解，且目标函数有下届，所以必存在最优基本可行解，设为 。此时，有三种情况：

• ，则原线性规划无可行解。因为若原线性规划有可行解，则 是这个线性规划的可行解，则目标函数可以取0，矛盾。
  
• 且  的分量都是非基变量。则  个基变量都是原线性规划的基变量。
  
• 且  的某些分量是基变量。这时可以使用主元消去法，将这些元素离基，得到不含人工变量的基变量。
  

2.3.3 第二阶段

用第一阶段得到的基，求解原线性规划问题。
2.4 大M法

2.4.1 大M法简要介绍

大M法和两阶段法类似，都是通过引入人工变量构造单位矩阵，然后迫使人工变量离基。但大M法只需要一个阶段，它的思想是在目标函数上加上很大的倍数M的人工变量的惩罚项，在优化过程中使人工变量必须为0。大M法其实是两阶段法中两个阶段的结合。
大M法求解以下线性规划问题。


其结果必是下面三种情况之一：

• 达到线性规划最优解，且  ,则此时  就是原线性规划最优解。
  
• 达到线性规划最优解，且  ，则原线性规划问题无可行解。
  
• 不存在有限最优值，则原线性规划问题无界或无可行解。
  

参考

• ^https://en.wikipedia.org/w/index.php?title=Linear_programming&oldid=1054533005