A truncated Newton optimization algorithm in meteorology applications with analytic Hessian/vector products. (English) Zbl 0831.90124

Wang, Zhi; Navon, I. M.; Zou, X.; Le Dimet, F. X.

Comput. Optim. Appl. 4, No. 3, 241-262 (1995).

Summary: A modified version of the truncated-Newton algorithm of S. G. Nash [SIAM J. Sci. Stat. Comput. 6, 599-616 (1985; Zbl 0592.65038)] is presented differing from it only in the use of an exact Hessian vector product for carrying out the large-scale unconstrained optimization required in variational data assimilation. The exact Hessian vector product is obtained by solving an optimal control problem of distributed parameters (i.e. the system under study occupies a certain spatial and temporal domain and is modeled by partial differential equations). The algorithm is referred to as the adjoint truncated-Newton algorithm. The adjoint truncated-Newton algorithm is based on the first and the second order adjoint techniques allowing to obtain a better approximation to the Newton line search direction for the problem tested here. The adjoint truncated-Newton algorithm is applied here to a limited-area shallow water equations model with model generated data where the initial conditions serve as control variables. We compare the performance of the adjoint truncated-Newton algorithm with that of the original truncated- Newton method and the LBFGS (Limited Memory BFGS)method of D. C. Liu and J. Nocedal [Math. Program., Ser. B 45, No. 3, 503-528 (1989; Zbl 0696.90048)]. Our numerical tests yield results which are twice as fast as these obtained by the truncated-Newton algorithm and are faster than the LBFGS method both in terms of number of iterations as well as in terms of CPU time.

MSC:

90C52	Methods of reduced gradient type
90C90	Applications of mathematical programming
86A10	Meteorology and atmospheric physics
90C30	Nonlinear programming

Keywords:

meteorology applications; limited memory BFGS; truncated-Newton algorithm

Citations:

Zbl 0592.65038; Zbl 0696.90048

Software:

Algorithm 500; TNPACK; L-BFGS; tn

References:

