Skip to main content
Log in

Some numerical experiments with variable-storage quasi-Newton algorithms

  • Published:
Mathematical Programming Submit manuscript

Abstract

This paper describes some numerical experiments with variable-storage quasi-Newton methods for the optimization of some large-scale models (coming from fluid mechanics and molecular biology). In addition to assessing these kinds of methods in real-life situations, we compare an algorithm of A. Buckley with a proposal by J. Nocedal. The latter seems generally superior, provided that careful attention is given to some nontrivial implementation aspects, which concern the general question of properly initializing a quasi-Newton matrix. In this context, we find it appropriate to use a diagonal matrix, generated by an update of the identity matrix, so as to fit the Rayleigh ellipsoid of the local Hessian in the direction of the change in the gradient.

Also, a variational derivation of some rank one and rank two updates in Hilbert spaces is given.

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

Access this article

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

  • E.M.L. Beale, “A derivation of conjugate gradients,” in: F. Lootsma, ed.,Numerical Methods for Non-linear Optimization (Academic Press, London, 1972) pp. 39–43.

    Google Scholar 

  • M.O. Bristeau, O. Pironneau, R. Glowinski, J. Périaux, P. Perrier and G. Poirier, “On the numerical solution of nonlinear problems in fluid dynamics by least squares and finite element methods (II). Application to transonic flow simulations,”Computer Methods in Applied Mechanics and Engineering 51 (1985) 363–394.

    Google Scholar 

  • M.O. Bristeau, R. Glowinski and J. Périaux, “Numerical methods for the Navier-Stokes equations,” in: R. Gruber, ed.,Finite elements methods in physics, Computer Physics Report, Vol. 6 (North-Holland, Amsterdam, 1987).

    Google Scholar 

  • A. Buckley, “A combined conjugate gradient quasi-Newton minimization algorithm,”Mathematical Programming 15 (1978) 200–210.

    Google Scholar 

  • A. Buckley, “Algorithm 630: BBVSCG—A variable-storage algorithm for function minimization,”ACM Transactions on Mathematical Software 11 (1985) 103–119.

    Google Scholar 

  • A. Buckley, “Remark on algorithm 630,”ACM Transactions on Mathematical Software 15 (1989) 262–274.

    Google Scholar 

  • A. Buckley and A. LeNir, “QN-like variable storage conjugate gradients,”Mathematical Programming 27 (1983) 155–175.

    Google Scholar 

  • R.H. Byrd, J. Nocedal and Y.-X. Yuan, “Global convergence of a class of quasi-Newton methods on convex problems,”SIAM Journal on Numerical Analysis 24 (1987) 1171–1190.

    Google Scholar 

  • P. Courtier, “Application du contrôle optimal à la prévision numérique en météorologie,” Thesis, University of Paris VI (Paris, 1987).

    Google Scholar 

  • J.E. Dennis and J. J. Moré, “Quasi-Newton methods, motivation and theory,”SIAM Review 19 (1977) 46–89.

    Google Scholar 

  • J.E. Dennis and R.B. Schnabel, “A new derivation of symmetric positive definite secant updates,” in: O.L. Mangasarian, R.R. Meyer and S.M. Robinson, eds.,Nonlinear Programming, Vol. 4 (Academic Press, New York, 1981) pp. 167–199.

    Google Scholar 

  • R. Fletcher, “Low storage methods for unconstrained optimization,” NA Report 117, University of Dundee (Dundee, UK, 1988).

    Google Scholar 

  • P.E. Gill and W. Murray, “Conjugate gradient methods for large scale nonlinear optimization,” Technical Report SOL 79-15, Department of Operations Research, Stanford University (Stanford, CA, 1979).

    Google Scholar 

  • W.A. Gruver and E. Sachs,Algorithmic Methods in Optimal Control, Research Notes in Mathematics, Vol. 47 (Pitman, London, 1980).

    Google Scholar 

  • H. Hauptman and J. Karle,Solution of the phase-problem. I: The centrosymmetric crystal, American Crystallographic Association, Monograph 3 (Polycrystal Book Service, Pittsburgh, PA, 1953).

    Google Scholar 

  • A. Klug, “Joint probability distributions of structure factors and the phase problem,”Acta Crystallographica 11 (1958) 515–543.

    Google Scholar 

  • C. Lemaréchal, “A view of line-searches,” in: A. Auslender, W. Oettli and J. Stoer, eds.,Optimization and optimal control, Lecture Notes in Control and Information Science, Vol. 30 (Springer, Heidelberg, 1981) pp. 59–78.

    Google Scholar 

  • D.C. Liu and J. Nocedal, “On the limited memory BFGS method for large scale optimization,” Technical Report NAM 03, Department of Electrical Engineering and Computer Science, Northwestern University (Evanston, IL, 1988).

    Google Scholar 

  • J.L. Nazareth, “A relationship between the BFGS and conjugate gradient algorithms and its implications for new algorithms,”SIAM Journal on Numerical Analysis 16 (1979) 794–800.

    Google Scholar 

  • J.L. Nazareth, “Conjugate gradient methods less dependent on conjugacy,”SIAM Review 28/4 (1986) 501–511.

    Google Scholar 

  • J. Nocedal, “Updating quasi-Newton matrices with limited storage,”Mathematics of Computation 35/151 (1980) 773–782.

    Google Scholar 

  • A. Nouailler, “Assimilation de données à petite échelle: technique de contrôle optimal,” Thesis, University of Clermont Ferrand (Clermont Ferrand, 1987).

    Google Scholar 

  • S. Oren and E. Spedicato, “Optimal conditioning of self-scaling variable metric algorithms,”Mathematical Programming 10 (1976) 70–90.

    Google Scholar 

  • F. Ortegón Gallego, “Estudio de un modelo matemático de turbulencia obtenido mediante técnicas de homogeneización,” Thesis, University of Sevilla (Sevilla, 1988).

    Google Scholar 

  • A. Perry, “A modified conjugate gradient algorithm,” Discussion Paper 229, Center for Mathematical Studies in Economics and Management Science, Northwestern University (Evanston, IL, 1976).

    Google Scholar 

  • A. Perry, “A class of conjugate gradient algorithms with a two-step variable metric memory,” Discussion Paper 269, Center for Mathematical Studies in Economics and Management Science, Northwestern University (Evanston, IL, 1977).

    Google Scholar 

  • M.J.D. Powell, “Restart procedures for the conjugate gradient method,”Mathematical Programming 12 (1977) 241–254.

    Google Scholar 

  • L. Schwartz,Les Tenseurs (Hermann, Paris, 2nd ed., 1981).

    Google Scholar 

  • D.F. Shanno, “Conjugate gradient methods with inexact searches,”Mathematics of Operations Research 3/3 (1978) 244–256.

    Google Scholar 

  • D.F. Shanno and K.-H. Phua, “Matrix conditioning and nonlinear optimization,”Mathematical Programming 14 (1978a) 149–160.

    Google Scholar 

  • D.F. Shanno and K.-H. Phua, “Numerical comparison of several variable metric algorithms,”Journal of Optimization Theory and Applications 25 (1978b) 507–518.

    Google Scholar 

  • J. Weidmann,Linear operators in Hilbert spaces, Graduate Texts in Mathematics, Vol. 68 (Springer, Heidelberg, 1980).

    Google Scholar 

  • P. Wolfe, “Convergence conditions for ascent methods,”SIAM Review 11/2 (1969) 226–235.

    Google Scholar 

  • K. Zimmermann, “ORAL: All-purpose molecular mechanics simulator & energy minimizer,” in preparation (1989).

Download references

Author information

Authors and Affiliations

Authors

Additional information

Work supported in part by FNRS (Fonds National de la Recherche Scientifique), Belgium.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gilbert, J.C., Lemaréchal, C. Some numerical experiments with variable-storage quasi-Newton algorithms. Mathematical Programming 45, 407–435 (1989). https://doi.org/10.1007/BF01589113

Download citation

  • Issue Date:

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

AMS (MOS) Subject Classifications

Key words

Navigation