Skip to main content
SpringerLink
Log in

Newton-type methods for unconstrained and linearly constrained optimization

  • Published:
Mathematical Programming Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. 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.

    Google Scholar 

  2. 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.

    Google Scholar 

  3. P. Businger and G.H. Golub, “Linear least squares solutions by Householder transformations”,Numerische Mathematik 7 (1965) 269–276.

    Google Scholar 

  4. 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.

    Google Scholar 

  5. A.V. Fiacco and G.P. McCormick,Nonlinear programming: sequential unconstrained minimization techniques (Wiley, New York, 1968).

    Google Scholar 

  6. P.E. Gill, G.H. Golub, W. Murray and M.A. Saunders, “Methods for modifying matrix factorizations”,Mathematics of Computation 28 (1974) 505–535.

    Google Scholar 

  7. 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.

    Google Scholar 

  8. P.E. Gill and W. Murray, “A numerically stable form of the simplex algorithm”,Linear Algebra and its Applications 7 (1973) 99–138.

    Google Scholar 

  9. 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.

    Google Scholar 

  10. P.E. Gill and W. Murray, “Quasi-Newton methods for linearly constrained optimization”, National Physical Laboratory Rept. NAC 32 (1973).

  11. P.E. Gill and W. Murray, “Safeguarded steplength algorithms for optimization using descent methods”, National Physical Laboratory Rept. NAC 37 (1974).

  12. 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).

  13. P.E. Gill, W. Murray and S.M. Picken, “The implementation of two modified Newton algorithms for linearly constrained optimization”, to appear.

  14. 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).

  15. A. Goldstein and J. Price, “An effective algorithm for minimization”,Numerische Mathematik 10 (1967) 184–189.

    Google Scholar 

  16. J. Greenstadt, “On the relative efficiencies of gradient methods”,Mathematics of Computation 21 (1967) 360–367.

    Google Scholar 

  17. R.S. Martin, G. Peters and J.H. Wilkinson, “Symmetric decomposition of a positive-definite matrix”,Numerische Mathematik 7 (1965) 362–383.

    Google Scholar 

  18. A. Matthews and D. Davies, “A comparison of modified Newton methods for unconstrained optimization”,Computer Journal 14 (1971) 213–294.

    Google Scholar 

  19. 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.

    Google Scholar 

  20. W. Murray, “An algorithm for finding a local minimum of an indefinite quadratic program” National Physical Laboratory Rept. NAC 1 (1971).

  21. W. Murray, “Second derivative methods”, in: W. Murray, ed.,Numerical methods for unconstrained optimization (Academic Press, New York, 1972) pp. 107–122.

    Google Scholar 

  22. J.M. Ortega and W.C. Rheinboldt,Iterative solution of non-linear equations in several variables (Academic Press, New York, 1970).

    Google Scholar 

  23. J. Stoer, “On the numerical solution of constrained least square problems”,SIAM Journal on Numerical Analysis 8 (1971) 382–411.

    Google Scholar 

  24. G. Zoutendijk,Methods of feasible directions (Elsevier, Amsterdam, 1960).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. National Physical Laboratory, Teddington, Middlesex, England

    Philip E. Gill & Walter Murray

Authors
  1. Philip E. Gill
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Walter Murray
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01585529

Keywords

Search

Navigation