论文部分内容阅读
摘要：内点法是一种求解线性规划和非线性规划问题的多项式算法，其迭代次数与系统规模关系不大。目前，内点法被扩展运用于求解二次规划模型，其计算速度和处理不等式约束的能力已经超过了求解二次规划模型的经典算法。本文主要介绍线性规划中内点法的运用以及对工程实例的计算，并且分析了如何运用内点法迭代原理得到最优解。
关键字：线性规划问题；内点法；最优解；二次规划；
中图分类号：F224文献标识码： A
1 引言
1984年，Karmarkar发现了一个关于求解线性规划的方法，这个方法称作内点法。内点法是罚函数中的一种，与外点法的最大的区别在于该方法利用罚函数生成一系列内点来逼近原约束问题的最优解。罚函数的作用是对企图脱离可行域的点给予惩罚，相当于在可行域的边界设置了障碍，不让迭代点穿越到可行域之外。内点法在迭代中总是从可行点出发，并保持在可行域内部进行搜索。后得出最优解。对于不等式约束的最优化问题，比较适合用内点法来解决。经过实际计算结果得出内点法与单纯形法存在着很大的可比性。在线性规划问题中，内点法比起单纯形法来说迭代次数更少，所以计算速度更快，从求得的结果来看，收敛性也比较好。内点法中比较常用的方法是最速下降法和牛顿法。最速下降法在解析法中是属于比较古老的一种，受该方法的启发，渐渐得到了其他不同的解析方法。最速下降法每次迭代的计算量很小，解法简单。如果从一个不好的初始点出发，也能收敛到局部极小点。迭代原理的应用对于解决线性规划和非线性规划问题中具有至关重要的作用。
2 内点法
2.1运筹学
运筹学[1]到现在都没有一个相对比较统一的定义，这正是因为它使用的复杂性以及使用的广泛性，也凸显出了它另一方面的独特魅力。以下是我查阅大量书籍后对运筹学所给出的定义：运筹学是一门在现有的技术及理论条件下，对问题现状的分析强调最优化决策的科学方法。
运筹帷幄之中，决胜千里之外这其中的运筹两字是赤壁之战的核心与关键，是整个战争通敌制胜的法宝。可见运筹学的运用自古有之。运筹学在古代生活与战争的应用可追溯到商朝时期，甚至更远。有人类就有运筹，有生活就有规划。这句话就已经说明运筹学在我们的生活中的普遍性。在第2次世界大战之后到现在的60多年来，运筹学这学科已变得非常完善，逐渐形成了相当庞大的分支。作为一门庞大的新兴学科，运筹学在现代生产与管理中有着极其广泛的应用，运筹学解决了在生产及经营中企业碰到的很多问题，有效的增进了企业的现代化、科学化管理，为企业的经济带来巨大的收益。因此，很多企业一直十分重视运筹学在实际中的应用。现代社会中，随着资源的优化利用与配置的合理化，管理以及經济计划的综合化和科学化。运筹学的应用十分广泛，目前正在向一些新的研究领域发展。其中运筹学中越来越受到重视的是建立模型的问题。在实际生活中，运筹学工作者经常碰到的难题是如何把一个实际问题转化成一个可以用数学方法或其他方法来解决的问题。实际问题中的运筹学问题，它的计算量一般都是很大的，所以运筹学的快速发展和计算机的迅速崛起有着密不可分的联系。如果有了计算速度快，存储量大的计算机，一定能更加快速的推动运筹学的发展。运筹学在短短60年的时间里，能够发展的如此迅速，已经可以说明很多问题。说明运筹学越来越得到人们的重视，作为一门学科，在理论和实际应用方面，都发挥出巨大的作用，前景十分广阔。
2.2 线性规划模型
线性规划[2]问题的一般形式为：
Maxc=
s.t.=
2.3 内点法的基本概念
内点法[3]的基本原理是用最速下降法从起点开始寻找一个下降方向，起点在“宇宙中心”，因为起点走出去第一步效果最好，所以应该想办法使每一次走出去都是第一步。Karmarkar[4]提出的内点法有点类似于单纯形法，其中两者的区别在于单纯形法是沿着可行域边界寻优，而内点法则是从可行域内部寻优。因为内点法的收敛性与计算速度均优于单纯形法，计算时间比单纯形法快50倍，所以对于各种大规模、复杂的线性规划问题，人们常常用内点法来解决。内点法对于线性规划和非线性规划问题可以统一解法，是一种具有多项式时间复杂性的算法。
2.4 原始--对偶内点法
原始-对偶内点法[5] 对原问题和对偶问题的信息进行了充分的利用，从可行域内部开始，通过多次迭代，得到原问题的最优解，主要考虑如下规划问题:
(2.1)
其中：
加入松弛变量得到如下形式：
（2.2）
那么(2.2)式的一阶KKT条件为：
（2.3）
其中：为的对角矩阵，
对于(2.3）进行扰动，求得扰动的KKT条件：
（2.4）
原始对偶内点法釆用牛顿迭代非线性方程组(2.4)，在牛顿迭代的过程中令，扰动因子，最后(2.4)的解逼近于(2.3)的解,这样就得到了式子(2.1)的KKT条件。
接下来，我们需要得到一个牛顿方向，所以在牛顿迭代中的第k步中，求解如下方程：
（2.5）
其中：，与(2.4)式中相同。将(2.5)式记做：。
最后，进行若干次牛顿迭代后，足够小了，原始对偶内点法就求出了式子(2.1)的最优解。
2.5预测校正内点法
预测校正内点法[6]是对原始对偶内点法的扩展，提高了计算收敛的速度，大幅度提高非线性内点法的性能。
该方法的思想如下：
1.为解式子（2.5），将进行分解：
2.令式子（2.5）中，解式子（2.5），得到仿射方向，
3.沿仿射方向走至最远，得到点，此处，最远是指不违背变量的非负约束。
4.求得新点的对偶间隙：。
5.则得到新的，其中：为当前对偶间隙。
6.将代入(2.5)中,令，并引入二阶误差，解(2.5)得到。
7. ，得到预测校正的牛顿方向。
2.6多中心校正内点法
多中心校正内点法[7]算法能有效的提高求解的收敛性和可靠性。该方法对预测校正内点法进行了改进，它可以进行多次校正，大大减少了计算时间。
3 内点法模型的建立
内点法又称为内罚函数法，罚函数的作用是对企图脱离可行域的点给予惩罚，相当于在可行域的边界设置了障碍，不让迭代点穿越到可行域之外，因此也称为障碍函数。
对数障碍函数
倒数障碍函数
算法步骤：
Step 1选取初始数据.给定初始内点，初始参数，缩小系数，允许误差，令.
Step 2求解无约束问题.以为初始点，求解无约束问题，设其最优解为.
Step 3检查是否满足终止准则.若，则迭代终止，为约束问题
的近似最优解；否则，令，返回Step 2 .
4实例
利用对数障碍函数求解不等式约束问题
要求选取.
解：引入对数障碍函数
，
用解析方法求解问题
其中令
解得，其中
.
依次对用上述公式计算，结果如表1所示，
表4-1计算结果表
表中每一个值都对应intS中的一个可行内点。
当即时，无约束问题的最优解点列从约束问题的可行域内部，向可行域边界上的最优解逼近.
5 结论
两个多月以来，通过对各种文献的翻阅查找以及自己的一些理解，本人对内点法的现状与应用前景进行了一个小小的总结。目前，内点法在各种优化问题中已经取得了很大的发展，尤其是在求解电力系统方面更是尤为突出。其中，内点法中应用得最多的是仿射尺度法和路径跟踪法。仿射尺度法的结构比较简单，计算效率较高。而路径跟踪法除了计算速度快以外，还有收敛性好和处理病态问题能力强的优点。总而言之，目前内点法已经应用于各种不同的生活实际问题当中，具有很大的研究价值，未来的发展前景十分可观。
参考文献：
[1]蒋智凯.浅谈运筹学教学[J].重庆科技学院学报(社会科学版),2010.
[2]涂为员.线性规划的优面算法[J].南昌大学学报(理科版)，2002.
[3]陈宝林.最优化理论与算法.北京：清华大学出版社，2005.
[4]关履泰.龚大平.陈辉汉.用线性分式规划的多项式算法改进线性规划的Karmarkar方法[J].工程数学学报，1990.
[5]陈宝林.最优化理论与算法.北京；清华大学出版社，2005.
[6]S.J. Wright.Primal-Dual Interior-Point Methods [M].SIAM, Philadelphia.USA,1997.
[7]S. Mehrotra. On the implementation of a (primal-dual) interior point method[J].SIAMJournal on Optimization, 1992,2: 575-601.
关键字：线性规划问题；内点法；最优解；二次规划；
中图分类号：F224文献标识码： A
1 引言
1984年，Karmarkar发现了一个关于求解线性规划的方法，这个方法称作内点法。内点法是罚函数中的一种，与外点法的最大的区别在于该方法利用罚函数生成一系列内点来逼近原约束问题的最优解。罚函数的作用是对企图脱离可行域的点给予惩罚，相当于在可行域的边界设置了障碍，不让迭代点穿越到可行域之外。内点法在迭代中总是从可行点出发，并保持在可行域内部进行搜索。后得出最优解。对于不等式约束的最优化问题，比较适合用内点法来解决。经过实际计算结果得出内点法与单纯形法存在着很大的可比性。在线性规划问题中，内点法比起单纯形法来说迭代次数更少，所以计算速度更快，从求得的结果来看，收敛性也比较好。内点法中比较常用的方法是最速下降法和牛顿法。最速下降法在解析法中是属于比较古老的一种，受该方法的启发，渐渐得到了其他不同的解析方法。最速下降法每次迭代的计算量很小，解法简单。如果从一个不好的初始点出发，也能收敛到局部极小点。迭代原理的应用对于解决线性规划和非线性规划问题中具有至关重要的作用。
2 内点法
2.1运筹学
运筹学[1]到现在都没有一个相对比较统一的定义，这正是因为它使用的复杂性以及使用的广泛性，也凸显出了它另一方面的独特魅力。以下是我查阅大量书籍后对运筹学所给出的定义：运筹学是一门在现有的技术及理论条件下，对问题现状的分析强调最优化决策的科学方法。
运筹帷幄之中，决胜千里之外这其中的运筹两字是赤壁之战的核心与关键，是整个战争通敌制胜的法宝。可见运筹学的运用自古有之。运筹学在古代生活与战争的应用可追溯到商朝时期，甚至更远。有人类就有运筹，有生活就有规划。这句话就已经说明运筹学在我们的生活中的普遍性。在第2次世界大战之后到现在的60多年来，运筹学这学科已变得非常完善，逐渐形成了相当庞大的分支。作为一门庞大的新兴学科，运筹学在现代生产与管理中有着极其广泛的应用，运筹学解决了在生产及经营中企业碰到的很多问题，有效的增进了企业的现代化、科学化管理，为企业的经济带来巨大的收益。因此，很多企业一直十分重视运筹学在实际中的应用。现代社会中，随着资源的优化利用与配置的合理化，管理以及經济计划的综合化和科学化。运筹学的应用十分广泛，目前正在向一些新的研究领域发展。其中运筹学中越来越受到重视的是建立模型的问题。在实际生活中，运筹学工作者经常碰到的难题是如何把一个实际问题转化成一个可以用数学方法或其他方法来解决的问题。实际问题中的运筹学问题，它的计算量一般都是很大的，所以运筹学的快速发展和计算机的迅速崛起有着密不可分的联系。如果有了计算速度快，存储量大的计算机，一定能更加快速的推动运筹学的发展。运筹学在短短60年的时间里，能够发展的如此迅速，已经可以说明很多问题。说明运筹学越来越得到人们的重视，作为一门学科，在理论和实际应用方面，都发挥出巨大的作用，前景十分广阔。
2.2 线性规划模型
线性规划[2]问题的一般形式为：
Maxc=
s.t.=
2.3 内点法的基本概念
内点法[3]的基本原理是用最速下降法从起点开始寻找一个下降方向，起点在“宇宙中心”，因为起点走出去第一步效果最好，所以应该想办法使每一次走出去都是第一步。Karmarkar[4]提出的内点法有点类似于单纯形法，其中两者的区别在于单纯形法是沿着可行域边界寻优，而内点法则是从可行域内部寻优。因为内点法的收敛性与计算速度均优于单纯形法，计算时间比单纯形法快50倍，所以对于各种大规模、复杂的线性规划问题，人们常常用内点法来解决。内点法对于线性规划和非线性规划问题可以统一解法，是一种具有多项式时间复杂性的算法。
2.4 原始--对偶内点法
原始-对偶内点法[5] 对原问题和对偶问题的信息进行了充分的利用，从可行域内部开始，通过多次迭代，得到原问题的最优解，主要考虑如下规划问题:
(2.1)
其中：
加入松弛变量得到如下形式：
（2.2）
那么(2.2)式的一阶KKT条件为：
（2.3）
其中：为的对角矩阵，
对于(2.3）进行扰动，求得扰动的KKT条件：
（2.4）
原始对偶内点法釆用牛顿迭代非线性方程组(2.4)，在牛顿迭代的过程中令，扰动因子，最后(2.4)的解逼近于(2.3)的解,这样就得到了式子(2.1)的KKT条件。
接下来，我们需要得到一个牛顿方向，所以在牛顿迭代中的第k步中，求解如下方程：
（2.5）
其中：，与(2.4)式中相同。将(2.5)式记做：。
最后，进行若干次牛顿迭代后，足够小了，原始对偶内点法就求出了式子(2.1)的最优解。
2.5预测校正内点法
预测校正内点法[6]是对原始对偶内点法的扩展，提高了计算收敛的速度，大幅度提高非线性内点法的性能。
该方法的思想如下：
1.为解式子（2.5），将进行分解：
2.令式子（2.5）中，解式子（2.5），得到仿射方向，
3.沿仿射方向走至最远，得到点，此处，最远是指不违背变量的非负约束。
4.求得新点的对偶间隙：。
5.则得到新的，其中：为当前对偶间隙。
6.将代入(2.5)中,令，并引入二阶误差，解(2.5)得到。
7. ，得到预测校正的牛顿方向。
2.6多中心校正内点法
多中心校正内点法[7]算法能有效的提高求解的收敛性和可靠性。该方法对预测校正内点法进行了改进，它可以进行多次校正，大大减少了计算时间。
3 内点法模型的建立
内点法又称为内罚函数法，罚函数的作用是对企图脱离可行域的点给予惩罚，相当于在可行域的边界设置了障碍，不让迭代点穿越到可行域之外，因此也称为障碍函数。
对数障碍函数
倒数障碍函数
算法步骤：
Step 1选取初始数据.给定初始内点，初始参数，缩小系数，允许误差，令.
Step 2求解无约束问题.以为初始点，求解无约束问题，设其最优解为.
Step 3检查是否满足终止准则.若，则迭代终止，为约束问题
的近似最优解；否则，令，返回Step 2 .
4实例
利用对数障碍函数求解不等式约束问题
要求选取.
解：引入对数障碍函数
，
用解析方法求解问题
其中令
解得，其中
.
依次对用上述公式计算，结果如表1所示，
表4-1计算结果表
表中每一个值都对应intS中的一个可行内点。
当即时，无约束问题的最优解点列从约束问题的可行域内部，向可行域边界上的最优解逼近.
5 结论
两个多月以来，通过对各种文献的翻阅查找以及自己的一些理解，本人对内点法的现状与应用前景进行了一个小小的总结。目前，内点法在各种优化问题中已经取得了很大的发展，尤其是在求解电力系统方面更是尤为突出。其中，内点法中应用得最多的是仿射尺度法和路径跟踪法。仿射尺度法的结构比较简单，计算效率较高。而路径跟踪法除了计算速度快以外，还有收敛性好和处理病态问题能力强的优点。总而言之，目前内点法已经应用于各种不同的生活实际问题当中，具有很大的研究价值，未来的发展前景十分可观。
参考文献：
[1]蒋智凯.浅谈运筹学教学[J].重庆科技学院学报(社会科学版),2010.
[2]涂为员.线性规划的优面算法[J].南昌大学学报(理科版)，2002.
[3]陈宝林.最优化理论与算法.北京：清华大学出版社，2005.
[4]关履泰.龚大平.陈辉汉.用线性分式规划的多项式算法改进线性规划的Karmarkar方法[J].工程数学学报，1990.
[5]陈宝林.最优化理论与算法.北京；清华大学出版社，2005.
[6]S.J. Wright.Primal-Dual Interior-Point Methods [M].SIAM, Philadelphia.USA,1997.
[7]S. Mehrotra. On the implementation of a (primal-dual) interior point method[J].SIAMJournal on Optimization, 1992,2: 575-601.