An Interior-Point Method With a New Iterative Scheme
-
摘要: 研究了求解线性规划问题的二阶Mehrotra型预估矫正内点算法,使用Newton方法求解预估方向和矫正方向,并利用两个方向的一种新的组合方式得到搜索方向.在每次迭代中,要求新的迭代点在中心路径的一个宽邻域内,从而计算出步长参数.通过分析,证明了该算法经过有限次迭代后收敛到问题的一个最优解,并具目前内点算法最好的多项式复杂度O(√nL).数值实验表明该算法在实践中是有效的.Abstract: 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 combination 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.
-
[1] Karmarkar N. A new polynomial-time algorithm for linear programming[J].Combinatorica,1984,4(4):302-311. [2] Wright S J.Primal-Dual Interior-Point Methods[M]. Pliladelphia: SIAM, 1997. [3] Peng J, Roos C, Terlaky T.Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms[M]. Princeton: Princeton University Press, 2002. [4] Bai Y, Ghami M, Roos C. A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization[J].SIAM J Optim,2004,15(1): 101-128. [5] Methrostra S. On the implementation of a primal dual interior point method[J].SIAM J Optim,1992,2(4): 575-601. [6] Salahi M, Mahdavi-Amiri N. Polynomial time second order Mehrotra-type predictor-corrector algorithms[J].Appl Math Comput,2006,183(1): 646-658. [7] Liu C, Liu H, Liu X. Polynomial convergence of second-order Mehrotra-type predictor-corrector algorithms over symmetric cones[J].J Optim Theory Appl,2012,154(3): 949-965. [8] Zhang J, Zhang K. Polynomial complexity of an interior point algorithm with a second order corrector step for symmetric cone programming[J].Math Meth Oper Res,2011,73(1): 75-90. [9] Zhang M. A second order Mehrotra-type predictor-corrector algorithm for semidefinite optimization[J].J Syst Sci Complex,2012,25(6): 1108-1121. [10] Liu C, Liu H. A new second-order corrector interior-point algorithm for semidefinite programming[J].Math Meth Oper Res,2012,75(2): 165-183. [11] Liu H, Liu C, Yang X. New complexity analysis of a Mehrotra-type predictor-corrector algorithm for semidefinite programming[J].Optim Method Softw,2013,28(6): 1179-1194. [12] Yang X, Liu H, Zhang Y. A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighbourhood for semi-definite programming[J].Int J Comput Math,2014,91(5): 1082-1096. [13] Yang X, Liu H, Dong X. Polynomial convergence of Mehrotra-type prediction-corrector infeasible-IPM for symmetric optimization based on the commutative class directions[J].Applied Mathematics and Computation,2014,230: 616-628. [14] Ai W, Zhang S. AnO(nL)-iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP[J].SIAM J Optim,2005,16(2): 400-417. [15] Browne S, Dongarra J, Grosse E, Rowan T.The Netlib Mathematical Software Repository[M]. Corporation for National Research Initiatives, 1995. [16] Ai W. Neighborhood-following algorithms for linear programming[J].Science in China, Ser A: Mathematics,2004,47(6): 812-820. [17] Ye Y, Todd J, Mizuno S. AnO(√nL)-iteration homogeneous and self-dual linear programming algorithm[J].Math Oper Res,1994,19(2): 53-67.
点击查看大图
计量
- 文章访问数: 828
- HTML全文浏览量: 35
- PDF下载量: 769
- 被引次数: 0