zbMATH — the first resource for mathematics

Limiting behavior of the affine scaling continuous trajectories for linear programming problems. (English) Zbl 0719.90044
The authors discuss the limiting behaviour of the continuous trajectories of the primal affine scaling (PAS) algorithm given by E. R. Barnes [Math. Program. 36, 174-182 (1986; Zbl 0626.90052)] and others, the dual affine scaling (DAS) algorithm given by the first author, M. Resende, G. Veiga and N. Karmarkar [ibid., Ser. A 44, No.3, 297- 335 (1989; Zbl 0682.90061)] and the primal-dual affine scaling (PDAS) algorithm introduced by the authors and M. Resende [Math. Oper. Res. 15, No.2, 191-214 (1990; Zbl 0714.90060)].
In this paper they present a weighted PAS algorithm and characterize its trajectories as solutions to a logarithmic barrier family of problems. The authors present several results on PAS, DAS and PDAS trajectories and claim to extend the results already obtained by N. Megiddo and M. Shub [ibid. 14, No.1, 97-146 (1989; Zbl 0675.90061)] and others about the limiting behaviour of PAS and PDAS trajectories. It is mentioned that their approach does not require the non-degeneracy assumption.
Reviewer: R.N.Kaul (Delhi)

90C05 Linear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI
[1] I. Adler, N. 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 · doi:10.1007/BF01587095
[2] E.R. Barnes, ”A variation on Karmarkar’s algorithm for solving linear programming problems,”Mathematical Programming 36 (1986) 174–182. · Zbl 0626.90052 · doi:10.1007/BF02592024
[3] D.A. Bayer and J.C. Lagarias, ”The nonlinear geometry of linear programming,”Transactions of the American Mathematical Society 314 (1989) 499–581. · Zbl 0671.90046
[4] I.I. Dikin, ”Iterative solution of problems of linear and quadratic programming,”Soviet Mathematics Doklady 8 (1967) 674–675. · Zbl 0189.19504
[5] A. Fiacco and G. McCormick,Nonlinear Programming: Sequential Unconstrained Minimization Techniques (John Wiley and Sons, New York, 1955). · Zbl 0193.18805
[6] N. Karmarkar, ”A new polynomial time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065 · doi:10.1007/BF02579150
[7] N. Karmarkar, Talk at the University of California at Berkeley (Berkeley, CA, 1984).
[8] N. Megiddo, ”Pathways to the optimal set in linear programming,” in: N. Megiddo, ed.,Progress in Mathematical Programming: Interior-Point Algorithms and Related Methods (Springer, Berlin, 1989) pp. 131–158. · Zbl 0687.90056
[9] N. Megiddo and M. Shub, ”Boundary behavior of interior point algorithms for linear programming,”Mathematics of Operations Research 14 (1989) 97–146. · Zbl 0675.90050 · doi:10.1287/moor.14.1.97
[10] 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 · doi:10.1016/0167-6377(87)90040-X
[11] R.D.C. Monteiro, I. Adler and M.G.C. Resende, ”A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension,”Mathematics of Operations Research 15 (1990) 191–214. · Zbl 0714.90060 · doi:10.1287/moor.15.2.191
[12] A. Schrijver,Theory of Linear and Integer Programming (John Wiley & Sons, New York 1986). · Zbl 0665.90063
[13] 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
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.