×

zbMATH — the first resource for mathematics

Global convergence of the affine scaling methods for degenerate linear programming problems. (English) Zbl 0749.90051
Summary: We show the global convergence of the affine scaling methods without assuming any condition on degeneracy. The behavior of the method near degenerate faces is analyzed in detail on the basis of the equivalence between the affine scaling methods for homogeneous LP problems and Karmarkar’s method. It is shown that the step-size \({1\over 8}\), where the displacement vector is normalized with respect to the distance in the scaled space, is sufficient to guarantee the global convergence of the affine scaling methods.

MSC:
90C05 Linear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] I. Adler, N.K. Karmarkar, M.G.C. Resende and G. Veiga, ”An implementation of Karmarkar’s algorithm for linear programming”Mathematical Programming 44 (1989) 297–335. · Zbl 0682.90061
[2] I. Adler, N.K. Karmarkar, M.G.C. Resende and G. Veiga, ”Data structures and programming techniques for the implementation of Karmarkar’s algorithm,”ORSA Journal on Computing 1(2) (1989) 84–106. · Zbl 0752.90043
[3] I. Adler and R.D.C. Monteiro, ”Limiting behavior of the affine scaling continuous trajectories for linear programming problems,”Mathematical Programming 50 (1991) 29–51. · Zbl 0719.90044
[4] E.R. Barnes, ”A variation on Karmarkar’s algorithm for solving linear programming problems,”Mathematical Programming 36 (1986) 174–182. · Zbl 0626.90052
[5] D.A. Bayer and J.C. Lagarias, ”The nonlinear geometry of linear programming: I. Affine and projective trajectories,”Transactions of the American Mathematical Society 314(2) (1989) 499–526. · Zbl 0671.90045
[6] I.I. Dikin, ”Iterative solution of problems of linear and quadratic programming,”Soviet Mathematics Doklady 8 (1967) 674–675. · Zbl 0189.19504
[7] I.I. Dikin, ”About the convergence of an iterative process,”Upravlyaemye Sistemi 12 (1974) 54–60. [In Russian.] · Zbl 0402.90059
[8] C.C. Gonzaga, ”Conial projection algorithms for linear programming,”Mathematical Programming 43 (1989) 151–173. · Zbl 0667.90064
[9] N. Karmarkar, ”A new polynomial-time algorithm for linear programming,”Combinatorica 4(4) (1984) 373–395. · Zbl 0557.90065
[10] K.A. McShane, C.L. Monma and D.F. Shanno, ”An implementation of a primal–dual interior point method for linear programming,”ORSA Journal on Computing 1 (1989) 70–83. · Zbl 0752.90047
[11] N. Megiddo and M. Shub, ”Boundary behavior of interior point algorithms for linear programming,”Mathematics of Operations Research 14(1) (1989) 97–146. · Zbl 0675.90050
[12] C.L. Monma and A.J. Morton, ”Computational experience with a dual affine variant of Karmarkar’s method for linear programming,”Operations Research Letters 6 (1987) 261–267. · Zbl 0627.90065
[13] A. Schrijver,Theory of Linear and Integer Programming (Wiley, Chichester, UK, 1986). · Zbl 0665.90063
[14] K. Tanabe and T. Tsuchiya, ”Global analysis of dynamical systems associated with Karmarkar’s method for linear programming,” Manuscript (1987).
[15] P. Tseng and Z.-Q. Luo, ”On the convergence of the affine-scaling algorithm,” Technical Report, CICS-P-169, Center for Intelligent Control Systems, Massachusetts Institute of Technology (Cambridge, MA, 1989).
[16] T. Tsuchiya, ”On Yamashita’s method and Freund’s method for linear programming,”Cooperative Research Report of the Institute of Statistical Mathematics 10 (1988) 105–115. [In Japanese.]
[17] T. Tsuchiya, ”Dual standard form linear programming problems and Karmarkar’s canonical form,”Lecture Note of the Research Institute of Mathematical Sciences 676 (1988) 330–336. [In Japanese.]
[18] T. Tsuchiya, ”Global convergence property of the affine scaling methods for the primal degenerate linear programming problems,” To appear inMathematics of Operations Research (1992). · Zbl 0762.90053
[19] T. Tsuchiya and K. Tanabe, ”Local convergence properties of new methods in linear programming,”The Journal of the Operations Research Society of Japan 33(1) (1990) 22–45. · Zbl 0714.90059
[20] T. Tsuchiya, ”Quadratic convergence of Iri and Imai’s algorithm for degenerate linear programming problems,” Research Memorandum 412, the Institute of Statistical Mathematics (Tokyo, Japan, 1991).
[21] 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
[22] R.J. Vanderbei and J.C. Lagarias, ”I.I. Dikin’s convergence result for the affine-scaling algorithm,” Technical Report, AT&T Bell Laboratories (Murray Hill, NJ, 1988). · Zbl 0727.90050
[23] H. Yamashita, ”A polynomially and quadratically convergent method for linear programming,” Technical Report, Mathematical System Inc. (Tokyo, 1986).
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.