线性规划基于修正牛顿方向的宽邻域内点算法  

Wide-Neighborhood Interior-Point Algorithm Based on Modified Newton Direction for Linear Programming

作　　者：汪威威[1,2] 刘红卫[1] 毕红梅[3] 

机构地区：[1]西安电子科技大学数学与统计学院,西安710126 [2]西安工业大学理学院,西安710032 [3]空军工程大学理学院,西安710051

出　　处：《吉林大学学报（理学版）》2014年第3期408-412,共5页Journal of Jilin University:Science Edition

基　　金：国家自然科学基金(批准号:61072144;61179040)

摘　　要：通过修正经典宽邻域算法的搜索方向,提出一种新的求解线性规划问题的宽邻域内点算法,并对算法进行收敛性分析,证明了该算法具有经典宽邻域算法的迭代复杂性界O(nL).数值实验表明算法是有效的.Based on modifying the search direction of classic wide-neighborhood algorithm,a new wideneighborhood interior point algorithm for linear programming was proposed.The convergence analysis of the new algorithm was presented.And the algorithm enjoys the iteration bound O（nL）,the same as the complexity result for classic wide-neighborhood interior point method.The numerical calculation shows that the new algorithm is efficient.

关 键 词：线性规划 内点算法 宽邻域算法 多项式复杂性 

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