| 线性规划的非可行的内点算法 |
| |
| 引用本文： | 国涓.线性规划的非可行的内点算法[J].沈阳航空工业学院学报,2007,24(2):85-89. |
| |
| 作者姓名： | 国涓 |
| |
| 作者单位： | 东北财经大学数量经济系,辽宁,大连,116025 |
| |
| 摘 要： | 首先简要介绍非可行的内点算法,然后提出一种新的中心路径的取法,并由此给出一个对Kojima-Megiddo-Mizuno算法的改进的方法,这一新的算法是具有O(n2L)次收敛性的算法,并对这一算法的收敛性加以证明,这一新的算法与其它算法最明显的差异是不必假设LP解的存在性,就可以证明原始—对偶问题的多项式时间收敛性。文章的最后通过数值实验将该算法与Ye的解决线性规划的中心路径算法进行了比较。比较的结果显示新的算法从各个方面都要优于Ye的算法。
|
| 关 键 词： | 原始-对偶规划 非可行内点算法 中心路径 |
| 文章编号： | 1007-1385（2007）02-0085-05 |
| 收稿时间： | 2006-11-03 |
| 修稿时间： | 2006-11-03 |
A modified infeasible-interior-point algorithm for linear programming |
| |
| GUO Juan.A modified infeasible-interior-point algorithm for linear programming[J].Journal of Shenyang Institute of Aeronautical Engineering,2007,24(2):85-89. |
| |
| Authors: | GUO Juan |
| |
| Institution: | Department of Quantitative Economic, Dongbei University of Finance and Economics, Liaoning Dalian 116025 |
| |
| Abstract: | 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. |
| |
| Keywords: | primal-dual programming infeasible interior-point algorithm central-path |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
