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

杨喜美; 刘红卫; 张因奎

doi:10.3879/j.issn.1000-0887.2014.09.012

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

doi: 10.3879/j.issn.1000-0887.2014.09.012

¹河南师范大学数学与信息科学学院, 河南新乡 453007;²西安电子科技大学数学与统计学院, 西安 710071

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

详细信息

作者简介:
杨喜美(1982—)，女，河南周口人，博士(通讯作者. E-mail: yangximeiluoyang@126.com);刘红卫(1967—)，男，陕西渭南人，教授(E-mail: liuhongweixidian@126.com);张因奎(1983—)，男，河南信阳人，硕士(E-mail: yangximeixidian@126.com).

中图分类号: O221.1
计量
- 文章访问数: 1026
- HTML全文浏览量: 78
- PDF下载量: 770
- 被引次数: 0
出版历程
- 收稿日期: 2013-12-24
- 刊出日期: 2014-09-15

An Interior-Point Method With a New Iterative Scheme

¹College of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan 453007, P.R.China;²School of Mathematics and Statistics, Xidian University, Xi’an 710071, P.R.China

Funds: The National Natural Science Foundation of China(61179040； 61303030)

摘要

摘要: 研究了求解线性规划问题的二阶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.
- linear programming /
- interior-point method /
- iterative scheme /
- wide neighborhood /
- polynomial complexity

HTML全文

参考文献(17)

[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.