×

zbMATH — the first resource for mathematics

Linear programming and the Newton barrier flow. (English) Zbl 0657.90059
The author investigates the interior algorithms for linear programming. These algorithms are connected with some trajectories of vectors approximating an optimal solution to a linear programming problem. The author shows that given a bounded polyhedral set P with nonempty interior, the logarithmic barrier function (with no objective components) induces a vector field of negative Newton directions which flows from the center of P to the solution of every possible linear program of P.
Reviewer: V.Mazurow

MSC:
90C05 Linear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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
[2] E.R. Barnes, S. Chopra and D. Jensen, manuscript in preparation, IBM Watson Research Center (Yorktown Heights, NY, 1987).
[3] D.A. Bayer and J.C. Lagarias, ”The nonlinear geometry of linear programming I. Affine and projective scaling trajectories,” AT&T Bell Laboratories (Murray Hill, NJ, 1986). · Zbl 0671.90045
[4] D.A. Bayer and J.C. Lagarias, ”The nonlinear geometry of linear programming II. Legendre transform coordinates,” AT&T Bell Laboratories (Murray Hill, NJ, 1986). · Zbl 0671.90046
[5] D.A. Bayer and J.C. Lagarias, ”The nonlinear geometry of linear programming III. Central trajectories,” AT&T Bell Laboratories (Murray Hill, NJ, 1986). · Zbl 0671.90046
[6] 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,”Mathematical Programming 36 (1986) 183–209. · Zbl 0624.90062 · doi:10.1007/BF02592025
[7] C.C. Gonzaga, ”An algorithm for solving linear programming problems in O(n 3 L) operations,” Memorandum UCB/ERL M87/10, University of California (Berkeley, CA, 1987).
[8] N. Karmarkar, ”A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065 · doi:10.1007/BF02579150
[9] J.C. Lagarias, private communication (1986).
[10] N. Megiddo, ”Pathways to the optimal set in linear programming,” Research Report RJ 5295, IBM Almaden Research Center (San Jose, CA, 1986). · Zbl 0612.90082
[11] N. Megiddo and M. Shub, ”Boundary behavior of interior point algorithms in linear programming,” Research report RJ 5319, IBM Watson Research Center (Yorktown Heights, NY, 1986). · Zbl 0675.90050
[12] J. Renegar, ”A polynomial-time algorithm, based on Newton’s method, for linear programming,”Mathematical Programming 40 (1988) 59–93. · Zbl 0654.90050 · doi:10.1007/BF01580724
[13] G. Sonnevend, ”An analytical centre for a polyhedron and new classes of global algorithms for linear (smooth, convex) programming,” in:Proceedings of the 12th IFIP Conference on System Modeling (Budapest, 1985).
[14] P.M. Vaidya, ”An algorithm for linear programming which requires O(((m+n)n 2+(m+n)1.5 n)L) arithmetic operations,” AT&T Bell Laboratories (Murray Hill, NJ, 1987). · Zbl 0708.90047
[15] R.J. Vanderbei, M.J. 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.