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

A modified infeasible-interior-point algorithm for linear programming

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

In this paper ,we introduced infeasible - interior- point algorithm in section 1. In section 2,we presented a modified algorithm for Kojima - Megiddo - Mizuno ,this new algorithm is convergent with . Then we proved the convergence of this new algorithm. The most significant difference between this new algorithm and other algorithms is in that we can proved the primal - dual programming convergence even if there is a solution of LP. In the last section, we compared this new algorithm with the algorithm of Ye＇s central - path algorithm,the result shows that this new algorithm is better than Ye＇s central - path algorithm.