×
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 Reviews
Cited in 127 Documents

MSC:

90C05 Linear programming
65K05 Numerical mathematical programming methods

Keywords:

least squares; modification; Karmarkar’s algorithm; projected gradient; Computational comparisons; revised simplex method
PDFBibTeX XMLCite
\textit{R. J. Vanderbei} et al., Algorithmica 1, 395--407 (1986; Zbl 0626.90056)
Full Text: DOI

References:

[1] Atkinson, L. V.; Harley, P. J., An Introduction to Numerical Methods with Pascal (1983), Reading, MA: Addison-Wesley, Reading, MA · Zbl 0512.65001
[2] Barnes, E. R., A variation on Karmarkar’s algorithm for solving linear programming problems (1985), Yorktown Heights, NY: IBM T. J. Watson Research Center, Yorktown Heights, NY
[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] Chvátal, V., Linear Programming (1983), New York and San Francisco: Freeman, New York and San Francisco · Zbl 0537.90067
[5] Eisenstat, S. C., Efficient implementation of a class of preconditioned conjugate gradient methods, SIAM J. Sci. Statist. Comput., 2, 4-7 (1985) · Zbl 0474.65020
[6] Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373-395 (1984) · Zbl 0557.90065 · doi:10.1007/BF02579150
[7] Lasdon, L. S., Optimization Theory for Large Systems (1970), New York: Macmillan, New York · Zbl 0224.90038
[8] Megiddo, N., A variation on Karmarkar’s algorithm (1985), San Jose, CA: IBM Research Laboratory, San Jose, CA
[9] Todd, M. J.; Burrell, B. P., An extension of Karmarkar’s algorithm for linear programming using dual variables (1985), Ithaca, NY: School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY
[10] Tomlin, J. A., An experimental approach to Karmarkar’s projective method for linear programming, Manuscript (1985), Mountain View, CA: Ketron Inc., Mountain View, CA
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.