Abstract
This paper describes two numerically stable methods for unconstrained optimization and their generalization when linear inequality constraints are added. The difference between the two methods is simply that one requires the Hessian matrix explicitly and the other does not. The methods are intimately based on the recurrence of matrix factorizations and are linked to earlier work on quasi-Newton methods and quadratic programming.
Similar content being viewed by others
References
R.H. Bartels, G.H. Golub and M.A. Saunders, “Numerical techniques in mathematical programming”, in: J.B. Rosen, O.L. Mangasarian and K. Ritter, eds.,Nonlinear programming (Academic Press, New York, 1970) pp. 123–176.
K.M. Brown and J.E. Dennis, Jr., “Derivative-free analogues of the Levenberg—Marquardt and Gauss algorithms for non-linear least squares approximation”,Numerische Mathematik 18 (1972) 289–297.
P. Businger and G.H. Golub, “Linear least squares solutions by Householder transformations”,Numerische Mathematik 7 (1965) 269–276.
A.R. Curtis, M.J.D. Powell and J.K. Reid, “On the estimation of sparse Jacobian matrices”,Journal of the Institute of Mathematics and its Applications 13 (1974) 117–119.
A.V. Fiacco and G.P. McCormick,Nonlinear programming: sequential unconstrained minimization techniques (Wiley, New York, 1968).
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 the Institute of Mathematics and its Applications 9 (1972) 91–108.
P.E. Gill and W. Murray, “A numerically stable form of the simplex algorithm”,Linear Algebra and its Applications 7 (1973) 99–138.
P.E. Gill and W. Murray, “The numerical solution of a problem in the calculus of variations”, in: D.J. Bell, ed.,Recent mathematical developments in control (Academic Press, New York, 1973) pp. 97–122.
P.E. Gill and W. Murray, “Quasi-Newton methods for linearly constrained optimization”, National Physical Laboratory Rept. NAC 32 (1973).
P.E. Gill and W. Murray, “Safeguarded steplength algorithms for optimization using descent methods”, National Physical Laboratory Rept. NAC 37 (1974).
P.E. Gill, W. Murray and S.M. Picken, “The implementation of two modified Newton algorithms for unconstrained optimization”, National Physical Laboratory Rept. NAC 24 (1972).
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”, National Physical Laboratory Rept. NAC 11 (1972).
A. Goldstein and J. Price, “An effective algorithm for minimization”,Numerische Mathematik 10 (1967) 184–189.
J. Greenstadt, “On the relative efficiencies of gradient methods”,Mathematics of Computation 21 (1967) 360–367.
R.S. Martin, G. Peters and J.H. Wilkinson, “Symmetric decomposition of a positive-definite matrix”,Numerische Mathematik 7 (1965) 362–383.
A. Matthews and D. Davies, “A comparison of modified Newton methods for unconstrained optimization”,Computer Journal 14 (1971) 213–294.
G.P. McCormick, “A second-order method for the linearly constrained non-linear programming problem”, in: J.B. Rosen, O.L. Mangasarian and K. Ritter, eds.,Nonlinear programming (Academic Press, New York, 1970) pp. 207–243.
W. Murray, “An algorithm for finding a local minimum of an indefinite quadratic program” National Physical Laboratory Rept. NAC 1 (1971).
W. Murray, “Second derivative methods”, in: W. Murray, ed.,Numerical methods for unconstrained optimization (Academic Press, New York, 1972) pp. 107–122.
J.M. Ortega and W.C. Rheinboldt,Iterative solution of non-linear equations in several variables (Academic Press, New York, 1970).
J. Stoer, “On the numerical solution of constrained least square problems”,SIAM Journal on Numerical Analysis 8 (1971) 382–411.
G. Zoutendijk,Methods of feasible directions (Elsevier, Amsterdam, 1960).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gill, P.E., Murray, W. Newton-type methods for unconstrained and linearly constrained optimization. Mathematical Programming 7, 311–350 (1974). https://doi.org/10.1007/BF01585529
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585529