[1]	H.T. Banks and K. Kunisch, ?Estimation techniques for distributed parameter systems?, Birkhauser: Boston (Systems & Control: Formulations & Applications), Vol. 11, p. 315, 1989. · Zbl 0695.93020
[2]	J. Burger, J.L. Brizaut, and M. Pogu, ?Comparison of two methods for the calculation of the gradient and of the Hessian of the cost functions associated with differential systems? Mathematics and Computers in Simulation, Vol. 34, pp. 551-562, 1992.
[3]	J.C.P. Bus, ?Convergence of Newton-like methods for solving systems of nonlinear equations?, Numerische Mathematik, Vol. 27, pp. 271-281, 1977. · Zbl 0332.65032
[4]	P. Courtier and O. Talagrand, ?Variational assimilation of meteorological observations with the adjoint equations Part 2. Numerical results?, Q.J.R. Meteorol. Soc., Vol. 113, pp. 1329-1347, 1987.
[5]	W.C. Davidon, ?Variable metric method for minimization,? A.E.C. Research and Development Report, ANL-5990 (Rev.), 1959. · Zbl 0752.90062
[6]	R.S. Dembo, S.C. Eisenstat, and T. Steihaug, ?Inexact Newton methods,? SIAM Journal of Numerical Analysis, Vol. 19, pp. 400-408, 1982. · Zbl 0478.65030
[7]	R.S. Dembo and T. Steihaug, ?Truncated-Newton algorithms for large-scale unconstrained optimization,? Math. Prog., Vol. 26, pp. 190, 212, 1983. · Zbl 0523.90078
[8]	J. Dennis and Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Englewood Cliffs, N. J.: Prentice-Hall, p. 378, 1983. · Zbl 0579.65058
[9]	J. Dennis and B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Englewood Cliffs, N.J.: Prentice-Hall, 1983. · Zbl 0579.65058
[10]	J. Dennis, Personal communication, Dept. of Math., Rice University, Houston, TX, 1994.
[11]	L.C.W. Dixon, ?Use of automatic differentiation for calculating Hessians and Newton steps?, in Automatic Differentiation of Algorithms: Theory, Implementation, and Application, Andreas Griewank and George F. Corliss (eds.) SIAM, Philadelphia, pp. 115-125, 1991. · Zbl 0782.65021
[12]	Ronald M. Errico, Tomislava Vuki?evi?, and Kevin Raeder, ?Examination of the accuracy of a tangent linear model?,Tellus, Vol. 45A, pp. 462-477, 1993.
[13]	J.C. Gilbert, ?Automatic differentiation and iterative processes,? Optimization Methods and Software, Vol. 1, pp. 13-21, 1992.
[14]	P.E. Gill and W. Murray, ?Quasi-Newton methods for unconstrained optimization,? J. Inst. Maths Applics, Vol. 9, pp. 91-108, 1972. · Zbl 0264.49026
[15]	P.E. Gill and W. Murray, Numerical Methods for Unconstrained Optimization, Academic Press, London and New-York, p. 283, 1974. · Zbl 0297.90082
[16]	P.E. Gill and W. Murray, ?Newton-type methods for unconstrained and linearly constrained optimization,? Math. Prog., Vol. 28, pp. 311-350, 1979. · Zbl 0297.90082
[17]	P.E. Gill, W. Murray, M.C. Saunders, and M.H. Wright, ?Computing forward-difference intervals for numerical optimization,? SIAM J. Sci. Stat. Comput., Vol. 4, pp. 310-321, 1983. · Zbl 0514.65044
[18]	A. Grammeltvedt, ?A survey of finite-difference schemes for the primitive equations for a barotropic fluid,? Mon. Wea. Rev., Vol. 97, pp. 387-404, 1969.
[19]	A. Griewank and George F. Corliss, Automatic Differentiation of Algorithms: Theory, Implementation, and Application, SIAM, Philadelphia, p. 353, 1991. · Zbl 0747.00030
[20]	R.W. Hamming, Numerical Methods for Scientists and Engineers, 2nd edition, New York: McGraw-Hill, 1973. · Zbl 0262.65001
[21]	J.F. Lacarra and O. Talagrand, ?Short-range evolution of small perturbations in a barotropic model,?Tellus, Vol. 40A, pp. 81-95, 1988.
[22]	F.X. Le Dimet and O. Talagrand, ?Variational algorithms for analysis and assimilation of meteorological observations: Theoretical aspects,? Tellus, Vol. 38A, pp. 97-110, 1986.
[23]	D.C. Liu, and Jorge Nocedal, ?On the limited memory BFGS method for large scale minimization,? Math. Prog., Vol. 45, pp. 503-528, 1989. · Zbl 0696.90048
[24]	S.G. Nash, ?Truncated-Newton methods?, Ph.D. Thesis, Computer Science Department, Stanford University, CA, 1982.
[25]	S.G. Nash, ?Newton-type minimization via the Lanczos method,? SIAM J. Numer. Anal., Vol. 21, No. 4, pp. 770-788, 1984. · Zbl 0558.65041
[26]	S.G. Nash, ?Truncated-Newton methods for large-scale function minimization,? Applications of Nonlinear Programming to Optimization and Control, H.E. Rauch (ed.), Pergamon Press, Oxford, pp. 91-100, 1984.
[27]	S.G. Nash, ?User’s guide for TN/TNBC: Fortran routines for nonlinear optimization,? Tech. Rep. No., Vol. 397, p. 17, 1984.
[28]	S.G. Nash, ?Solving nonlinear programming problems using truncated-Newton techniques,? Numerical optimization, P.T. Boggs, R.H. Byrd, and R.B. Schnabel (eds.), Philadelphia: SIAM, pp. 119-136, 1984.
[29]	S.G. Nash, ?Preconditioning of truncated-Newton methods,? SIAM J. Sci. Stat. Comput., Vol. 6, No. 3, pp. 599-616, 1985. · Zbl 0592.65038
[30]	S.G. Nash and A. Sofer, ?Block truncated-Newton methods for parallel optimization,? Math. Prog., Vol. 45, pp. 529-546, 1989. · Zbl 0689.90060
[31]	S.G. Nash and A. Sofer, ?A parallel line search for Newton type methods in computer science and statistics,? in Proceeding 21-st Symposium on the Interface, K. Berk and L. Malone (eds.), ASA, pp. 134-137, 1989.
[32]	S.G. Nash and Jorge Nocedal, ?A numerical study of the limited memory BFGS method and the truncated-Newton method for large scale optimization,? Tech. Rep. NAM, Vol. 2, Dept. of Electrical Engineering and Computer Science, Northwestern University, p. 19, Dec. 1989. · Zbl 0756.65091
[33]	S.G. Nash and A. Sofer, ?Assessing a search direction within a truncated-Newton method,? Operations Research Letters, Vol. 9, No. 4, pp. 219-221, 1990. · Zbl 0706.90073
[34]	I.M. Navon and D.M. Legler, ?Conjugate gradient methods for large scale minimization in meteorology,? Mon. Wea. Rev., Vol. 115, pp. 1479-1502, 1987.
[35]	I.M. Navon, X.L. Zou, J. Derber, and J. Sela, ?Variational data assimilation with an adiabatic version of the NMC Spectral Model,? Mon. Wea. Rev., Vol. 122, pp. 1433-1446, 1992.
[36]	J. Nocedal, ?Updating quasi-newton matrices with limited storage,? Mathematics of Computation, Vol. 35, pp. 773-782, 1980. · Zbl 0464.65037
[37]	D.P. O’Leary, ?A discrete Newton algorithm for minimizing a function of many variables,? Math. Prog., Vol. 23, pp. 20-23, 1983. · Zbl 0477.90055
[38]	S. Omatu and John H. Seinfeld, ?Distributed Parameter Systems, Theory and Applications,? Oxford Science Publications, Oxford Mathematical Monographs, Claredon Press, Oxford, p. 430, 1989. · Zbl 0675.93001
[39]	Santosa, Fadil, and William W. Symes, ?Computation of the Hessian for least-squares solutions of inverse problems of reflection seismology,? Inverse Problems, Vol. 4, pp. 211-233, 1988. · Zbl 0642.65052
[40]	Santosa, Fadil, and William W. Symes, ?An analysis of least squares velocity inversion,? Society of Exploration Geophysicists, Geophysical monograph #4, Tulsa, 1989.
[41]	T. Schlick and A. Fogelson, ?TNPACK?A truncated Newton minimization Package for large-scale problems: I. Algorithm and usage,? ACMTOMS, Vol. 18, No. 1, pp. 46-70, 1992. · Zbl 0892.65030
[42]	T. Schlick and A. Fogelson, ?TNPACK?A Truncated Newton minimization package for large-scale problems: II. Implementation examples,? ACMTOMS, Vol. 18, No. 1, pp. 71-111, 1992. · Zbl 0892.65031
[43]	D.F. Shanno and K.H. Phua, ?Remark on algorithm 500?a variable method subroutine for unconstrained nonlinear minimization?, ACM Trans. on Mathematical Software, Vol. 6, pp. 618-622, 1980.
[44]	G.W. Stewart III, ?A modification of Davidon’s minimization method to accept difference approximations of derivatives,? Journal of the Association for Computing Machinery, Vol. 14, No. 1, pp. 72-83, 1967. · Zbl 0239.65056
[45]	William W. Symes, ?A differential semblance algorithm for the inverse problem of reflection seismology,? Computers Math. Applic., Vol. 22, No. 4/5, pp. 147-178, 1991. · Zbl 0728.73023
[46]	O. Talagrand and P. Courtier, ?Variational assimilation of meteorological observations with the adjoint vorticity equation?Part 1, Theory,? Q.J.R. Meteorol. Soc., Vol. 113, pp. 1311-1328, 1987.
[47]	Thomas R. Cuthbert, Jr., Optimization using personal computers, John Wiley & Sons, New York, p. 474, 1987.
[48]	Z. Wang, I.M. Navon, F.X. Le Dimet, and X. Zou, ?The Second Order Adjoint Analysis: Theory and Application,? Meteorology and Atmospheric Physics, Vol. 50, pp. 3-20, 1992.
[49]	Z. Wang, I.M. Navon, and X. Zou, ?The adjoint truncated Newton algorithm for large-scale unconstrained optimization,? Tech. Rep. FSU-SCRI-92-170, Florida State University, Tallahassee, Florida, p. 44, 1993.
[50]	Zhi, Wang, ?Variational data assimilation with 2-D shallow water equations and 3-D FSU global spectral models,? Tech. Rep. FSU-SCRI-93T-149, Florida State University, Tallahassee, Florida, p. 235, 1993.
[51]	William W.-G. Yeh, ?Review of parameter identification procedures in groundwater hydrology: The inverse problem,? Water Resources Research, Vol. 22, No. 2, pp. 95-108, 1986.
[52]	X. Zou, I.M. Navon, F.X. Le Dimet, A. Nouailler, and T. Schlick, ?A comparison of efficient large-scale minimization algorithms for optimal control applications in meteorology, Tech. Rep. FSU-SCRI-90-167, Florida State University, Tallahassee, Florida, p. 44, 1990.
[53]	X. Zou, I.M. Navon, M. Berger, Paul K.H. Phua, T. Schlick, and F.X. Le Dimet, ?Numerical experience with limited-Memory Quasi-Newton methods and Truncated Newton methods,? SIAM Jour. on Numerical Optimization, Vol. 3, pp. 582-608, 1993. · Zbl 0784.90086
[54]	X. Zou, I.M. Navon, and F.X. Le Dimet, ?Incomplete observations and control of gravity waves in variational data assimilation,? Tellus, Vol. 44A, pp. 273-296, 1992.