×

Two computationally efficient polynomial-iteration infeasible interior-point algorithms for linear programming. (English) Zbl 1406.90075

Summary: Since the beginning of the development of interior-point methods, there exists a puzzling gap between the results in theory and the observations in numerical experience, i.e., algorithms with good polynomial bounds are not computationally efficient and algorithms demonstrated efficiency in computation do not have a good or any polynomial bound. Todd raised a question in 2002: “Can we find a theoretically and practically efficient way to reoptimize?” This paper is an effort to close the gap. We propose two arc-search infeasible interior-point algorithms with infeasible central path neighborhood wider than all existing infeasible interior-point algorithms that are proved to be convergent. We show that the first algorithm is polynomial and its simplified version has a complexity bound equal to the best known complexity bound for all (feasible or infeasible) interior-point algorithms. We demonstrate the computational efficiency of the proposed algorithms by testing all Netlib linear programming problems in standard form and comparing the numerical results to those obtained by Mehrotra’s predictor-corrector algorithm and a recently developed more efficient arc-search algorithm (the convergence of these two algorithms is unknown). We conclude that the newly proposed algorithms are not only polynomial but also computationally competitive compared to both Mehrotra’s predictor-corrector algorithm and the efficient arc-search algorithm.

MSC:

90C05 Linear programming
90C51 Interior-point methods

Software:

