The adjoint Newton algorithm for large-scale unconstrained optimization in meteorology applications. (English) Zbl 0912.90265

Wang, Zhi; Droegemeier, K.

Comput. Optim. Appl. 10, No. 3, 283-320 (1998); erratum ibid. 74, No. 3, 949 (2019).

Summary: A new algorithm is presented for carrying out large-scale unconstrained optimization required in variational data assimilation using the Newton method. The algorithm is referred to as the adjoint Newton algorithm. The adjoint Newton algorithm is based on the first- and second-order adjoint techniques allowing us to obtain the Newton line search direction by integrating a tangent linear equations model backwards in time (starting from a final condition with negative time steps). The error present in approximating the Hessian (the matrix of second-order derivatives) of the cost function with respect to the control variables in the quasi-Newton type algorithm is thus completely eliminated, while the storage problem related to the Hessian no longer exists since the explicit Hessian is not required in this algorithm. The adjoint Newton algorithm is applied to three one-dimensional models and to a two-dimensional limited-area shallow water equations model with both model generated and first global geophysical experiment data. We compare the performance of the adjoint Newton algorithm with that of truncated Newton, adjoint truncated Newton, and LBFGS methods. Our numerical tests indicate that the adjoint Newton algorithm is very efficient and could find the minima within three or four iterations for problems tested here. In the case of the two-dimensional shallow water equations model, the adjoint Newton algorithm improves upon the efficiencies of the truncated Newton and LBFGS methods by a factor of at least 14 in terms of the CPU time required to satisfy the same convergence criterion.
The Newton, truncated Newton and LBFGS methods are general purpose unconstrained minimization methods. The adjoint Newton algorithm is only useful for optimal control problems where the model equations serve as strong constraints and their corresponding tangent linear model may be integrated backwards in time. When the backwards integration of the tangent linear model is ill-posed in the sense of Hadamard, the adjoint Newton algorithm may not work. Thus, the adjoint Newton algorithm must be used with some caution. A possible solution to avoid the current weakness of the adjoint Newton algorithm is proposed.

MSC:

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

Keywords:

large-scale unconstrained optimization; variational data assimilation; adjoint Newton algorithm; LBFGS methods; truncated Newton

Software:

tn; Algorithm 500; L-BFGS; TNPACK

References:

