A preconditioning algorithm for large-scale minimization problems

Milija Županski

doi:10.3402/tellusa.v45i5.15048

A preconditioning algorithm for large-scale minimization problems

Tellus

Volume 45 (1993): Issue 5

By: Milija Županski

Open Access

|Jan 1993

Abstract

A new preconditioning algorithm is proposed, employing a Taylor series expansion of the cost-function, and the relation between the adjustment of the control variable and the computed gradient norm. The preconditioning matrix is a positive definite diagonal matrix, being a product of two positive definite diagonal matrices. One is the weight matrix related to the Hessian matrix definition in the case of identity model operator (“rough” scaling), and the other matrix is interpreted as a refined scaling of the control variable. The procedure is quite easy to implement, and the computer time and space requirements are negligible. The algorithm was tested in two cases of realistic four-dimensional variational data assimilation experiments, performed using an adiabatic version of the NMC's new regional forecast model and operationally obtained optimal interpolation analyses. Test results show a significant improvement in the decrease of the cost-function and the gradient norm when using the new preconditioning procedure. The preconditioning was applied to a memoryless quasi-Newton method, however, the technique should be applicable to other minimization algorithms.

References

Axelsson , O. and Barker , V. A . 1984 . Finite-element solution of boundary-value problems. Theory and computation . Academic Press (Computer Science and Applied Mathematics Series) , 432 pp.
Search in Google Scholar Back to article
Chao , W. C. and Chang , L. P . 1992 . Development of a four-dimensional variational assimilation system using the adjoint method at GLA. Part I: Dynamics. Mon . Wea. Re v . 120 , 1661 – 1673 .
Search in Google Scholar Back to article
Conway , J. B . 1985 . A course in functional analysis . Springer-Verlag , New York , 404 pp.
Search in Google Scholar Back to article
Courtier , P. , Thepaut , J.-N. and Hollingsworth , A . 1992 . A strategy for operational implementation of 4D-VAR. Proceedings of the ECMWF workshop on Variational assimilation with emphasis on three-dimensional aspects. Reading , 9-12 November 1992 .
Search in Google Scholar Back to article
Derber , J. C . 1989 . A variational continuous assimilation technique. Mon . Wea. Re v . 117 , 2437 – 2446 .
Search in Google Scholar Back to article
DiMego , G. J . 1988 . The National Meteorological Center Regional Analysis System. Mon . Wea. Re v . 116 , 977 – 1000 .
Search in Google Scholar Back to article
Fletcher , R . 1972 . Conjugate gradient methods for unconstrained optimization, ed . W. Murray , Academic Press , 144 pp.
Search in Google Scholar Back to article
Forsythe , G. E. and Strauss , E. G . 1955 . On best condi-tioned matrices . Proceedings of the Amer. Math. Soc . 6 , 340 – 345 .
Search in Google Scholar Back to article
Gill , P. E. , Murray , W. and Wright , M. H . 1981 . Practical optimization . Academic Press , London , 401 pp.
Search in Google Scholar Back to article
Golub , G. H. and Van Loan , C. F . 1989 . Matrix computations . The John Hopkins University Press , Baltimore and London , 642 pp.
Search in Google Scholar Back to article
Hoffman , R. N . 1986 . A four-dimensional analysis exactly satisfying equations of motion. Mon . Wea. Re v . 114 , 388 – 397 .
Search in Google Scholar Back to article
Hoffman , K. and Kunze , R . 1971 . Linear algebra . Prentice-Hall Inc ., Second Edition , 406 pp.
Search in Google Scholar Back to article
Janjic , Z. I . 1990 . The step-mountain coordinate: Physical package. Mon . Wea. Re v . 118 , 1429 – 1443 .
Search in Google Scholar Back to article
Liu , D. C. and Nocedal , J . 1989 . On the limited memory BFGS method for large scale optimization . Math. Program . 45 , 503 – 528 .
Search in Google Scholar Back to article
Lorenc , A . 1986 . Analysis methods for numerical weather prediction . Quart. J. R. Met. Soc . 112 , 1177 – 1194 .
Search in Google Scholar Back to article
Luenberger , D. L . 1984 . Linear and non-linear pro-gramming . Addison-Wesley , 2nd edition , 491 pp.
Search in Google Scholar Back to article
Mesinger , F. , Janjic , Z. I. , Nickovic , S. , Gavrilov , D. and Deaven , D . 1988 . The step mountain coordinate: model description and performance for cases of Alpine lee cyclogenesis and for a case of an Appalachian redevelopment. Mon . Wea. Re v . 116 , 1493 – 1518 .
Search in Google Scholar Back to article
Nash , S. G . 1985 . Preconditioning of truncated-Newton methods . SIAM J. Sci. Stat. Comput . 6 , 599 – 616 .
Search in Google Scholar Back to article
Navon , I. M. and de Villiers , R . 1983 . Combined penalty muliplier optimization methods to enforce integral invariant conservation. Mon . Wea. Re v . 111 , 1228 – 1243 .
Search in Google Scholar Back to article
Navon , I. M. and Legler , D. M . 1987 . Conjugate-gradient methods for large scale minimization in meteorology. Mon . Wea. Re v . 115 , 1479 – 1502 .
Search in Google Scholar Back to article
Navon , I. M. , Zou , X. , Derber , J. C. and Sela , J . 1992 . Variational data assimilation with an adiabatic version of the NMC spectral model. Mon . Wea. Re v . 120 , 1433 – 1446 .
Search in Google Scholar Back to article
Nocedal , J . 1980 . Updating quasi-Newton matrices with limited storage . Math. of Computation 35 , 773 – 782 .
Search in Google Scholar Back to article
Rabier , F. and Courtier , P . 1992 . Four-dimensional assimilation in the presence of baroclinic instability . Q. J. Roy. Meteor. Soc . 118 , 649 – 672 .
Search in Google Scholar Back to article
Shanno , D. F . 1978 . Conjugate gradient methods with inexact line searches . Math. Operations Res . 3 , 244 – 256 .
Search in Google Scholar Back to article
Shanno , D. F . 1985 . Globally convergent conjugate gradient algorithms. Math. Program . 33 , 61 - 67 .
Search in Google Scholar Back to article
Thacker , W. C . 1989 . The role of the Hessian matrix in fitting models to measurements . J. Geophys. Res . 94 , C5 , 6177 – 6196 .
Search in Google Scholar Back to article
Thepaut , J.-N. and Courtier , P . 1991 . Four-dimensional variational data assimilation using the adjoint of a multilevel primitive equation model . Quart. J. R. Met. Soc . 117 , 1225 – 1254 .
Search in Google Scholar Back to article
Thepaut , J.-N. , Vasiljevic , D. , Courtier , P. and Pailleux , J . 1993 . Variational assimilation of conventional meteorological observations with a multilevel primitive equation model . Quart. J. R. Met. Soc . 119 , 153 – 186 .
Search in Google Scholar Back to article
Wang , Z. and Navon , I. M . 1992 . The adjoint truncated Newton algorithm for large-scale unconstrained optimization . Report FSU-SCRI-92-170, The Florida State University, Tallahassee , Florida , USA .
Search in Google Scholar Back to article
Wang , Z. , Navon , I. M. , Le Dimet , F. X. and Zou , X . 1993 . The second order adjoint analysis: theory and applications . J. Atmos. Phys ., in press .
Search in Google Scholar Back to article
Zupanski , M . 1993 . Regional four-dimensional varia-tional data assimilation in a quasi-operational forecasting environment. Mon . Wea. Re v . 121 , 2396 – 2408 .
Search in Google Scholar Back to article