CurveLP; Matlab; LIPSOL; PCx
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Wright, S.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997) · Zbl 0863.65031 · doi:10.1137/1.9781611971453
[2] Mehrotra, S., On the implementation of a primal-dual interior point method, SIAM J. Optim., 2, 575-601, (1992) · Zbl 0773.90047 · doi:10.1137/0802028
[3] Lustig, I.; Marsten, R.; Shannon, D., Computational experience with a primal-dual interior-point method for linear programming, Linear Algebra Appl., 152, 191-222, (1991) · Zbl 0731.65049 · doi:10.1016/0024-3795(91)90275-2
[4] Lustig, I.; Marsten, R.; Shannon, D., On implementing Mehrotra’s predictor-corrector interior-point method for linear programming, SIAM J. Optim., 2, 432-449, (1992) · Zbl 0771.90066 · doi:10.1137/0802022
[5] Monteiro, R.; Adler, I.; Resende, M., A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension, Math. Oper. Res., 15, 191-214, (1990) · Zbl 0714.90060 · doi:10.1287/moor.15.2.191
[6] Kojima, M.; Mizuno, S.; Yoshise, A., A polynomial-time algorithm for a class of linear complementarity problem, Math. Program., 44, 1-26, (1989) · Zbl 0676.90087 · doi:10.1007/BF01587074
[7] Kojima, Masakazu; Mizuno, Shinji; Yoshise, Akiko, A Primal-Dual Interior Point Algorithm for Linear Programming, 29-47, (1989), New York, NY · Zbl 0708.90049 · doi:10.1007/978-1-4613-9617-8_2
[8] Cartis, C., Some disadvantages of a Mehrotra-type primal-dual corrector interior-point algorithm for linear programming, Appl. Numer. Math., 59, 1110-1119, (2009) · Zbl 1163.90042 · doi:10.1016/j.apnum.2008.05.006
[9] Klee, V., Minty, G.: How good is the simplex algorithm? In: Shisha, O. (ed.) Inequalities, vol. III, pp 159-175, Academic Press (1972) · Zbl 0297.90047
[10] Khachiyan, L., A polynomial algorithm in linear programming, Doklady Akademiia Nauk SSSR, 224, 1093-1096, (1979) · Zbl 0414.90086
[11] Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 375-395, (1984) · Zbl 0557.90065 · doi:10.1007/BF02579150
[12] Todd, MJ, The many facets of linear programming, Math. Progr. Ser B, 91, 417-436, (2002) · Zbl 1030.90051 · doi:10.1007/s101070100261
[13] Yang, Y., A polynomial arc-search interior-point algorithm for linear programming, J. Optim. Theory Appl., 158, 859-873, (2013) · Zbl 1274.90494 · doi:10.1007/s10957-013-0281-0
[14] Yang, Y., A polynomial arc-search interior-point algorithm for convex quadratic programming, Eur. J. Oper. Res., 215, 25-38, (2011) · Zbl 1252.90059 · doi:10.1016/j.ejor.2011.06.020
[15] Cartis, C., Gould, N.I.M.: Finding a point in the relative interior of a polyhedron. Technical Report NA-07/01, Computing Laboratory Oxford University (2007)
[16] Yang, Y., CurveLP-a MATLAB implementation of an infeasible interior-point algorithm for linear programming, Numer. Algorithms, 74, 967-996, (2017) · Zbl 1378.65127 · doi:10.1007/s11075-016-0180-1
[17] Zhang, Y., On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem, SIAM J. Optim., 4, 208-227, (1994) · Zbl 0803.90092 · doi:10.1137/0804012
[18] Mizuno, Shinji, Polynomiality of infeasible-interior-point algorithms for linear programming, Mathematical Programming, 67, 109-119, (1994) · Zbl 0828.90086 · doi:10.1007/BF01582216
[19] Miao, J., Two infeasible interior-point predict-corrector algorithms for linear programming, SIAM J. Optim., 6, 587-599, (1996) · Zbl 0856.90075 · doi:10.1137/S105262349325771X
[20] Yang, Yaguang; Yamashita, Makoto, An arc-search \[{\mathcal {O}}(nL)\] O ( n L ) infeasible-interior-point algorithm for linear programming, Optimization Letters, 12, 781-798, (2017) · Zbl 1422.90022 · doi:10.1007/s11590-017-1142-9
[21] Kojima, M., Basic lemmas in polynomial-time infeasible interior-point methods for linear programming, Ann. Oper. Res., 62, 1-28, (1996) · Zbl 0848.90084 · doi:10.1007/BF02206809
[22] Andersen, ED, Finding all linearly dependent rows in large-scale linear programming, Optim. Methods Softw., 6, 219-227, (1995) · doi:10.1080/10556789508805634
[23] Yang, Y.: Arc-search path-following interior-point algorithms for linear programming, Optimization Online. http://www.optimization-online.org/DB_HTML/2009/08/2375.html (2009)
[24] Yang, Y.: An Efficient Polynomial Interior-Point Algorithm for Linear Programming, arXiv:1304.3677 [math.OC] (2013)
[25] Kojima, M.; Megiddo, N.; Mizuno, S., A primal-dual infeasible interior-point algorithm for linear programming, Math. Program. Series A, 61, 261-280, (1993) · Zbl 0808.90093 · doi:10.1007/BF01582151
[26] Czyzyk, J., Mehrotra, S., Wagner, M., Wright, S.J.: PCx User Guide (version 1.1). Technical Report OTC 96/01 Optimization Technology Center (1997)
[27] Zhang, Y.: Solving large-scale linear programs by interior-point methods under the Matlab environment. Technical Report TR96-01, Department of Mathematics and Statistics University of Maryland (1996)
[28] Ng, E.; Peyton, BW, Block sparse Cholesky algorithm on advanced uniprocessor computers, SIAM J. Sci. Comput., 14, 1034-1056, (1993) · Zbl 0785.65015 · doi:10.1137/0914063
[29] Liu, JW, Modification of the minimum degree algorithm by multiple elimination, ACM Trans. Math. Softw., 11, 141-153, (1985) · Zbl 0568.65015 · doi:10.1145/214392.214398
[30] Guler, O.; den Hertog, D.; Roos, C.; Terlaky, T.; Tsuchiya, T., Degeneracy in interior-point methods for linear programming: A survey, Ann. Oper. Res., 46, 107-138, (1993) · Zbl 0785.90067 · doi:10.1007/BF02096259
[31] Gill, PE; Murray, W.; Saunders, MA; Tomlin, JA; Wright, MH, On projected Newton barrier methods for linear programming and an equivalence of Karmarkar’s projective method, Math. Program., 36, 183-209, (1986) · Zbl 0624.90062 · doi:10.1007/BF02592025
[32] Ekefer, J., Sequential minimax search for a maximum, Proc. Amer. Math. Soc., 4, 502-506, (1953) · Zbl 0050.35702 · doi:10.1090/S0002-9939-1953-0055639-3
[33] Luenberger, D.: Linear and Nonlinear Programming, 2nd edn. Addison-Wesley Publishing Company, Menlo Park (1984) · Zbl 0571.90051
[34] Tits, AL; Yang, Y., Globally convergent algorithms for robust pole assignment by state feedback, IEEE Trans. Autom. Control, 41, 1432-1452, (1996) · Zbl 0884.93030 · doi:10.1109/9.539425
[35] Dolan, ED; More, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.