×

Degeneracy in interior point methods for linear programming: A survey. (English) Zbl 0785.90067

Summary: The publication of Karmarkar’s paper has resulted in intense research activity into interior point methods (IPMs) for linear programming. Degeneracy is present in most real-life problems and has always been an important issue in linear programming, especially in the simplex method. Degeneracy is also an important issue in IPMs. However, the difficulties are different in the two methods. In this paper, we survey the various theoretical and practical issues related to degeneracy in IPMs for linear programming.
We survey results, which, for the most part, have already appeared in the literature. Roughly speaking, we shall deal with the effect of degeneracy on the following: the convergence of IPMs, the trajectories followed by the algorithms, numerical performance, and finding basic solutions.

MSC:

90C05 Linear programming
90C31 Sensitivity, stability, parametric optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] I. Adler, N. Karmarkar, M.G.C. Resende and G. Veiga, An implementation of Karmarkar’s algorithm for linear programming, Math. Progr. 44 (1989) 297–335. Errata in: Math. Progr. 50 (1991) 415. · Zbl 0682.90061 · doi:10.1007/BF01587095
[2] I. Adler and D.D.C. Monteiro, A geometric view of parametric linear programming, Algorithmica 8 (1992) 161–176. · Zbl 0767.90042 · doi:10.1007/BF01758841
[3] I. Adler and D.D.C. Monteiro, Limiting behavior of the affine scaling continuous trajectories for linear programming problems, Math. Progr. 50 (1991) 29–51. · Zbl 0719.90044 · doi:10.1007/BF01594923
[4] K.M. Anstreicher, Linear programming and the Newton barrier flow, Math. Progr. 41 (1988) 363–373. · Zbl 0657.90059 · doi:10.1007/BF01580774
[5] M.D. Asic, V.V. Kovacevic-Vujcic and M.D. Radosavljevic-Nikolic, Asymptotic behavior of Karmarkar’s method for linear programming, Math. Progr. 46 (1990) 173–190. · Zbl 0697.90049 · doi:10.1007/BF01585736
[6] M.D. Asic, V.V. Kovacevic-Vujcic and M.D. Radosavljevic-Nikolic, A note on limiting behavior of the projective and the affine rescaling algorithms, Contemp. Math. 114 (1990) 151–157.
[7] M.L. Balinski and A.W. Tucker, Duality theory of linear programs: A constructive approach with applications, SIAM Rev. 11 (1969) 499–581. · Zbl 0225.90024 · doi:10.1137/1011060
[8] E.R. Barnes, A variation on Karmarkar’s algorithm for solving linear programming problems, Math. Progr. 36 (1986) 174–182. · Zbl 0626.90052 · doi:10.1007/BF02592024
[9] E.R. Barnes, Some results concerning convergence of the affine scaling algorithm, Contemp. Math. 114 (1990) 131–139. · Zbl 0724.90038
[10] E.R. Barnes, S. Chopra and D.L. Jensen, A polynomial-time version of the affine scaling algorithm, Working Paper 88-101, Graduate School of Business and Administration, New York University, NY (1988).
[11] D.A. Bayer and J.C. Lagarias, The nonlinear geometry of linear programming, I. Affine and projective scaling trajectories, II. Legendre transform coordinates, Trans. AMS 314 (1989) 499–581. · Zbl 0671.90046
[12] R.E. Bixby, J.W. Gregory, I.J. Lustig, R.E. Marsten and D.F. Shanno, Very large-scale linear programming: A case study in combining interior point and simplex methods, Oper. Res. 40 (1992) 885–897. · Zbl 0758.90056 · doi:10.1287/opre.40.5.885
[13] R.E. Bixby and M.J. Saltzman, Recovering an optimal LP basis from an interior point solution, Technical Report 607, Department of Mathematical Sciences, Clemson University, Clemson, SC (1992). · Zbl 0814.90073
[14] V. Chandru and B. Kochar, A class of algorithms for linear programming, Research Memorandum 85-14, Department of Industrial Engineering, Purdue University, West Lafayette, IN (1985).
[15] A. Charnes and K.O. Kortanek, An opposite sign algorithm for purification to an extreme point solution, Memorandum No. 129, Office of Naval Research, Northwestern University, Evanston, IL (1963).
[16] G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).
[17] I.I. Dikin, Iterative solution of problems of linear and quadratic programming, Sov. Math. Doklady 8 (1967) 674–675. · Zbl 0189.19504
[18] I.I. Dikin, On the speed of an iterative process, Upravlyaemye Sistemi 12 (1974) 54–60. · Zbl 0402.90059
[19] I.I. Dikin, Determination of the interior point of a system of linear inequalities, Cybern. Syst. Anal. 1 (1992).
[20] I.I. Dikin, On the convergence of dual variables, Technical Report, Siberian Energy Institute, Irkutsk, USSR (1991).
[21] A.S. El-Bakry, R.A. Tapia and Y. Zhang, A study of indicators for identifying zero variables in interior point methods, Technical Report 91-15, Department of Mathematical Sciences, Rice University, Houston, TX (1991). · Zbl 0801.65056
[22] T. Gal,Postoptimal Analysis, Parametric Programming and Related Topics (McGraw-Hill, 1979).
[23] T. Gal, Shadow prices and sensitivity analysis in linear programming under degeneracy, state-of-the-art-survey, OR Spektrum 8 (1986) 59–71. · Zbl 0591.90056 · doi:10.1007/BF01719736
[24] D.M. Gay, Stopping tests that compute optimal solutions for interior-point linear programming algorithms, in:Advances in Numberical Partial Differential Equations and Optimization, Proc. 5th Mexico-United States Workshop, eds. S. Gomez, J.P. Hennart and R.A. Tapia, Proc. in Applied Mathematics, Vol. 47 (1991) pp. 17–42. · Zbl 0813.90082
[25] D.M. Gay, A variant of Karmarkar’s linear programming problems in standard form, Math. Progr. 37 (1987) 81–90. Errata in: Math. Progr. 40 (1988) 111. · Zbl 0629.90056 · doi:10.1007/BF02591685
[26] P.E. Gill, W. Murray, M.A. Saunders, J.A. Tomlin and M.H. Wright, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method, Math. Progr. 36 (1986) 183–209. · Zbl 0624.90062 · doi:10.1007/BF02592025
[27] D. Goldfarb and M.J. Todd, Linear programming, in:Optimization, Handbooks in Operations Research and Management Science, Vol. 1, eds. G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd (North-Holland, Amsterdam, The Netherlands, 1989) pp. 141–170.
[28] A.J. Goldman and A.W. Tucker, Theory of linear programming, in:Linear Inequalities and Related Systems, eds. H.W. Kuhn and A.W. Tucker, Annals of Mathematical Studies 38 (Princeton University Press, Princeton, NJ, 1956). · Zbl 0072.37601
[29] C.C. Gonzaga, An algorithm for solving linear programming problems inO(n 3 L) operations, in:Progress in Mathematical Programming: Interior Point and Related Methods, ed. N. Megiddo (Springer, New York, 1989) pp. 1–28.
[30] C.C. Gonzaga, Polynomial affine algorithms for linear programming, Math. Progr. 49 (1990) 7–21. · Zbl 0777.90027 · doi:10.1007/BF01588776
[31] C.C. Gonzaga, Large step path-following methods for linear programming, part I: Barrier function method, SIAM J. Optim. 1 (1991) 268–279. · Zbl 0754.90035 · doi:10.1137/0801018
[32] C.C. Gonzaga, Large step path-following methods for linear programming, part II: Potential reduction method, SIAM J. Optim. 1 (1991) 280–292. · Zbl 0754.90036 · doi:10.1137/0801019
[33] C.C. Gonzaga, Convergence of the large step primal affine scaling algorithm for primal nondegenerate linear programs, Technical Report ES-230/90, Department of Systems Engineering and Computer Sciences, COPPE Federal University of Rio de Janeiro, Rio de Janeiro, Brazil (1990).
[34] C.C. Gonzaga, Search directions for interior linear programming methods, Algorithmica 6 (1991) 153–181. · Zbl 0718.90064 · doi:10.1007/BF01759039
[35] C.C. Gonzaga, A simple presentation of Karmarkar’s algorithm, Technical Report, Department of Systems Engineering and Computer Sciences, COPPE Federal University of Rio de Janeiro, Rio de Janeiro, Brazil (1988).
[36] C.C. Gonzaga, Path following methods for linear programminig, SIAM Rev. 34 (1992) 167–227. · Zbl 0763.90063 · doi:10.1137/1034048
[37] O. Güler, Existence of interior points and interior paths in nonlinear monotone complementarity problems, Working Paper, The College of Business Administration, The University of Iowa, Iowa City, Iowa (1990), to appear in: Math. Oper. Res.
[38] O. Güler and Y. Ye, Convergence behavior of some interior-point algorithms, Working Paper 91-04, The College of Business Administration, The University of Iowa, Iowa City, Iowa (1991), to appear in: Math. Progr.
[39] O. Güler, C. Roos, T. Terlaky and J.-Ph. Vial, Interior point approach to the theory of linear programming, Technical Report No. 1992.3, Département d’Economie Commerciale et Industrielle, Université de Genève, Switzerland (1992).
[40] Hall and R.J. Vanderbei, private communication (1992).
[41] D. den Hertog, Interior point approach to linear, quadratic and convex programming – Algorithms and complexity, Ph.D. Thesis, Faculty of Mathematics and Informatics, TU Delft, Delft, The Netherlands (1992) (Kluwer, Dordrecht, The Netherlands), to be published.
[42] D. den Hertog and C. Roos, Survey of search directions of interior point methods, Math. Progr. 52 (1991) 481–509. · Zbl 0739.90041 · doi:10.1007/BF01582902
[43] D. den Hertog, C. Roos and T. Terlaky, A potential-reduction variant of Renegar’s short-step path-following method for linear programming, Lin. Alg. Appl. 152 (1991) 43–68. · Zbl 0734.65050 · doi:10.1016/0024-3795(91)90266-Y
[44] D. den Hertog, C. Roos and J.-Ph. Vial, A complexity reduction for the long-step path-following algorithm for linear programming, SIAM J. Optim. 2 (1992) 71–87. · Zbl 0763.90064 · doi:10.1137/0802006
[45] H. Imai, On the convexity of the multiplicative version of Karmarkar’s potential function, Math. Progr. 40 (1988) 29–32. · Zbl 0657.90060 · doi:10.1007/BF01580721
[46] M. Iri, A proof of the polynomiality of the Iri-Imai method for linear programming, Technical Report, Department of Mathematical Engineering and Information Physics, The University of Tokyo, Tokyo, Japan (1991). · Zbl 0811.90066
[47] M. Iri and H. Imai, A multiplicative barrier function method for linear programming, Algorithmica 1 (1986) 455–482. · Zbl 0641.90048 · doi:10.1007/BF01840457
[48] B. Jansen, C. Roos and T. Terlaky, An interior point approach to postoptimal and parametric analysis in linear programming, Technical Report No. 92-21, Faculty of Mathematics and Informatics, TU Delft, Delft, The Netherlands (1992), to appear in Math. Progr.
[49] J.A. Kaliski, A decomposition variant for large scale linear programming, Ph.D. Thesis, Department of Management Sciences, The University of Iowa, Iowa City, Iowa (1992).
[50] N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984) 373–395. · Zbl 0557.90065 · doi:10.1007/BF02579150
[51] M. Kojima, Determining basic variables of optimal solutions in Karmarkar’s new LP algorithm, Algorithmica 1 (1986) 499–515. · Zbl 0661.90057 · doi:10.1007/BF01840459
[52] M. Kojima, N. Megiddo and S. Mizuno, Theoretical convergence of large-step primal-dual interior point algorithms for linear programs, Math. Progr. 59 (1993) 1–22. · Zbl 0780.90063 · doi:10.1007/BF01581234
[53] M. Kojima, S. Mizuno and T. Noma, Limiting behavior of trajectories generated by a continuation method for monotone complementarity problems, Math. Oper. Res. 15 (1990) 662–675. · Zbl 0719.90085 · doi:10.1287/moor.15.4.662
[54] M. Kojima, S. Mizuno and A. Yoshise, A polynomial-time algorithm for a class of linear complementarity problems, Math. Progr. 4 (1989) 41–26. · Zbl 0676.90087
[55] M. Kojima, N. Megiddo, T. Noma and A. Yoshise,A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Science 538 (Springer, New York, 1991). · Zbl 0745.90069
[56] M. Kojima, S. Mizuno and A. Yoshise, AnO(L) iteration potential-reduction algorithm for linear complementarity problems, Math. Progr. 50 (1991) 331–342. · Zbl 0738.90077 · doi:10.1007/BF01594942
[57] M. Kojima and K. Tone, An efficient implementation of Karmarkar’s new LP algorithm, Research Report on Information Sciences B-180, Department of Information Sciences, Tokyo Institute of Technology, Tokyo 152, Japan (1986).
[58] K.O. Kortanek and J. Zhu, New purification algorithms for linear programming, Naval Res. Log. Quarterly 35 (1988) 571–583. · Zbl 0685.90070 · doi:10.1002/1520-6750(198808)35:4<571::AID-NAV3220350410>3.0.CO;2-L
[59] E. Kranich, Interior point methods for mathematical programming: A bibliography, Diskussionsbeitrag Nr. 171, Gesamthochschule FernUniversität Hagen, Germany (1991). Can be obtained by e-mail: netlib@research.att.com.
[60] I.J. Lustig, An implementation of a strongly polynomial time algorithm for basis recovery (using an interior point method), Technical Report (in preparation), School of Engineering and Applied Science, Department of Civil Engineering and Operations Research, Princeton University, Princeton, NJ (1992).
[61] I.J. Lustig, R.E. Marsten and D.F. Shanno, On implementing Mehrotra’s predictor corrector interior point method for linear programming, SIAM J. Optim. 2 (1990) 435–449. · Zbl 0771.90066 · doi:10.1137/0802022
[62] I.J. Lustig, R.E. Marsten and D.F. Shanno, Interior method vs. simplex method: Beyond netlib, COAL Newsletter 19 (1991) 41–44.
[63] R.E. Marsten, M.J. Saltzman, D.F. Shanno, J.F. Ballintijn and G.S. Pierce, Implementation of a dual affine interior point algorithm for linear programming, ORSA J. Comput. 1 (1991) 287–297. · Zbl 0752.90046
[64] L. McLinden, An analogue of Moreau’s proximation theorem, with application to the nonlinear complementarity problem, Pacific J. Math. 88 (1980) 101–161. · Zbl 0403.90081
[65] L. McLinden, The complementarity problem for maximal monotone multifunctions, in:Variational Inequalities and Complementarity Problems, eds. R.W. Cottle, F. Giannessi and J.L. Lions (Wiley, New York, 1980) pp. 251–270. · Zbl 0499.90073
[66] N. Megiddo, Pathways to the optimal set in linear programming, in:Progress in Mathematical Programming: Interior and Related Methods, ed. N. Megiddo (Springer, New York, 1989) pp. 131–158.
[67] N. Megiddo, On finding primal- and dual-optimal bases, ORSA J. Comput. 3 (1991) 63–65. · Zbl 0755.90056
[68] N. Megiddo, Switching from a primal-dual Newton algorithm to a primal-dual (interior) simplex-algorithm, Technical Report RJ 6327, IBM Almaden Research Center, San Jose, CA (1988).
[69] N. Megiddo and M. Shub, Boundary behavior of interior point algorithms in linear programming, Math. Oper. Res. 14 (1987) 97–114. · Zbl 0675.90050 · doi:10.1287/moor.14.1.97
[70] S. Mehrotra, On finding a vertex solution using interior point methods, Lin. Alg. Appl. 152 (1991) 233–253. · Zbl 0737.65050 · doi:10.1016/0024-3795(91)90277-4
[71] S. Mehrotra, Finite termination and superlinear convergence in primal-dual methods, Technical Report 91-13, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL (1991).
[72] S. Mehrotra, Quadratic convergence in a primal-dual method, Technical Report 91-15, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL (1991). · Zbl 0794.90034
[73] S. Mehrotra and Y. Ye, On finding the optimal face of linear programs, Technical Report 91-10, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL (1991). · Zbl 0803.90089
[74] S. Mizuno, M.J. Todd and Y. Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Technical Report No. 944, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY (1991), to appear in: Math. Oper. Res. · Zbl 0810.90091
[75] D.D.C. Monteiro, On the continuous trajectories for a potential reduction algorithm for linear programming, Math. Oper. Res. 17 (1992) 225–253. · Zbl 0793.90032 · doi:10.1287/moor.17.1.225
[76] D.D.C. Monteiro, Convergence and boundary behavior of the projective scaling trajectories for linear programming, Contemp. Math. 114 (1991) 213–232. · Zbl 0748.90041
[77] D.D.C. Monteiro and I. Adler, Interior path-following primal-dual algorithms, Part I: Linear programming, Math. Progr. 44 (1989) 27–41. · Zbl 0676.90038 · doi:10.1007/BF01587075
[78] D.D.C. Monteiro, I. Adler and M.G.C. Resende, A polynomial-time primal-dual affine scaling algorithms for linear and convex quadratic programming and its power series extension, Math. Oper. Res. 15 (1990) 191–214. · Zbl 0714.90060 · doi:10.1287/moor.15.2.191
[79] J. Renegar, A polynomial-time algorithm, based on Newton’s method, for linear programming, Math. Progr. 40 (1988) 59–93. · Zbl 0654.90050 · doi:10.1007/BF01580724
[80] C. Roos and J.-Ph. Vial, A polynomial method of approximate centers for linear programming, Math. Progr. 54 (1992) 295–305. · Zbl 0771.90067 · doi:10.1007/BF01586056
[81] A. Schrijver,Theory of Linear and Integer Programming (Wiley, New York, 1986). · Zbl 0665.90063
[82] D.F. Shanno, private communication (1991).
[83] H.D. Sherali, B.O. Skarpness and B. Kim, An assumption-free analysis of the scaling algorithm for linear programs, with application to theL 1 estimation problem, Naval Res. Log. Quarterly 35 (1988) 473–492. · Zbl 0652.90071 · doi:10.1002/1520-6750(198808)35:4<473::AID-NAV3220350403>3.0.CO;2-C
[84] Gy. Sonnevend, An ”analytic center” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, in:Lecture Notes in Control and Information Sciences, vol. 84, eds. A. Prékopa, J. Szelezsán and B. Straziczki (Springer, New York, 1985) pp. 866–876.
[85] K. Tanabe, Centered Newton method for mathematical programming, in:Proc. 13th IFIP Conf., eds. M. Iri and K. Yajima (Springer, Berlin, 1988) pp. 197–206. · Zbl 0656.90085
[86] K. Tanabe, Centered Newton method for nonlinear programming (in Japanese), in: Proc. Inst. Statist. Math. 38 (Tokyo, 1990) 119–120.
[87] K. Tanabe and T. Tsuchiya, Global analysis of dynamical systems associated with Karmarkar’s method for linear programming, in:Proc. Annual Meeting of the Operations Research Society of Japan, Chigasaki, Japan (1987) pp. 132–133.
[88] R. A. Tapia and Y. Zhang, A fast optimal basis identification technique for interior point linear programming methods, Technical Report 89-1, Department of Mathematical Sciences, Rice University, Houston, TX (1989).
[89] R.A. Tapia and Y. Zhang, An optimal basis identification technique for interior point linear programming algorithms, Lin. Alg. Appl. 152 (1991) 343–363. · Zbl 0737.65052 · doi:10.1016/0024-3795(91)90281-Z
[90] T. Terlaky and S. Zhang, A survey of pivot rules for linear programming, Ann. Oper. Res. 46 (1993), this volume. · Zbl 0793.90034
[91] M.J. Todd, Improved bounds and containing ellipsoids in Karmarkar’s linear programming algorithm, Math. Oper. Res. 13 (1988) 650–659. · Zbl 0665.90059 · doi:10.1287/moor.13.4.650
[92] M.J. Todd and B. Burrell, An extension of Karmarkar’s algorithm for linear programming using dual variables, Algorithmica 1 (1986) 409–424. · Zbl 0621.90048 · doi:10.1007/BF01840455
[93] M.J. Todd and Y. Ye, A centered projective algorithm for linear programming, Math. Oper. Res. 15 (1990) 508–529. · Zbl 0722.90044 · doi:10.1287/moor.15.3.508
[94] P. Tseng and Z.Q. Luo, On the convergence of the affine-scaling algorithm, Math. Progr. 52 (1992) 301–319. · Zbl 0762.90052 · doi:10.1007/BF01580904
[95] T. Tsuchiya, Global convergence property of the affine scaling methods for primal degenerate linear programming problems, Math. Oper. Res. 17 (1992) 527–557. · Zbl 0762.90053 · doi:10.1287/moor.17.3.527
[96] T. Tsuchiya, Global convergence of the affine scaling methods for degenerate linear programming problems, Math. Progr. 52 (1991) 377–404. · Zbl 0749.90051 · doi:10.1007/BF01582896
[97] T. Tsuchiya, Quadratic convergence of Iri and Imai’s algorithm for degenerate linear programming problems, Research Memorandum No. 412, The Institute of Statistical Mathematics, Tokyo, Japan (1991), to appear in: J. Optim. Theory Appl.
[98] T. Tsuchiya, A study on global and local convergence of interior point algorithms for linear programming (in Japanese), Ph.D. Thesis, Faculty of Engineering, The University of Tokyo, Tokyo, Japan (1991).
[99] T. Tsuchiya and M. Muramatsu, Global convergence of a long-step affine scaling algorithm for degenerate linear programming problems, Research Memorandum 423, The Institute of Statistical Mathematics, Tokyo, Japan (1992). · Zbl 0838.90081
[100] T. Tsuchiya and K. Tanabe, Local convergence properties of new methods in linear programming, J. Oper. Res. Soc. Japan 33 (1990) 22–45. · Zbl 0714.90059
[101] R.J. Vanderbei and J.C. Lagarias, Dikin’s convergence result for the affine-scaling algorithm, Contemp. Math. 114 (1990) 109–119. · Zbl 0727.90050
[102] R.J. Vanderbei, M.S. Meketon and B.A. Freedman, A modification of Karmarkar’s linear programming algorithm, Algorithmica 1 (1986) 395–407. · Zbl 0626.90056 · doi:10.1007/BF01840454
[103] J.E. Ward and R.E. Wendell, Approaches to sensitivity analysis in linear programming, Ann. Oper. Res. 27 (1990) 3–38. · Zbl 0722.90075 · doi:10.1007/BF02055188
[104] C. Witzgall, P.T. Boggs and P.D. Domich, On the convergence behavior of trajectories for linear programming, Contemp. Math. 114 (1990) 161–187. · Zbl 0725.90060
[105] M.H. Wright, Interior point methods for constrained optimization, in:Acta Numerica, ed. A. Iserles (Cambridge University Press, New York, 1992) pp. 341–407. · Zbl 0766.65053
[106] H. Yamashita, A polynomially and quadratically convergent method for linear programming, Technical Report, Mathematical Systems Inc., Shinjuku, Tokyo, Japan (1986).
[107] Y. Ye, Karmarkar’s algorithm and the ellipsoid method, Oper. Res. Lett. 6 (1987) 177–182. · Zbl 0631.90035 · doi:10.1016/0167-6377(87)90016-2
[108] Y. Ye, Recovering optimal basis in Karmarkar’s polynomial algorithm for linear programming, Math. Oper. Res. 15 (1990) 564–572. · Zbl 0708.90048 · doi:10.1287/moor.15.3.564
[109] Y. Ye, AnO(n 3 L) potential reduction algorithm for linear programming, Math. Progr. 50 (1991) 239–258. · Zbl 0734.90057 · doi:10.1007/BF01594937
[110] Y. Ye, On the finite convergence of interior-point algorithms for linear programming, Math. Progr. Ser. B 57 (1992) 325–335. · Zbl 0794.90036 · doi:10.1007/BF01581087
[111] Y. Ye, O. Güler, R.A. Tapia and Y. Zhang, A quadratically convergentO(L)-iteration algorithm for linear programming, Technical Report 91-26, Department of Mathematical Sciences, Rice University, Houston, TX (1991), to appear in: Math. Progr.
[112] Y. Ye and J. Kaliski, private communication (1991).
[113] Y. Ye and M. Kojima, Recovering optimal dual solutions in Karmarkar’s polynomial algorithm for linear programming, Math. Progr. 39 (1987) 305–317. · Zbl 0639.90062 · doi:10.1007/BF02592079
[114] Y. Ye, R.A. Tapia and Y. Zhang, A superlinearly convergentO(L)-iteration algorithm for linear programming, Technical Report 91-22, Department of Mathematical Sciences, Rice University, Houston, TX (1991).
[115] Y. Ye and M.J. Todd, Containing and shrinking ellipsoids in the path-following algorithm, Math. Progr. 47 (1990) 1–10. · Zbl 0746.90049 · doi:10.1007/BF01580848
[116] Y. Zhang, R. Tapia and J.E. Dennis, On the superlinear and quadratic convergence of primal-dual interior-point linear programming algorithms, SIAM J. Optim. 2 (1990) 304–324. · Zbl 0763.90066 · doi:10.1137/0802015
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.