线性规划的一个宽邻域预估-矫正内点算法  

A Wide-neighborhood Predictor-corrector Algorithm for Linear Programming

作　　者：刘长河[1] 任建林 

机构地区：[1]河南科技大学数学与统计学院,河南洛阳471023 [2]信阳工业学校,河南信阳465150

出　　处：《平顶山学院学报》2014年第2期6-9,共4页Journal of Pingdingshan University

基　　金：国家自然科学基金(61301229);河南科技大学自然科学基金(2013QN030)

摘　　要：在线性规划的内点算法中,宽邻域算法比窄邻域算法的数值效果好,但宽邻域算法的复杂性比窄邻域差.提出了求解线性规划问题的一个宽邻域预估-矫正内点算法,证明了该算法的迭代复杂性是O(n L),这是线性规划的内点算法中最好的复杂性结果.In interior point algorithm of linear programming,the wide-neighborhood algorithm has a better practical performance compared with narrow-neighborhood algorithm in practice,while the former has a worse complexity than the latter. We propose a new wide-neighborhood predictor-corrector algorithm and prove the iteration complexity of the algorithm is O n L,which is the best complexity result for any interior point algorithm.

关 键 词：线性规划 内点方法 预估-矫正算法 宽邻域算法 多项式复杂性 

分 类 号：O221.1[理学—运筹学与控制论]