Vanderbei, Robert J.; Meketon, Marc S.; Freedman, Barry A. A modification of Karmarkar’s linear programming algorithm. (English) Zbl 0626.90056 Algorithmica 1, 395-407 (1986). The authors present a modification of Karmarkar’s algorithm, which uses a recentered projected gradient approach thereby obviating a priori knowledge of the optimal value of the objective function. The proof of the convergence is given assuming primal and dual nondegeneracy. Computational comparisons between this algorithm and the revised simplex method are reported. The authors undertook a regression on the algorithm of the time (number of iterations) as a linear function of the logarithms of m and n. Reviewer: V.Mazurow Cited in 4 ReviewsCited in 126 Documents MSC: 90C05 Linear programming 65K05 Numerical mathematical programming methods Keywords:least squares; modification; Karmarkar’s algorithm; projected gradient; Computational comparisons; revised simplex method PDF BibTeX XML Cite \textit{R. J. Vanderbei} et al., Algorithmica 1, 395--407 (1986; Zbl 0626.90056) Full Text: DOI References: [1] L. V. Atkinson and P. J. Harley,An Introduction to Numerical Methods with Pascal, Addison-Wesley, Reading, MA, 1983. · Zbl 0512.65001 [2] E. R. Barnes, A variation on Karmarkar’s algorithm for solving linear programming problems, Manuscript, IBM T. J. Watson Research Center, Yorktown Heights, NY, 1985. [3] T. M. Cavalier and A. L. Soyster, Some computational experience and a modification of the Karmarkar algorithm, ISME Working Paper 85–105, The Pennsylvania State University, 1985. [4] V. Chvátal,Linear Programming, Freeman, New York and San Francisco, 1983. [5] S. C. Eisenstat, Efficient implementation of a class of preconditioned conjugate gradient methods,SIAM J. Sci. Statist. Comput.,2 (1985), 4–7. · Zbl 0474.65020 [6] N. Karmarkar, A new polynomial-time algorithm for linear programming,Combinatorica,4 (1984), 373–395. · Zbl 0557.90065 · doi:10.1007/BF02579150 [7] L. S. Lasdon,Optimization Theory for Large Systems, Macmillan, New York, 1970. · Zbl 0224.90038 [8] N. Megiddo, A variation on Karmarkar’s algorithm, Manuscript, IBM Research Laboratory, San Jose, CA, 1985. · Zbl 0561.90063 [9] M. J. Todd and B. P. Burrell, An extension of Karmarkar’s algorithm for linear programming using dual variables, Technical Report No. 648, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1985. · Zbl 0621.90048 [10] J. A. Tomlin, An experimental approach to Karmarkar’s projective method for linear programming, Manuscript, Ketron Inc., Mountain View, CA, 1985. · Zbl 0634.90044 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.