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.
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.
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.
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).
A. Buckley, “A combined conjugate gradient quasi-Newton minimization algorithm,”Mathematical Programming 15 (1978) 200–210.
A. Buckley, “Algorithm 630: BBVSCG—A variable-storage algorithm for function minimization,”ACM Transactions on Mathematical Software 11 (1985) 103–119.
A. Buckley, “Remark on algorithm 630,”ACM Transactions on Mathematical Software 15 (1989) 262–274.
A. Buckley and A. LeNir, “QN-like variable storage conjugate gradients,”Mathematical Programming 27 (1983) 155–175.
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.
P. Courtier, “Application du contrôle optimal à la prévision numérique en météorologie,” Thesis, University of Paris VI (Paris, 1987).
J.E. Dennis and J. J. Moré, “Quasi-Newton methods, motivation and theory,”SIAM Review 19 (1977) 46–89.
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.
R. Fletcher, “Low storage methods for unconstrained optimization,” NA Report 117, University of Dundee (Dundee, UK, 1988).
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).
W.A. Gruver and E. Sachs,Algorithmic Methods in Optimal Control, Research Notes in Mathematics, Vol. 47 (Pitman, London, 1980).
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).
A. Klug, “Joint probability distributions of structure factors and the phase problem,”Acta Crystallographica 11 (1958) 515–543.
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.
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).
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.
J.L. Nazareth, “Conjugate gradient methods less dependent on conjugacy,”SIAM Review 28/4 (1986) 501–511.
J. Nocedal, “Updating quasi-Newton matrices with limited storage,”Mathematics of Computation 35/151 (1980) 773–782.
A. Nouailler, “Assimilation de données à petite échelle: technique de contrôle optimal,” Thesis, University of Clermont Ferrand (Clermont Ferrand, 1987).
S. Oren and E. Spedicato, “Optimal conditioning of self-scaling variable metric algorithms,”Mathematical Programming 10 (1976) 70–90.
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).
A. Perry, “A modified conjugate gradient algorithm,” Discussion Paper 229, Center for Mathematical Studies in Economics and Management Science, Northwestern University (Evanston, IL, 1976).
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).
M.J.D. Powell, “Restart procedures for the conjugate gradient method,”Mathematical Programming 12 (1977) 241–254.
L. Schwartz,Les Tenseurs (Hermann, Paris, 2nd ed., 1981).
D.F. Shanno, “Conjugate gradient methods with inexact searches,”Mathematics of Operations Research 3/3 (1978) 244–256.
D.F. Shanno and K.-H. Phua, “Matrix conditioning and nonlinear optimization,”Mathematical Programming 14 (1978a) 149–160.
D.F. Shanno and K.-H. Phua, “Numerical comparison of several variable metric algorithms,”Journal of Optimization Theory and Applications 25 (1978b) 507–518.
J. Weidmann,Linear operators in Hilbert spaces, Graduate Texts in Mathematics, Vol. 68 (Springer, Heidelberg, 1980).
P. Wolfe, “Convergence conditions for ascent methods,”SIAM Review 11/2 (1969) 226–235.
K. Zimmermann, “ORAL: All-purpose molecular mechanics simulator & energy minimizer,” in preparation (1989).
Author information
Authors and Affiliations
Additional information
Work supported in part by FNRS (Fonds National de la Recherche Scientifique), Belgium.
Rights 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
Issue Date:
DOI: https://doi.org/10.1007/BF01589113