An Interior-Point Method With a New Iterative Scheme

YANG Xi-mei; LIU Hong-wei; ZHANG Yin-kui

doi:10.3879/j.issn.1000-0887.2014.09.012

Volume 35 Issue 9

Turn off MathJax

Article Contents

Article Navigation > Applied Mathematics and Mechanics > 2014 > 35(9): 1063-1070

YANG Xi-mei, LIU Hong-wei, ZHANG Yin-kui. An Interior-Point Method With a New Iterative Scheme[J]. Applied Mathematics and Mechanics, 2014, 35(9): 1063-1070. doi: 10.3879/j.issn.1000-0887.2014.09.012

Citation:

YANG Xi-mei, LIU Hong-wei, ZHANG Yin-kui. An Interior-Point Method With a New Iterative Scheme[J]. Applied Mathematics and Mechanics, 2014, 35(9): 1063-1070. doi: 10.3879/j.issn.1000-0887.2014.09.012

Citation:

YANG Xi-mei, LIU Hong-wei, ZHANG Yin-kui. An Interior-Point Method With a New Iterative Scheme[J]. Applied Mathematics and Mechanics, 2014, 35(9): 1063-1070. doi: 10.3879/j.issn.1000-0887.2014.09.012

PDF( 373 KB)

An Interior-Point Method With a New Iterative Scheme

doi: 10.3879/j.issn.1000-0887.2014.09.012

¹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)

Received Date: 2013-12-24
Publish Date: 2014-09-15

Abstract

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

FullText(HTML)

References(17)

References

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