线性规划的非可行的内点算法

摘要

首先简要介绍非可行的内点算法,然后提出一种新的中心路径的取法,并由此给出一个对Kojima-Megiddo-Mizuno算法的改进的方法,这一新的算法是具有O(n2L)次收敛性的算法,并对这一算法的收敛性加以证明,这一新的算法与其它算法最明显的差异是不必假设LP解的存在性,就可以证明原始—对偶问题的多项式时间收敛性。文章的最后通过数值实验将该算法与Ye的解决线性规划的中心路径算法进行了比较。比较的结果显示新的算法从各个方面都要优于Ye的算法。