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

An Interior-Point Method With a New Iterative Scheme

研究了求解线性规划问题的二阶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.