Abstract
An algorithm for solving large-scale nonlinear programs with linear constraints is presented. The method combines efficient sparse-matrix techniques as in the revised simplex method with stable quasi-Newton methods for handling the nonlinearities. A general-purpose production code (MINOS) is described, along with computational experience on a wide variety of problems.
Similar content being viewed by others
References
J. Abadie, “Application of the GRG algorithm to optimal control problems”, in: J. Abadie, ed.,Integer and nonlinear programming (North-Holland, Amsterdam, 1970) pp. 191–211.
R.H. Bartels, “A stabilization of the simplex method”,Numerische Mathematik 16 (1971) 414–434.
R.H. Bartels and G.H. Golub, “The simplex method of linear programming using LU decomposition”,Communications of ACM 12 (1969) 266–268.
E.M.L. Beale, “Numerical methods”, in: J. Abadie, ed.,Nonlinear programming (North-Holland, Amsterdam, 1967) pp. 132–205.
J. Bracken and G.P. McCormick,Selected applications of nonlinear programming (Wiley, New York, 1968).
R.P. Brent, “Reducing the retrieval time of scatter storage techniques”,Communications of ACM 16 (1973) 105–109.
C.G. Broyden, “Quasi-Newton methods”, in: W. Murray, ed.,Numerical methods for unconstrained optimization (Academic Press, New York, 1972) pp. 87–106.
A. Buckley, “An alternate implementation of Goldfarb's minimization algorithm”,Mathematical Programming 8 (1975) 207–231.
A.R. Colville, “A comparative study on nonlinear programming codes”, IBM New York Scientific Center Report 320-2949 (1968).
A.R. Conn, “Linear programming via a non-differentiable penalty function”,SIAM Journal of Numerical Analysis 13 (1) (1976) 145–154.
R.W. Cottle, “The principal pivoting method of quadratic programming”, in: G.B. Dantzig and A.F. Veinott, Jr., eds.,Mathematics of the decision sciences, Part 1 (American Mathematical Society, 1968) pp. 144–162.
G.B. Dantzig,Linear programming and extensions (Princeton University Press, NJ, 1963).
W.C. Davidon, “Variable metric method for minimization”, AEC Research and Development Report ANL-5990 (1959).
I.S. Duff, “On algorithms for obtaining a maximum transversal”, to appear.
I.S. Duff and J.K. Reid, “An implementation of Tarjan's algorithm for the block triangularization of a matrix”, AERE Report C.S.S. 29 (1976), Harwell, England.
P. Faure and P. Huard, “Resolution de programmes mathematiques a fonction nonlineaire par la methode du gradient reduit”,Revue Francaise de Recherche Operationelle 36 (1965) 167–206.
R. Fletcher, “Minimizing general functions subject to linear constraints”, in: F.A. Lootsma, ed.,Numerical methods for nonlinear optimization (Academic Press, London and New York, 1972) pp. 279–296.
R. Fletcher and M.J.D. Powell, “A rapidly convergent descent method for minimization”,Computer Journal 6 (1963) 163–168.
R. Fletcher and C.M. Reeves, “Function minimization by conjugate gradients”,Computer Journal 7 (1964) 149–154.
P.E. Gill, G.H. Golub, W. Murray and M.A. Saunders, “Methods for modifying matrix factorizations”,Mathematics of Computation 28 (1974) 505–535.
P.E. Gill and W. Murray, “Quasi-Newton methods for unconstrained optimization”,Journal of Institute of Mathematics and its Applications 9 (1972) 91–108.
P.E. Gill and W. Murray, “Quasi-Newton methods for linearly constrained optimization”, Report NAC 32 (1973), National Physical Laboratory, Teddington.
P.E. Gill and W. Murray, “Newton-type methods for unconstrained and linearly constrained optimization”,Mathematical Programming 7 (1974) 311–350.
P.E. Gill and W. Murray, “Safeguarded steplength algorithms for optimization using descent methods”, Report NAC 37 (1974), National Physical Laboratory, Teddington.
P.E. Gill and W. Murray, eds.,Numerical methods for constrained optimization (Academic Press, London, 1974).
P.E. Gill and W. Murray, “Linearly constrained optimization including quadratic and linear programming”, in: Jacobs and Scriven, eds.,Modern numerical analysis (Academic Press, London, 1977), Proceedings of conference on “State of the art of numerical analysis”, University of York (April 1976).
P.E. Gill, W. Murray and S.M. Picken, “The implementation of two modified Newton algorithms for linearly constrained optimization” (to appear).
P.E. Gill, W. Murray and R.A. Pitfield, “The implementation of two revised quasi-Newton algorithms for unconstrained optimization”, Report NAC 11 (1972), National Physical Laboratory, Teddington.
P.E. Gill, W. Murray and M.A. Saunders, “Methods for computing and modifying the LDV factors of a matrix”,Mathematics of Computation 29 (1975) 1051–1077.
D. Goldfarb, “Extension of Davidon's variable metric method to maximization under linear inequality and equality constraints”,SIAM Journal of Applied Mathematics 17 (1969) 739–764.
D. Goldfarb, “On the Bartels—Golub decomposition for linear programming bases”, AERE Report C.S.S. 18 (1975), Harwell, England.
E. Hellerman and D.C. Rarick, “Reinversion with the preassigned pivot procedure”,Mathematical Programming 1 (1971) 195–216.
E. Hellerman and D.C. Rarick, “The partitioned preassigned pivot procedure”, in: D.J. Rose and R.A. Willoughby, eds.,Sparse matrices and their applications (Plenum Press, New York, 1972) pp. 67–76.
D.M. Himmelblau,Applied nonlinear programming (McGraw-Hill, New York, 1972).
A. Jain, L.S. Lasdon and M.A. Saunders, “An in-core nonlinear mathematical programming system for large sparse nonlinear programs”, presented at ORSA/TIMS joint national meeting, Miami, Florida (November, 1976).
J.E. Kalan, “Aspects of large-scale in-core linear programming”, Proceedings of ACM conference, Chicago (1971) 304–313.
C.E. Lemke, “Bimatrix equilibrium points and mathematical programming”,Management Science 11 (1965) 681–689.
A.S. Manne, “Waiting for the breeder”, The review of economic studies symposium (1974) 47–65.
A.S. Manne, “U.S. options for a transition from oil and gas to synthetic fuels”, presented at the World Congress of the Econometric Society, Toronto (August 1975).
A.S. Manne, “ETA: a model for Energy Technology Assessment”,Bell Journal of Economics (Autumn 1976) 381–406.
G.P. McCormick, “The variable-reduction method for nonlinear programming”,Management Science 17 (3) (1970) 146–160.
G.P. McCormick, “A second order method for the linearly constrained nonlinear programming problem”, in: J.B. Rosen, O.L. Mangasarian and K. Ritter, eds.,Nonlinear programming (Academic Press, New York, 1970) pp. 207–243.
B.A. Murtagh and P.D. Lucas, “The modelling of energy production and consumption in New Zealand”, IBM (N.Z.) 5 (1975) 3–6.
B.A. Murtagh and R.W.H. Sargent, “A constrained minimization method with quadratic convergence”, in: R. Fletcher, ed.,Optimization (Academic Press, New York, 1969) pp. 215–246.
A. Perry, “An improved conjugate gradient algorithm”, Technical note (March 1976), Dept. of Decision Sciences, Graduate School of Management, Northwestern University, Evanston, Illinois.
E. Polak,Computational methods in optimization: a unified approach (Academic Press, New York, 1971).
M.J. D. Powell, “Restart procedures for the conjugate gradient method”, AERE Report C.S.S. 24 (1975), Harwell, England.
D.C. Rarick, An improved pivot row selection procedure, implemented in the mathematical programming system MPS III, Management Science Systems, Rockville, MA, U.S.A.
R.W.H. Sargent, “Reduced-gradient and projection methods for nonlinear programming”, in: P.E. Gill and W. Murray, eds.,Numerical methods for constrained optimization (Academic Press, London, 1974) pp. 149–174.
R.W. Sargent and B.A. Murtagh, “Projection methods for nonlinear programming”,Mathematical Programming 4 (1973) 245–268.
M.A. Saunders, “Large-scale linear programming using the Cholesky factorization”, Report STAN-CS-72-252 (1972), Computer Science Dept., Stanford University, Stanford, CA, U.S.A.
M.A. Saunders, “A fast, stable implementation of the simplex method using Bartels—Golub updating”, in: J.R. Bunch and D.J. Rose, eds.,Sparse Matrix Computations (Academic Press, New York, 1976) pp. 213–226.
B.R. Smith, P.D. Lucas and B.A. Murtagh, “The development of a New Zealand energy model”,N.Z. Operational Research 4 (2) (1976) 101–117.
J.A. Tomlin, “On pricing and backward transformation in linear programming”,Mathematical Programming 6 (1974) 42–47.
P. Wolfe, “The simplex method for quadratic programming”,Econometrica 27 (1959) 382–398.
P. Wolfe, “The reduced gradient method”, unpublished manuscript, The RAND Corporation (June 1962).
P. Wolfe, “Methods of nonlinear programming”, in: J. Abadie, ed.,Nonlinear programming (North-Holland, Amsterdam, 1967) pp. 97–131.
M.J. Wood, “The February 1975 state of BUILD”, Ministry of Works and Development report (February 1975), Wellington, New Zealand.
P.E. Gill, W. Murray, S.M. Picken, H.M. Barber and M.H. Wright, Subroutine LNSRCH, NPL Algorithms Library, Reference No. E4/16/0/Fortran/02/76 (February 1976).
J.A. Tomlin, “Robust implementation of Lemke's method for the linear complementarity problem”, Technical Report SOL 76-24, Systems Optimization Laboratory, Stanford University (September 1976).
Author information
Authors and Affiliations
Additional information
This research was supported by the U.S. Office of Naval Research (Contract N00014-75-C-0267), the National Science Foundation (Grants MCS71-03341 A04, DCR75-04544), the U.S. Energy Research and Development Administration (Contract E(04-3)-326 PA #18), the Victoria University of Wellington, New Zealand, and the Department of Scientific and Industrial Research Wellington, New Zealand.
Rights and permissions
About this article
Cite this article
Murtagh, B.A., Saunders, M.A. Large-scale linearly constrained optimization. Mathematical Programming 14, 41–72 (1978). https://doi.org/10.1007/BF01588950
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01588950