×

Representations of quasi-Newton matrices and their use in limited memory methods. (English) Zbl 0809.90116

The authors derive new representations of limited memory quasi-Newton matrices and show how to use them efficiently in the kind of matrix computations required in constrained optimization methods. They present new expressions for both the BFGS and symmetric rank-one formulae for optimization and also derive a compact expression for Broyden’s method for solving systems of nonlinear equations.
These representations allow us to efficiently implement limited memory methods for large constrained optimization problems. In particular, it is discussed how to compute projections of limited memory matrices onto subspaces.

MSC:

90C30 Nonlinear programming
90C06 Large-scale problems in mathematical programming

Software:

L-BFGS; LBFGS-B
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Barnes, ”An algorithm for solving nonlinear equations based on the secant method,”Computer Journal 8 (1965) 66–67. · Zbl 0254.65036 · doi:10.1093/comjnl/8.2.113
[2] L. Biegler, J. Nocedal and C. Schmid, ”Reduced Hessian methods for large scale constrained optimization,” Technical Report, Department of Electrical Engineering and Computer Science, Northwestern University (Evanston, IL, 1993). · Zbl 0828.65061
[3] C.G. Broyden, ”A class of methods for solving nonlinear simultaneous equations,”Mathematics of Computation 19 (1965) 577–593. · Zbl 0131.13905 · doi:10.1090/S0025-5718-1965-0198670-6
[4] A. Buckley and A. LeNir, ”QN-like variable storage conjugate gradients,”Mathematical Programming 27 (1983) 103–119. · Zbl 0519.65038 · doi:10.1007/BF02591943
[5] R.H. Byrd, P. Lu and J. Nocedal, ”A limited memory algorithm for bound constrained optimization,” Technical Report, Department of Electrical Engineering and Computer Science, Northwestern University (Evanston, IL, 1993). · Zbl 0836.65080
[6] A.R. Conn, N.I.M. Gould and Ph.L. Toint, ”Testing a class of methods for solving minimization problems with simple bounds on the variables,”Mathematics of Computation 50/182 (1988) 399–430. · Zbl 0645.65033 · doi:10.1090/S0025-5718-1988-0929544-3
[7] J.E. Dennis Jr. and R.B. Schnabel,Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Prentice-Hall, Englewood Cliffs, NJ, 1983).
[8] R. Fletcher,Practical Methods of Optimization (Wiley, Chichester, 1987, 2nd ed.). · Zbl 0905.65002
[9] D.M. Gay and R.B. Schnabel, ”Solving systems of nonlinear equations by Broyden’s method with projected updates,” in: O.L. Mangasarian, R.R. Meyer and S.M. Robinson, eds.,Nonlinear Programming 3 (Academic Press, New York, 1978) pp. 245–281.
[10] J.C. Gilbert and C. Lemaréchal, ”Some numerical experiments with variable storage quasi-Newton algorithms,”Mathematical Programming 45 (1989) 407–436. · Zbl 0694.90086 · doi:10.1007/BF01589113
[11] J.C. Gilbert and J. Nocedal, ”The limited memory step computation and automatic differentiation,”Applied Math Letters 6(3) (1993) 47–50. · Zbl 00270151 · doi:10.1016/0893-9659(93)90032-I
[12] A. Griewank, ”On automatic differentiation,” in: M. Iri and K. Tanabe, eds.,Mathematical Programming (Kluwer Academic Publishers, Tokyo, 1989) pp. 83–107. · Zbl 0696.65015
[13] H. Fayez Khalfan, ”Topics in quasi-Newton methods for unconstrained optimization,” Ph.D. thesis, Department of Mathematics, University of Colorado (Boulder, CO, 1989).
[14] H. Fayez Khalfan, R.H. Byrd, and R.B. Schnabel, ”A theoretical and experimental study of the symmetric rank one update,”SIAM Journal on Optimization 3 (1993) 1–24. · Zbl 0771.65029 · doi:10.1137/0803001
[15] D.C. Liu and J. Nocedal, ”On the limited memory BFGS method for large scale optimization,”Mathematical Programming 45 (1989) 503–528. · Zbl 0696.90048 · doi:10.1007/BF01589116
[16] D.Q. Mahidhara and L. Lasdon, ”An SQP algorithm for large sparse nonlinear programs,” Technical report, MSIS Department, School of Business Administration, University of Texas (Austin, TX, 1990).
[17] H. Matthies and G. Strang, ”The solution of nonlinear finite element equations,”International Journal of Numerical Methods in Engineering 14 (1979) 1613–1626. · Zbl 0419.65070 · doi:10.1002/nme.1620141104
[18] J. Nocedal, ”Updating quasi-Newton matrices with limited storage,”Mathematics of Computation 35 (1980) 773–782. · Zbl 0464.65037 · doi:10.1090/S0025-5718-1980-0572855-7
[19] J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New York, 1970). · Zbl 0241.65046
[20] R.B. Schnabel, ”Quasi-Newton methods using multiple secant equations,” Technical Report CU-CS-247-83, Department of Computer Science, University of Colorado (Boulder, CO, 1983).
[21] H.F. Walker, ”Implementation of the GMRES method using Householder transformations,”SIAM Journal on Scientific and Statistical Computing 9(1) (1988) 152–163. · Zbl 0698.65021 · doi:10.1137/0909010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.