A variable-metric variant of the Karmarkar algorithm for linear programming. (English) Zbl 0635.90058
The most time-consuming part of the Karmarkar algorithm for linear programming is the projection of a vector onto the nullspace of a matrix that changes at each iteration. We present a variant of the Karamarkar algorithm that uses standard variable-metric techniques in an innovative way to approximate this projection. In limited tests, this modification greatly reduces the number of matrix factorizations needed for the solution of linear programming problems.
References:
| [1] | Kurt M. Anstreicher, ”A monotonic projective algorithm for fractional linear programming,” Yale School of Management (New Haven, CT, 1985, revised 1986). To appear inAlgorithmica. · Zbl 0625.90088 |
| [2] | T.M. Cavalier and A.L. Soyster, ”Some computational experience and a modification of the Karmarkar algorithm,” Department of Industrial and Management Systems Engineering, The Pennsylvania State University (University Park, PA, 1985). |
| [3] | A. Charnes, T. Song, and M. Wolfe, ”An explicit solution sequence and convergence of Karmarkar’s algorithm,” Center for Cybernetic Studies, The University of Texas at Austin, Research CCS 501 (Austin, TX, 1984). |
| [4] | J.E. Dennis, Jr. and Robert B. Schnabel,Numerical methods for unconstrained optimization and nonlinear equations (Prentice-Hall, Englewood Cliffs, NJ, 1983). · Zbl 0579.65058 |
| [5] | David M. Gay, ”A variant of Karmarkar’s linear programming algorithm for problems in standard form,” AT & T Bell Laboratories Numerical Analysis Manuscript 85-10 (Murray Hill, NJ, 1985), to appear inMathematical Programming. |
| [6] | David M. Gay, ”Electronic mail distribution of linear programming test problems,”Committee on Algorithms Newsletter, Mathematical Programming Society 13 (December, 1985). |
| [7] | Philip E. Gill, Walter Murray, Michael A. Saunders, J. A. Tomlin and Margaret H. Wright, ”On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method,” Systems Optimization Laboratory, Stanford University, Technical Report SOL 85-11 (Stanford, CA, 1985), to appear inMathematical Programming. · Zbl 0624.90062 |
| [8] | Philip E. Gill, Walter Murray, Michael A. Saunders and Margaret H. Wright, ”A note on non-linear approaches to linear programming,” Systems Optimization Laboratory, Stanford University, Technical Report SOL 86-7 (Stanford, CA, 1986). · Zbl 0624.90062 |
| [9] | Donald Goldfarb and Sanjay Mehrotra, ”A relaxed version of Karmarkar’s method,” Department of Industrial Engineering and Operations Research, Columbia University in the City of New York (New York, NY, 1985, revised 1986). · Zbl 0654.90049 |
| [10] | N. Karmarkar, ”A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065 · doi:10.1007/BF02579150 |
| [11] | Irvin J. Lustig, ”A practical approach to Karmarkar’s algorithm,” Systems Optimization Laboratory, Stanford University, Technical Report SOL 85-5 (Stanford, CA, 1985). |
| [12] | David F. Shanno, ”A reduced gradient variant of Karmarkar’s algorithm,” Graduate School of Administration, University of California, Davis, Working Paper 85-01 (Davis, CA, 1985). |
| [13] | David F. Shanno, ”Computing Karmarkar projections quickly,” Graduate School of Administration, University of California, Davis, Working Paper 85-10 (Davis, CA, 1985). |
| [14] | David F. Shanno and Roy E. Marsten, ”On implementing Karmarkar’s method,” Graduate School of Administration, University of California, Davis, Working Paper 85-01 (Davis, CA, 1985). |
| [15] | Michael J. Todd and Bruce P. Burrell, ”An extension of Karmarkar’s algorithm for linear programming using dual variables,” School of Operations Research and Industrial Engineering, Cornell University, Technical Report No. 648 (Ithaca, NY, 1985), to appear inAlgorithmica. · Zbl 0621.90048 |
| [16] | Michael J. Todd, Private communication (July, 1986). |
| [17] | J.A. Tomlin, ”An experimental approach to Karmarkar’s projective method for linear programming,” Ketron, Inc. (Mountain View, CA, 1985), to appear in aMathematical Programming Study on Computational Mathematical Programming. · 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. 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.
