线性规划中几种内点算法的比较
来源:用户上传
作者: 林育山
[摘要] 该文是关于内点算法的一篇综述，对几种较为实用的求解线性规划问题的算法进行总结，包括单纯形法、椭球算法、Karmarkar算法、原仿射尺度算法等，并对这些算法进行比较。
[关键词] 线性规划 内点算法 比较
1 问题的提出
1947年，美国数学家G.B . Dantzig提出了求解线性规划问题的通用方法――单纯形法，大量的实际应用表明，单纯形法是一种行之有效的解线性规划问题的算法。但是在理论上，单纯形法并不是一个“好算法”，特别是在1972年美国学者V.Klee与G.L.Minty发表了一个例子，通过构造一个病态的线性规划，说明了单纯形法在解决某些极端的例子中效果不好，很多研究线性规划的数学家开始探讨解线性规划的NP问题。1979年，前苏联数学家哈奇扬发表了椭球算法，并证明了该算法是个多项式时间算法，说明线性规划的多项式时间算法是存在的，但在实际应用中，这一算法并没有很强的实用性。1984年，在美国贝尔实验室工作的印度籍数学家N.Karmarkar提出了解线性规划的投影尺度法，这也是一个多项式时间算法，它比椭球法优化了很多，这一工作一时引起了很多数学家对内点算法的研究热情，在不断的改进中，一些新的、改进的或变形的内点算法相继出现。无论是内点算法还是椭球算法，它们有一个共同点，就是采用了非线性规划的一些思想来解决线性规划问题。
2 几种算法的简单介绍
2.1 单纯形法
将线性规划问题（LP）写成如下的矩阵形式：
式（1）可以用分块矩阵写成如下形式： （2）
设B是A的一个基，不失一般性的，设它由A中的前m列所组成，由高等代数的知识，必可将矩阵（1）通过初等变换注：
①若式（4）满足 ，称（4）为单纯形法下的标准型。
②若问题（LP）有可行解，则必有基本可行解，故可知 。
单纯形法的具体步骤如下：
Step1 列出初始表，在表中找到一个初始基，化为标准形，得到对应初始基的基本可行解。
Step2 检查标准形表上的检验数(ci=m+1, …, n)是否均为正数，若是，则停止，当前的基本可行解为最优解，否则，进入Step 3。
Step3 任取小于0的(ci=m+1, …, n)，若集合 ，停止求解，规划问题有无界解，否则，进入Step 4。
Step4 此时，以 为入基变量，求出
，（若最小值在不止一个指标处达到，则任取一个指标作为r即可），则 为离基变量。
Step5 以 为主元进行转轴，得到新的基本可行解及标准形表，回到Step 2。
在前面单纯形法的介绍中，我们强调了一个非退化的前提，在退化的情况下，用上面的步骤去迭代时，可能出现死循环，对于这个问题，先后有Charnes提出了摄动法，Dantzig、Orden、Wolfe提出了字典序法以及Bland提出了Bland法则，本论文中我们仅介绍Bland法则。
Bland法则：在迭代的过程中，如果检验数有多个为负，则选其中下标最小的检验数相对应的变量为入基变量，如果 有多处同时达到的话，也取下标最小者对应的变量为离基变量。
2.2 椭球算法
如果能够找到求解严格不等式组多项式时间算法，那么就有（LP）问题的多项式时间算法。椭球算法就是一种通过寻求严格不等式组的多项式时间算法，来证明线性规划问题有多项式时间算法。可以理解为把线性规划问题转化为（8）的形式，即为弱不等式组，然后求出相应的严格不等式组的解，从而导出弱不等式组的解，则可以求出原线性规划问题的最优解。所以椭球算法的本质是求严格不等式组的解。下面简单介绍一下椭球算法的原理。
椭球算法的目标是求解严格不等式组(9) 的解。
设A，b的元素都是整数，n，m>1，并将不等式组(9)的解集用K来表示，椭球算法的基本思想是首先选取一个很大的球 ，由于足够大，只要 ，则可以认为 ，然后用一个迭代，依次产生一系列的椭球 一般的设 ，将 分成两半，其中必有一半与 的交非空，设法产生另一个椭球 ，使其包含着 的这一半，从而保证 。另一方面，又要求 的体积至多为 的 倍，随着迭代的进行，椭球的体积不断减少，逐步趋于0，但其中包含着 的点，最后可以得到不等式组的解。
2.2.1 基本定义
仿射变换：Q为非奇异阵， 是n维列向量，称变换 为 的仿射变换。
旋转变换：若仿射变换 满足 以及 ，则称它为旋转变换。
单位球：称集合 为单位球。
椭球： 是一个仿射变换，称 为一个椭球，可以得到
则令 ，返回2。
2.3 Karmarkar算法
Karmarkar算法运用了求解非线性规划问题的思想来解决线性规划问题。这种算法是在把一般线性规划问题转化为Karmarkar所特有的标准型，再利用一种求解这种标准型的算法最终求出最优解。Karmarkar算法把线性规划问题转化成它所要求的那种标准型，我们称之为Karmarkar标准型，形式如下：
s.t (10)
其中这个标准型还要求满足以下三个条件：
① A为m×n矩阵，c为n维列向量， ，并不失一般性的，假设秩(A)为m；
② 问题(10)是可行的，单纯形 的中心 是可行解；
③ 对于每个的可行点x，有 ，且最优目标函数值为0。
Karmarkar算法的具体步骤：
下面对Karmarkar算法从一个迭代点寻求下一个迭代点的原理进行解释。
该方法的基本思路是寻找一个变换，它将上面所说的单纯形S映射到自身，且把 映射到单纯形中心 。为此，令矩阵 ，做变换 。
容易验证 ，即变换T把可行点 变换到单纯形的中心，这就保证了搜索总是在单纯形内部进行。
是一个线性分式变换，易知其逆变换为
利用这两个公式，Karmarkar标准型就变换成关于 的如下问题：
由于变换T将目标函数变为非线性函数，从而不再是线性规划问题，为此把它的目标函数暂且近似为 ，并且令 ，从而考虑如下定义的线性规划问题：
试寻找某一方向 ，使其从单纯形中心 出发，沿该方向移动时既可以保证可行性，又使目标函数之有所下降，为此要求也即 。
因此可取 为向量 在B的零空间N（B）=投影，
即。
由于A是行满秩，则显然有 为正定阵，从而逆阵存在。
由于单纯形S的内切球半径 ，因此为保证约束条件 满足，从中心 出发，移动的距离不超过 ，在前面的Karmarkar算法的介绍中，我们看到实际上取的是
，其中取 ，
再把 通过逆变换 ，把它变换为 ，即为新的迭代点。
注:
①对于 取 在 上的投影的原因解释：
由于 取 在 上的投影，则 ，其中 ，因此 ， ②对单纯形的内切球半径 的解释：
由于单纯型S的中心为 ，内切球与单纯型S的边的交点为
2.4 原仿射尺度算法
原仿射问题与上面介绍的两种内点算法不同，它是可以求解标准形式的线性规划问题LP：
现设 ，原仿射尺度算法的思想就是从 中找到一个内点可行解，然后寻求一个使目标函数下降的可行方向，沿该方向得到下一个内点可行解，从本质上来讲，原仿射尺度算法也是采用了非线性规划的思想来解决线性规划问题。
问题：对于初始点位于 的中心位置的情况，可以选取最速下降方向作为迭代方向，但对于初始点 偏离中心位置而与某边特别靠近时，这样的迭代方向可能会出现不利于题目的实际情况的问题。为此原仿射尺度借鉴了Karmarkar算法中的方法，取迭代方向为目标函数系数向量在约束条件的系数矩阵的零空间的投影方向的反方向，这样既可以满足约束条件，又可以使目标函数值下降。因此，原仿射尺度算法主要做的有三方面的事情：一是把原始点 变换为中心位置，二是选取迭代方向以及确定步长，三是确定迭代何时停止。下面就如何实现这些目标进行解释。
对于 ，令 ，由 知， 可逆。
变换 ，
则 经过变换后变为 ，这使得了 到非负卦限的每个界面的距离相等，由于 可逆，则显然 是存在的，其逆变换为 ，则(LP)等价于
由对偶理论，当 为原问题和对偶问题的最优解，则有 ，因此，我们只需定 为一很小的常数，当 ，则停止。
原仿射尺度算法与Karmarkar算法在构造原理上有很多的相似之处，它的好处是不用把一般的线性规划问题转化为Karmarkar标准型，由于把一般的问题转化为Karmarkar标准型并不容易，所以原仿射尺度算法在实际应用中是很受推崇的。但是原仿射尺度算法在理论上并未被证明是一个多项式时间算法。
3 几种算法的比较
在基本可行解中寻找最优基本可行解 指数形时间算法 大量的实际应用证明单纯形法是一种行之有效的解线性规划问题的算法，但对于一些极端的问题，单纯形法效果不好
椭球算法 把解决线性规划问题转化为求解严格不等式组 通过不断缩小严格不等式组的解所在的椭球的体积，最终确定是否有解 多项式时间算法 椭球算法证明了求解线性规划问题的多项式时间算法的存在，但在实际应用中，远没有单纯形法好用
Karmarkar算法 把解决线性规划问题转化求解Karmarkar标准型的问题 从可行解的多面体内部一个点出发，产生一个直接穿过多面体内部的点列，从而得到所需的最优解 多项式时间算法 是一种行之有效的多项式时间算法，但把一般的线性规划问题转化为Karmarkar标准型并不容易
原仿射尺度算法 可以直接求解线性规划问题 在寻找迭代点的原理上与Karmarkar算法原理相似，但在确定何时停止迭代运用了线性规划的对偶理论 在理论上还未被证明是多项式时间算法 实际效果优于Karmarkar算法，在中大规模的线性规划问题上，它们的求解效率优于单纯形法
参考文献：
[1] 张建中，许绍吉. 线性规划[M]. 北京: 科学出版社，1990.
[2] 姚恩瑜，何 勇，陈仕平. 数学规划和组合优化[M]. 杭州: 浙江大学出版社，2001.
[3] Papadimitriou H C，Steiglizt K.，Combinatorial optimization algorithms and complexity[J]. Printice-Hall,1982.
[4] P.GaCs and L.Lovasz. Khachian’s algorithm for linear programming[J]. Math,Programming Study 14 (1981): 61-68.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
转载注明来源:https://www.xzbu.com/1/view-242978.htm
