带有新的迭代格式的内点算法  

An Interior-Point Method With a New Iterative Scheme

作　　者：杨喜美[1] 刘红卫[2] 张因奎 

机构地区：[1]河南师范大学数学与信息科学学院,河南新乡453007 [2]西安电子科技大学数学与统计学院,西安710071

出　　处：《应用数学和力学》2014年第9期1063-1070,共8页Applied Mathematics and Mechanics

基　　金：国家自然科学基金(61179040;61303030);广西高校科研重点项目资助(ZD2014050)~~

摘　　要：研究了求解线性规划问题的二阶Mehrotra型预估-矫正内点算法,使用Newton方法求解预估方向和矫正方向,并利用两个方向的一种新的组合方式得到搜索方向.在每次迭代中,要求新的迭代点在中心路径的一个宽邻域内,从而计算出步长参数.通过分析,证明了该算法经过有限次迭代后收敛到问题的一个最优解,并具目前内点算法最好的多项式复杂度O(槡nL).数值实验表明该算法在实践中是有效的.A 2nd-order Mehrotra-type predictor-corrector interior-point method was proposed for linear programming, in which the predictor direction and corrector direction were computed with the Newton method and the search direction was obtained through a new form of combina- tion of the predictor direction and corrector direction. At each step of the iteration, the step size parameter was calculated with the iteration restricted to a wide neighborhood of the central path. Analysis indicates the proposed algorithm converges to the optimal solution after finite times of iteration and has the polynomial iteration complexity O（√nL）, which is the best complexity result for the current interior-point methods. Numerical experiment proves the high efficiency of the proposed algorithm.

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

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