[1]	A. Bennett, Inverse Problem in Physical Oceanography, Cambridge University Press, 1992, pp. 346. · Zbl 0782.76002
[2]	M.S. Berger, Nonlinearity and Functional Analysis, Academic Press: New York, 1977, pp. 417.
[3]	Caradus, S. R., Operator Theory of the Pseudo-Inverse, 67 (1974), Kingston, Ontario, Canada · Zbl 0286.47001
[4]	Carey, G. F.; Oden, J. T., No article title, Finite Elements Computational Aspects, 3, 350 (1984)
[5]	W.C. Davidon, “Variable metric method for minimization,” A.E.C. Research and Development Report, ANL-5990 (Rev.). · 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]	J. Dennis and Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall: Englewood Cliffs, NJ, 1983, pp. 378. · Zbl 0847.65038
[8]	J. Dieudonne, Foundations of Modern Analysis, Academic Press: New York, 1960, pp. 361.
[9]	John Fritz, Partial Differential Equations, 4th edition, Springer-Verlag: New York, 1986, pp. 247.
[10]	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
[11]	P.E. Gill and W. Murray, Practical Optimization, Academic Press, 1981, pp. 401. · Zbl 0503.90062
[12]	G.H. Golub and C.F. Van Loan, Matrix Computations, 2nd edition, The Johns Hopkins University Press: Baltimore and London, 1989, pp. 642.
[13]	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.
[14]	R.N. Hoffmann, “SASS wind ambiguity removal by direct minimization,” Mon. Wea. Rev., vol. 110, pp. 434-445, 1982.
[15]	R.N. Hoffmann, “SASS wind ambiguity removal by direct minimization Part II: Use of smoothness and dynamical constraints,” Mon. Wea. Rev., vol. 112, pp. 1829-1852, 1984.
[16]	R.N. Hoffmann, “A four dimensional analysis exactly satisfying equations of motion,” Mon. Wea. Rev., vol. 114, pp. 388-397, 1986.
[17]	J.F. Lacarra and O. Talagrand, Short-range evolution of small perturbations in a barotropic model,” Tellus, vol. 40A, pp. 81-95, 1988.
[18]	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.
[19]	J.L. Lions, Optimal control of systems governed by partial differential equations,” Translated by S.K. Mitter, Springer-Verlag: Berlin-Heidelberg, 1971, pp. 404.
[20]	D.C. Liu and Jorge Nocedal, “On the limited memory BFGS method for large scale minimization,” Mathematical Programming, vol. 45, pp. 503-528, 1989. · Zbl 0696.90048
[21]	David G. Luenberger, Linear and Nonlinear Programming, 2nd edition, Addison-Wesley: Reading, MA, 1984, pp. 491. · Zbl 1134.90040
[22]	Nash, S. G.; Rauch, H. E. (ed.), Truncated-Newton methods for large-scale function minimization, 91-100 (1984), Oxford
[23]	Nash, S. G.; Boggs, P. T. (ed.); Byrd, R. H. (ed.); Schnabel, R. B. (ed.), Solving nonlinear programming problems using truncated Newton techniques, 119-136 (1984), Philadelphia
[24]	S.G. Nash, “Preconditioning of truncated-Newton methods,” SIAM J. Sci. Stat. Comput., vol. 6, no.3, pp. 599-616, 1985. · Zbl 0592.65038
[25]	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, 02, Department of Electrical Engineering and Computer Science, Northwestern University, 1989, p. 19. · Zbl 0756.65091
[26]	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.
[27]	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.
[28]	J. Nocedal, “Updating quasi-Newton matrices with limited storage,” Mathematics of Computation, vol. 35, pp. 773-782, 1980. · Zbl 0464.65037
[29]	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
[30]	Z. Pu, E. Kalnay, and J. Sela, “Sensitivity of forecast error to initial conditions with a quasi-inverse linear method,” Mon. Wea. Rev., 1996, accepted for publication.
[31]	C.R. Rao and S.K. Mitra, Generalized Inverse of Matrices and its Applications to Statistics, John Wiley & and Sons, 1971, p. 240. · Zbl 0236.15004
[32]	Fadil Santosa 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
[33]	Fadil Santosa and William W. Symes, “An analysis of least squares velocity inversion,” Society of Exploration Geophysicists, Geophysical Monograph #4, Tulsa, 1989. · Zbl 0642.65052
[34]	T. Schlick and A. Fogelson, “TNPACK-Atruncated Newton minimization package for large-scale problems: I. Algorithm and usage,” ACMTOMS, vol. 18, no.1, pp. 46-70, 1992a. · Zbl 0892.65030
[35]	T. Schlick and A. Fogelson, “TNPACK-Atruncated Newton minimization package for large-scale problems: II. Implementation examples,” ACMTOMS, vol. 18, no.1, pp. 71-111, 1992b. · Zbl 0892.65031
[36]	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.
[37]	J. Stoer and R. Bulirsch, Introduction to Numerical Analysis, 2nd edition, Springer-Verlag: New York, 1976, pp. 659.
[38]	William W. Symes, “A differential semblance algorithm for the inverse problem of reflection seismology,” Computers Math. Applic., vol. 22, nos.4/5, pp. 147-178, 1991. · Zbl 0728.73023
[39]	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.
[40]	Zhi Wang, “Variational data assimilation with 2D shallow water equations and 3DFSU global spectral models,” Tech. Rep. FSU-SCRI-93T-149, Florida State University, Tallahassee, Florida, 1993, p. 235.
[41]	Zhi Wang, I.M. Navon, F.X. Le Dimet, and X. Zou, “The second order adjoint analysis: Theory and application,” Meteorol. and Atmos. Phy., vol. 50, pp. 3-20, 1992.
[42]	Zhi Wang, I.M. Navon, X. Zou, and F.X. Le Dimet, “A truncated Newton optimization algorithm in meteorology applications with analytic Hessian/vector products,” Computational Optimization and Applications, vol. 4, no.3, pp. 241-262, 1995. · Zbl 0831.90124
[43]	Zhi Wang, Kelvin K. Droegemeier, and L. White, “Application of a New Adjoint Newton Algorithm to the 3-D ARPS Storm Scale Model Using Simulated Data,” Accepted for publication by Mon. Wea. Rev., 1997.
[44]	X.L. 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.