Solving parameter estimation problems with discrete adjoint exponential integrators. (English) Zbl 1401.49050

Summary: The solution of inverse problems in a variational setting finds best estimates of the model parameters by minimizing a cost function that penalizes the mismatch between model outputs and observations. The gradients required by the numerical optimization process are computed using adjoint models. Exponential integrators are a promising family of time discretization schemes for evolutionary partial differential equations. In order to allow the use of these discretization schemes in the context of inverse problems, adjoints of exponential integrators are required. This work derives the discrete adjoint formulae for W-type exponential propagation iterative methods of Runge-Kutta type (EPIRK-W). These methods allow arbitrary approximations of the Jacobian while maintaining the overall accuracy of the forward integration. The use of Jacobian approximation matrices that do not depend on the model state avoids the complex calculation of Hessians in the discrete adjoint formulae. The adjoint code itself is generated efficiently via algorithmic differentiation and used to solve inverse problems with the Lorenz-96 model and a model from computational magnetics. Numerical results are encouraging and indicate the suitability of exponential integrators for this class of problems.


49N45 Inverse problems in optimal control
49M25 Discrete approximations in optimal control
65L06 Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations
Full Text: DOI arXiv


[1] Alexe, M.; Sandu, A., forward and adjoint sensitivity analysis with continuous explicit Runge–Kutta schemes, Appl. Math. Comput., 208, 328-34, (2009) · Zbl 1159.65071
[2] Alexe, M.; Sandu, A., on the discrete adjoints of variable step time integrators, J. Comput. Appl. Math., 233, 1005-1020, (2009) · Zbl 1177.65098
[3] Alnæs, M. S.; Blechta, J.; Hake, J.; Johansson, A.; Kehlet, B.; Logg, A.; Richardson, C.; Ring, J.; Rognes, M. E.; Wells, G. N., the fenics project version 1.5, Arch. Numer. Soft., 3, 9-23, (2015)
[4] Anderson, J. L., spatially and temporally varying adaptive covariance inflation for ensemble filters, Tellus A, 61, 72-83, (2009)
[5] MATLODE: A MATLAB ODE solver and sensitivity analysis toolbox, ACM TOMS in preparation, 2018
[6] Bachinger, F.; Langer, U.; Schöberl, J., numerical analysis of nonlinear multiharmonic eddy current problems, Numer. Math., 100, 593-616, (2005) · Zbl 1122.78016
[7] Betts, J. T., Practical methods for optimal control and estimation using nonlinear programming, (2010), SIAM, Philadelphia · Zbl 1189.49001
[8] Betts, J. T.; Campbell, S. L., discretize then optimize, (2003) · Zbl 1197.49032
[9] Direct Transcription Solution of Inequality Constrained Optimal Control Problems, in American Control Conference, 2004. Proceedings of the 2004, Vol. 2, IEEE, 2004, pp. 1622–1626
[10] Bíró, O., edge element formulations of eddy current problems, Comput. Methods Appl. Mech. Eng., 169, 391-405, (1999) · Zbl 0937.78002
[11] Bonnans, J. F.; Laurent-Varin, J., computation of order conditions for symplectic partitioned Runge–Kutta schemes with application to optimal control, Numer. Math., 103, 1-10, (2006) · Zbl 1112.65063
[12] Byrd, R. H.; Lu, P.; Nocedal, J.; Zhu, C., A limited memory algorithm for bound constrained optimization, SIAM J. Sci. Comput., 16, 1190-1208, (1995) · Zbl 0836.65080
[13] High order variational integrators in the optimal control of mechanical systems, preprint (2015). Available at arXiv:1502.00325
[14] Cheng, H.; Jardak, M.; Alexe, M.; Sandu, A., A hybrid approach to estimating error covariances in variational data assimilation, Tellus A, 62, 288-297, (2010)
[15] Adjoint implementation of Rosenbrock methods applied to variational data assimilation, in Air Pollution Modeling and its Application XIV, S. Gryning and F. Schiermeier, eds., Springer, 2000, pp. 361–369. Available at
[16] Daescu, D.; Carmichael, G.; Sandu, A., adjoint implementation of rosenbrock methods applied to variational data assimilation problems, J. Comput. Phys., 165, 496-510, (2000) · Zbl 1043.76051
[17] Daescu, D.; Sandu, A.; Carmichael, G., direct and adjoint sensitivity analysis of chemical kinetic systems with KPP: II – numerical validation and applications, Atmos. Environ., 37, 5097-5114, (2003)
[18] Fertig, E. J.; Harlim, J.; Hunt, B. R., A comparative study of 4D-VAR and a 4D ensemble Kalman filter: perfect model simulations with Lorenz-96, Tellus A: Dynamic Meteorology and Oceanography, 59, 96-100, (2007)
[19] Geuzaine, C.; Remacle, J. F., gmsh: A 3-D finite element mesh generator with built-in pre-and post-processing facilities, Int. J. Numer. Methods Eng., 79, 1309-1331, (2009) · Zbl 1176.74181
[20] Gou, T.; Sandu, A., continuous versus discrete advection adjoints in chemical data assimilation with CMAQ, Atmos. Environ., 45, 4868-4881, (2011)
[21] Griewank, A.; Walther, A., algorithm 799: revolve: an implementation of checkpointing for the reverse or adjoint mode of computational differentiation, ACM Trans. Math. Softw., 26, 19-45, (2000) · Zbl 1137.65330
[22] Griewank, A.; Walther, A., Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, (2008), SIAM, Philadelphia · Zbl 1159.65026
[23] Hager, W. W., Runge–Kutta methods in optimal control and the transformed adjoint system, Numer. Math., 87, 247-282, (2000) · Zbl 0991.49020
[24] Solving ordinary differential equations II: Stiff and differential-algebraic problems, 2nd ed., no. 14 in Springer Series in Computational Mathematics, Springer-Verlag, Berlin, Heidelberg, 1996 · Zbl 0859.65067
[25] Hascoët, L.; Pascual, V., the tapenade automatic differentiation tool: principles, model, and specification, ACM Trans. Math. Softw., 39, (2013) · Zbl 1295.65026
[26] Hochbruck, M.; Lubich, C., on Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 34, 1911-1925, (1997) · Zbl 0888.65032
[27] SciPy: Open source scientific tools for Python, 2001. Available at
[28] Kalnay, E., Atmospheric Modeling, Data Assimilation and Predictability, (2003), Cambridge University Press, Cambridge
[29] Lang, J.; Verwer, J. G., W-methods in optimal control, Numer. Math., 124, 337-360, (2013) · Zbl 1269.65063
[30] Lei, J.; Bickel, P., A moment matching ensemble filter for nonlinear non-Gaussian data assimilation, Mon. Weather Rev., 139, 3964-3973, (2011)
[31] Li, H.; Kalnay, E.; Miyoshi, T., simultaneous estimation of covariance inflation and observation errors within an ensemble Kalman filter, Q. J. R. Meteorol. Soc., 135, 523-533, (2009)
[32] Logg, A.; Mardal, K. A.; Wells, G. N., Automated Solution of Differential Equations by the Finite Element Method, (2012), Springer-Verlag, Berlin
[33] Predictability – a problem partly solved, in Predictability of Weather and Climate, Cambridge University Press (CUP), 1996, pp. 40–58. Available at
[34] Finite element method magnetics, version 4.0.1 (03dec2006 build). Available at
[35] Forward, Tangent Linear, and Adjoint Runge Kutta Methods in KPP-2.2, in International Conference on Computational Science (ICCS 2006), Lecture Notes in Computer Science, Vol. 3993, Reading, UK, Springer, Berlin, Heidelberg, 2006, pp. 120–127. Available at
[36] EPIRK-W and EPIRK-K time discretization methods, CoRR abs/1701.06528 (2017). Available at
[37] Naumann, U., The Art of Differentiating Computer Programs: An Introduction to Algorithmic Differentiation, (2011), SIAM, Philadelphia
[38] Neidinger, R. D., introduction to automatic differentiation and MATLAB object-oriented programming, SIAM Rev., 52, 545-563, (2010) · Zbl 1196.65048
[39] Ott, E.; Hunt, B. R.; Szunyogh, I.; Zimin, A. V.; Kostelich, E. J.; Corazza, M.; Kalnay, E.; Patil, D. J.; Yorke, J. A., A local ensemble Kalman filter for atmospheric data assimilation, Tellus A: Dynamic Meteorology and Oceanography, 56, 415-428, (2004)
[40] Peterson, P., F2py: A tool for connecting Fortran and python programs, Int. J. Comput. Sci. Eng., 4, 296-305, (2009)
[41] Rao, V.; Sandu, A., an adjoint-based scalable algorithm for time-parallel integration, J. Comput. Sci., 5, 76-84, (2014)
[42] Rao, V.; Sandu, A., A posteriori error estimates for the solution of variational inverse problems, SIAM/ASA J. Uncertain. Quant., 3, 737-761, (2015) · Zbl 1327.65135
[43] Rosseel, E.; De Gersem, H.; Vandewalle, S., nonlinear stochastic Galerkin and collocation methods: application to a ferromagnetic cylinder rotating at high speed, Commun. Comput. Phys., 8, 947-975, (2010) · Zbl 1364.74099
[44] The discrete adjoint method for exponential integration, preprint (2016). Available at arXiv:1610.02596
[45] On the properties of Runge-Kutta discrete adjoints, in Lecture Notes in Computer Science, Vol. LNCS 3994, Part IV, Springer, Berlin, Heidelberg, 2006, pp. 550–557. Available at · Zbl 1157.65421
[46] On consistency properties of discrete adjoint linear multistep methods, Tech. Rep. CS-TR-07-40, Computer Science Department, Virginia Tech, 2007. Available at
[47] Solution of inverse ODE problems using discrete adjoints, in Large Scale Inverse Problems and Quantification of Uncertainty, L. Biegler, G. Biros, O. Ghattas, M. Heinkenschloss, D. Keyes, B. Mallick, L. Tenorio, B. van Bloemen Waanders, and K. Willcox, eds., Chapter 12, John Wiley & Sons, 2010, pp. 345–364. Available at
[48] Sandu, A.; Miehe, P., forward, tangent linear, and adjoint Runge Kutta methods in KPP–2.2 for efficient chemical kinetic simulations, Int. J. Comput. Math., 87, 2458-2479, (2010) · Zbl 1202.65090
[49] Sandu, A.; Daescu, D.; Carmichael, G., direct and adjoint sensitivity analysis of chemical kinetic systems with KPP: I – theory and software tools, Atmos. Environ., 37, 5083-5096, (2003)
[50] Sandu, A.; Daescu, D.; Carmichael, G.; Chai, T., adjoint sensitivity analysis of regional air quality models, J. Comput. Phys., 204, 222-252, (2005) · Zbl 1061.92061
[51] Sanz-Serna, J. M., symplectic Runge–Kutta schemes for adjoint equations, automatic differentiation, optimal control, and more, SIAM Rev., 58, 3-33, (2016) · Zbl 1339.65243
[52] Sidje, R. B., expokit: A software package for computing matrix exponentials, ACM Trans. Math. Softw., 24, 130-156, (1998) · Zbl 0917.65063
[53] Towards the Construction of a Standard Adjoint GEOS-Chem Model, in Proceedings of the 2009 Spring Simulation Multiconference (SpringSim’09), High Performance Computing Symposium (HPC-2009), March, 2009, p. 8. Available at
[54] Singh, K.; Sandu, A.; Jardak, M.; Bowman, K. W.; Lee, M., A practical method to estimate information content in the context of 4D-VAR data assimilation, SIAM/ASA J. Uncertain. Quant., 1, 106-138, (2013) · Zbl 1283.65009
[55] Steihaug, T.; Wolfbrandt, A., an attempt to avoid Jacobian and nonlinear equations in the numerical solution of stiff differential equations, Math. Comput., 33, 521-521, (1979) · Zbl 0451.65055
[56] Tokman, M., efficient integration of large stiff systems of ODEs with exponential propagation iterative (EPI) methods, J. Comput. Phys., 213, 748-776, (2006) · Zbl 1089.65063
[57] Tokman, M., A new class of exponential propagation iterative methods of Runge–Kutta type (EPIRK), J. Comput. Phys., 230, 8762-8778, (2011) · Zbl 1370.65035
[58] Zhang, H.; Sandu, A., FATODE: A library for forward, adjoint, and tangent linear integration of ODEs, SIAM J. Sci. Comput., 36, C504-C523, (2014) · Zbl 1307.65104
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.