摘要
提出了一种新的内点算法——宽邻域预估校正算法。该算法基于经典预估校正算法思想,把窄邻域拓展到宽邻域里,使算法更快地迭代。给出了算法的具体步骤,讨论了其计算复杂性,分析结果表明,所给算法是一多项式时间算法。通过数值实验验证算法的有效性。
A new interior point wide-neighborhood predictor-correcting algorithm is presented for a linear programming problem. On the basis of the idea of a predictor-correcting algorithm, the iteration of our algorithm is faster in a wide-neighborhood than in a narrow one. The concrete steps of the algorithm are introduced, its computational complexity is discussed, and the results indicate that the algorithm is a polynomial-time one. The validity of the algorithm is confirmed though a numerical experiment.
出处
《山东大学学报（理学版）》
CAS
CSCD
北大核心
2009年第7期66-70,76,共6页
Journal of Shandong University(Natural Science)
基金
国家自然科学基金资助项目(10872085)
四川省教育厅青年基金资助项目(08zb046)
关键词
线性规划
宽邻域
预估校正算法
复杂度
linear programming
wide-neighborhood
predictor-eorrector algorithms
complexity
