Limiting behavior of the affine scaling continuous trajectories for linear programming problems. (English) Zbl 0719.90044

Adler, Ilan; Monteiro, Renato D. C.

Math. Program., Ser. A 50, No. 1, 29-51 (1991).

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)

MSC:

90C05	Linear programming
90-08	Computational methods for problems pertaining to operations research and mathematical programming

Keywords:

primal affine scaling; dual affine scaling; primal-dual affine scaling; logarithmic barrier; limiting behaviour

Citations:

Zbl 0626.90052; Zbl 0682.90061; Zbl 0714.90060; Zbl 0675.90061

References:

[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