×

Conical projection algorithms for linear programming. (English) Zbl 0667.90064

An algorithm for linear programming is given as a nonlinear programming procedure which minimizes Karmarkar’s logarithmic potential function over an appropriate constraint set.
Reviewer: M.A.Hanson

MSC:

90C05 Linear programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] I. Adler, M. Resende and G. Veiga, ”An implementation of Karmarkar’s algorithm for linear programming,” Report ORC86-8, Operations Research Center, University of California (Berkeley, CA, 1986). · Zbl 0682.90061
[2] K. Anstreicher, ”A monotonic projective algorithm for fractional linear programming,”Algorithmica 1 (1986) 483–498. · Zbl 0625.90088 · doi:10.1007/BF01840458
[3] T. Cavalier and A. Soyster, ”Some computational experience and a modification of the Karmarkar algorithm,” Working Paper 85-105, Dept. of Industrial and Management System Eng., Pennsylvania State University (University Park, PA, 1985).
[4] D. Gay, ”A variant of Karmarkar’s linear programming algorithm for problems in standard form,”Mathematical Programming 37 (1987) 81–90. · Zbl 0629.90056 · doi:10.1007/BF02591685
[5] P. Gill, W. Murray, M. Saunders, J. Tomlin and M. 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
[6] C. Gonzaga, ”A conical projection algorithm for linear programming,” memorandum No. UCB/ERL M85/61, Electronics Research Laboratory, University of California (Berkeley, CA, 1985).
[7] M. Heath, ”Some extensions of an algorithm for sparse linear least squares problems,”SIAM Journal on Scientific and Statistical Computing 3 (1982) 223–237. · Zbl 0483.65027 · doi:10.1137/0903014
[8] 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
[9] N. Karmarkar, ”A new polynomial time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065 · doi:10.1007/BF02579150
[10] W. Murray and M. Wright, ”Efficient linear search algorithms for the logarithmic barrier function,” Report SOL 76-18, Dept. of Operations Research (Stanford, CA, 1976).
[11] M. Padberg, ”Solution of a nonlinear programming problem arising in the projective method for linear programming,” Manuscript, New York University (New York, NY, 1985).
[12] R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970). · Zbl 0193.18401
[13] M. 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
[14] Y. Ye, ”A large group of projections for linear programming,” Manuscript, Engineering-Economic System Dept., Stanford University (Stanford, CA, 1985).
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.