An Interior-Point Algorithm for Linear Programming with Optimal Selection of Centering Parameter and Step Size

doi:10.1007/s40305-020-00312-x

Abstract

Abstract: For interior-point algorithms in linear programming, it is well known that the selection of the centering parameter is crucial for proving polynomiality in theory and for efficiency in practice. However, the selection of the centering parameter is usually by heuristics and separated from the selection of the line-search step size. The heuristics are quite different while developing practically efficient algorithms, such as Mehrotra's predictor-corrector (MPC) algorithm, and theoretically efficient algorithms, such as short-step path-following algorithm. This introduces a dilemma that some algorithms with the best-known polynomial bound are least efficient in practice, and some most efficient algorithms may not be convergent in polynomial time. Therefore, in this paper, we propose a systematic way to optimally select the centering parameter and linesearch step size at the same time, and we show that the algorithm based on this strategy has the best-known polynomial bound and may be very efficient in computation for real problems.

Key words: Interior-point method, Convergence, Polynomial algorithm, Linear programming

CLC Number:

90C05
90C51

Ya-Guang Yang. An Interior-Point Algorithm for Linear Programming with Optimal Selection of Centering Parameter and Step Size[J]. Journal of the Operations Research Society of China, 2021, 9(3): 659-671.

TrendMD

References

[1] Andersen, E.D., Gondzio, J., Meszaros, C., Xu, X.:Implementation of interior-point methods for large scale linear programming. In:Terlaky, T. (ed.) Interior Point Methods of Mathematical Programming, pp. 189-252. Kluwer Academic Publishers, Dordrecht (1996)
[2] Bai, Y.Q., El Ghami, M., Roos, C.:A comparative study of kernel functions for primal-dual interiorpoint algorithms in linear optimization. SIAM J. Opitm. 15, 101-128(2004)
[3] Cartis, C.:Some disadvantages of a Mehrotra-type primal-dual corrector interior point algorithm for linear programming. Appl. Numer. Math. 59, 1110-1119(2009)
[4] Cartis, C., Gould, N.I.M.:Finding a point in the relative interior of a polyhedron. Technical Report NA-07/01. Oxford University, Computing Laboratory (2007)
[5] Davis, T.A.:Multifrontal multithreaded rank-revealing sparse QR factorization, Technical Report, Department of Computer and Information Science and Engineering, University of Florida (2008)
[6] Klee, V., Minty, G.:How good is the simplex algorithm? In:Shisha, O., (eds.) Inequalities, Vol. III, pp. 159-175, Academic Press, New York (1972)
[7] Kojima, M., Megiddo, N., Mizuno, S.:A primal-dual infeasible-interior-point algorithm for linear programming. Math. Program. Ser. A 61, 261-280(1993)
[8] Luenberger, D.G., Ye, Y.:Linear and Nonlinear Programming. Springer, New York (2008)
[9] Lustig, I.J., Marsten, R.E., Shanno, D.F.:Computational experience with a primal-dual interior point method for linear programming. Linear Algebra Appl. 152, 191-222(1991)
[10] Mehrotra, S.:On the implementation of a primal-dual interior point method. SIAM J. Optim. 2, 575-601(1992)
[11] Monteiro, R., Adler, I., Resende, M.:A polynominal-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension. Math. Oper. Res. 15, 191-214(1990)
[12] Nocedal, J., Wright, S.J.:Numerical Optimization. Springer, New York (1999)
[13] Peng, J., Roos, C., Terlaky, T.:Self-Regularity:A New Paradigm for Primal-Dual Interior Point Algorithms. Princeton University Press, Princeton (2002)
[14] Roos, C., Terlaky, T.:and J-Ph, Vial, Theory and Algorithms for Linear Optimization:An Interiorpoint Approach. Wiley, Chichester (1997)
[15] Salahi, M., Peng, J., Terlaky, T.:On mehrotra-type predictor-corrector algorithms. SIAM J. Optim 18, 1377-1397(2007)
[16] Shmakov, F.S.L.:A universal method of solving quartic equations. Int. J. Pure Appl. Math. 71, 251-259(2011)
[17] Todd, M.J.:The many facets of linear programming. Math. Program. Ser. B 91, 417-436(2002)
[18] Wright, S.:Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997)
[19] Yang, Y.:Arc-Search Techniques for Interior-Point Methods. CRC Press, Boca Raton, FL (1997)
[20] Yang, Y.:A polynomial arc-search interior-point algorithms for convex quadratic programming. Eur. J. Oper. Res. 215, 25-38(2011)
[21] Yang, Y.:A Polynomial Arc-Search Interior-Point Algorithm for Linear Programming. J. Optim. Theory Appl. 158(3), 859-873(2013)
[22] Yang, Y., Zhou, Z.:An analytic solution to Wahba's problem. Aerosp. Sci. Technol. 30(1), 46-49(2013)
[23] Ye, Y.:Interior-Point Algorithms:Theory and Analysis. Wiley, New York (1997)
[24] Zhang,Y.:SolvingLarge-scaleLinearProgramsbyInterior-PointMethodsUndertheMatlabEnvironment. Technical Report TR96-01. Department of Mathematics and Statistics, University of Maryland, Maryland (1996)