Skip to main content
SpringerLink
Log in

A truncated Newton optimization algorithm in meteorology applications with analytic Hessian/vector products

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

A modified version of the truncated-Newton algorithm of Nash ([24], [25], [29]) 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 products 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 [29] and the LBFGS (Limited Memory BFGS) method of Liu and Nocedal [23]. 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.

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

Access this article

Log in via an institution

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

  1. H.T. Banks and K. Kunisch, “Estimation techniques for distributed parameter systems”, Birkhauser: Boston (Systems & Control: Formulations & Applications), Vol. 11, p. 315, 1989.

    Google Scholar 

  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.

    Google Scholar 

  3. J.C.P. Bus, “Convergence of Newton-like methods for solving systems of nonlinear equations”, Numerische Mathematik, Vol. 27, pp. 271–281, 1977.

    Google Scholar 

  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.

    Google Scholar 

  5. W.C. Davidon, “Variable metric method for minimization,” A.E.C. Research and Development Report, ANL-5990 (Rev.), 1959.

  6. R.S. Dembo, S.C. Eisenstat, and T. Steihaug, “Inexact Newton methods,” SIAM Journal of Numerical Analysis, Vol. 19, pp. 400–408, 1982.

    Google Scholar 

  7. R.S. Dembo and T. Steihaug, “Truncated-Newton algorithms for large-scale unconstrained optimization,” Math. Prog., Vol. 26, pp. 190, 212, 1983.

    Google Scholar 

  8. J. Dennis and Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Englewood Cliffs, N. J.: Prentice-Hall, p. 378, 1983.

    Google Scholar 

  9. J. Dennis and B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Englewood Cliffs, N.J.: Prentice-Hall, 1983.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  13. J.C. Gilbert, “Automatic differentiation and iterative processes,” Optimization Methods and Software, Vol. 1, pp. 13–21, 1992.

    Google Scholar 

  14. P.E. Gill and W. Murray, “Quasi-Newton methods for unconstrained optimization,” J. Inst. Maths Applics, Vol. 9, pp. 91–108, 1972.

    Google Scholar 

  15. P.E. Gill and W. Murray, Numerical Methods for Unconstrained Optimization, Academic Press, London and New-York, p. 283, 1974.

    Google Scholar 

  16. P.E. Gill and W. Murray, “Newton-type methods for unconstrained and linearly constrained optimization,” Math. Prog., Vol. 28, pp. 311–350, 1979.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  19. A. Griewank and George F. Corliss, Automatic Differentiation of Algorithms: Theory, Implementation, and Application, SIAM, Philadelphia, p. 353, 1991.

    Google Scholar 

  20. R.W. Hamming, Numerical Methods for Scientists and Engineers, 2nd edition, New York: McGraw-Hill, 1973.

    Google Scholar 

  21. J.F. Lacarra and O. Talagrand, “Short-range evolution of small perturbations in a barotropic model,”Tellus, Vol. 40A, pp. 81–95, 1988.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  24. S.G. Nash, “Truncated-Newton methods”, Ph.D. Thesis, Computer Science Department, Stanford University, CA, 1982.

    Google Scholar 

  25. S.G. Nash, “Newton-type minimization via the Lanczos method,” SIAM J. Numer. Anal., Vol. 21, No. 4, pp. 770–788, 1984.

    Google Scholar 

  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.

    Google Scholar 

  27. S.G. Nash, “User's guide for TN/TNBC: Fortran routines for nonlinear optimization,” Tech. Rep. No., Vol. 397, p. 17, 1984.

    Google Scholar 

  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.

    Google Scholar 

  29. S.G. Nash, “Preconditioning of truncated-Newton methods,” SIAM J. Sci. Stat. Comput., Vol. 6, No. 3, pp. 599–616, 1985.

    Google Scholar 

  30. S.G. Nash and A. Sofer, “Block truncated-Newton methods for parallel optimization,” Math. Prog., Vol. 45, pp. 529–546, 1989.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  36. J. Nocedal, “Updating quasi-newton matrices with limited storage,” Mathematics of Computation, Vol. 35, pp. 773–782, 1980.

    Google Scholar 

  37. D.P. O'Leary, “A discrete Newton algorithm for minimizing a function of many variables,” Math. Prog., Vol. 23, pp. 20–23, 1983.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  47. Thomas R. Cuthbert, Jr., Optimization using personal computers, John Wiley & Sons, New York, p. 474, 1987.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Center for Analysis and Prediction of Storms, University of Oklahoma, 73019, Norman, OK

    Zhi Wang

  2. Department of Mathematics and Supercomputer Computations, Research Institute, Florida State University, 32306, Tallahassee, FL

    I. M. Navon

  3. National Center for Atmospheric Research, 80307, Boulder, Colorado

    X. Zou

  4. Grenoble, Laboratoire de Modelisation et Calcul, B.P. 53X, 38041, Grenoble Cedex, France

    F. X. Le Dimet

Authors
  1. Zhi Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. I. M. Navon
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. X. Zou
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. F. X. Le Dimet
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wang, Z., Navon, I.M., Zou, X. et al. A truncated Newton optimization algorithm in meteorology applications with analytic Hessian/vector products. Comput Optim Applic 4, 241–262 (1995). https://doi.org/10.1007/BF01300873

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Keywords

Search

Navigation