Abstract
In this paper we discuss the use of implicit Runge–Kutta schemes for the time discretization of optimal control problems with evolution equations. The specialty of the considered discretizations is that the discretizations schemes for the state and adjoint state are chosen such that discretization and optimization commute. It is well known that for Runge–Kutta schemes with this property additional order conditions are necessary. We give sufficient conditions for which class of schemes these additional order condition are automatically fulfilled. The focus is especially on implicit Runge–Kutta schemes of Gauss, Radau IA, Radau IIA, Lobatto IIIA, Lobatto IIIB and Lobatto IIIC collocation type up to order six. Furthermore, we also use a SDIRK (singly diagonally implicit Runge–Kutta) method to demonstrate, that for general implicit Runge–Kutta methods the additional order conditions are not automatically fulfilled. Numerical examples illustrate the predicted convergence rates.
Funding source: Deutsche Forschungsgemeinschaft
Award Identifier / Grant number: SPP 1253
Funding statement: The work was partially supported by the DFG priority program SPP 1253.
A Order Conditions
We repeat these order conditions up to order four in Table 2, the conditions of order five in Table 3 and the conditions of order six in Tables 4–7.
Table 2.
The order conditions for Runge–Kutta discretization for the state equation and optimal control problems, see also [4, Tables 2–4] and [8, Tables 1 and 2]. All summations go from 1 to the number of stages s:
Abbreviations:
Order conditions for the state equation without control:
(O1)(O2)(O3)(O4)Additional order conditions for optimal control problems:
(A3)(A4)
Table 3.
The order conditions of order five for Runge–Kutta discretization for the state equation and optimal control problems, see also [4, Table 6]. All summations go from 1 to the number of stages s:
Order conditions of order five for the state equation without control (computed with Mathematica):
(O5-1)(O5-2)(O5-3)Additional order conditions of order five for optimal control problems (see also [4, Table 6]):
(A5-1)(A5-2)(A5-3)(A5-4)(A5-5)(A5-6)(A5-7)
Table 4.
The order conditions of order six for Runge–Kutta discretization for the state equation without control (computed with Mathematica). All summations go from 1 to the number of stages s:
Table 5.
Part 1 of the additional order conditions of order six for Runge–Kutta discretization for optimal control problems, see also [4, Table 6]. All summations go from 1 to the number of stages s:
Table 6.
Part 2 of the additional order conditions of order six for Runge–Kutta discretization for optimal control problems, see also [4, Table 6]. All summations go from 1 to the number of stages s:
Table 7.
Part 3 of the additional order conditions of order six for Runge–Kutta discretization for optimal control problems, see also [4, Table 6]. All summations go from 1 to the number of stages s:
B Coefficients of Runge–Kutta Schemes
We repeat the Butcher tableaux for selected Runge–Kutta schemes of order two and three in Table 8 a, order four in Table 9, order five in Table 10 and order six in Table 11.
Table 8.
Coefficients of Runge–Kutta schemes of order two and three (see also [9, 10, 11]).
Coefficients of the Störmer–Verlet discretization for the state (cf. [9, Table 2.1]):
Coefficients for the Radau IA method of order three (cf. [11, Table IV.5.3.]):
Coefficients for the Radau IIA method of order three (cf. [11, Table IV.5.5.]):
Table 9.
Coefficients of Runge–Kutta schemes of order four (see also [9, 10, 11]).
Coefficients for an L-stable SDIRK method of order four (cf. [11, Formula (6.16)]):
Coefficients for the Lobatto IIIA method of order four (cf. [11, Table IV.5.7.]):
Coefficients for the Lobatto IIIB method of order four (cf. [11, Table IV.5.9.]):
Coefficients for the Lobatto IIIC method of order four (cf. [11, Table IV.5.11.]):
Table 10.
Coefficients of Runge–Kutta schemes of order five (see also [9, 10, 11]).
Coefficients for the Radau IA method of order five (cf. [11, Table IV.5.3.]):
Coefficients for the Radau IIA method of order five (cf. [11, Table IV.5.5.]):
Table 11.
Coefficients of Runge–Kutta schemes of order six (see also [9, 10, 11]).
Coefficients for the Gauss scheme of order six (cf. [11, Table IV.5.2.]):
Coefficients for the Lobatto IIIC method of order six(cf. [11, Table IV.5.11.]):
Coefficients for the Lobatto IIIA method of order six (cf. [11, Table IV.5.7.]):
Coefficients for the Lobatto IIIB method of order six (cf. [11, Table IV.5.9.]):
C Proof of Theorem 3.7
Full proof of Theorem 3.7.
The idea of the proof is to use the simplifying assumptions (B${(p)}$), ((C${(\eta)}$)), ((D${(\zeta)}$)) to reduce the additional order conditions to the classic order conditions or order conditions of lower order, which have already been reduced to the order conditions of the uncontrolled system. As all the numerical schemes fulfill the order conditions for the uncontrolled systems, these conditions can be used to calculate the value of the reduced expression.
Surely the way of the application of the simplifying assumptions is not unique, here one possibility is presented.
A first goal in the reduction of order conditions with a fraction
For the first additional order condition of (A5-1) we use the simplifying assumption ((D${(\zeta)}$)) for
For the second additional order condition of (A5-1) we use the simplifying assumption ((D${(\zeta)}$)) for
For the last order condition of (A5-1) we use again the simplifying assumption ((D${(\zeta)}$)) for
For the first condition of (A5-2) we apply the simplifying assumption ((D${(\zeta)}$)) for
For the second condition of (A5-2) we use the simplifying assumption ((D${(\zeta)}$)) for
For the third condition of (A5-2) we apply the simplifying assumption ((C${(\eta)}$)) for
For the first condition of (A5-3) we apply again the simplifying assumption ((C${(\eta)}$)) for
For the second condition of (A5-3) we apply first the simplifying assumptions ((D${(\zeta)}$)) for
For the last condition of (A5-3) we apply the simplifying assumption ((D${(\zeta)}$)) for
For the first condition of (A5-4) we use the simplifying assumption ((D${(\zeta)}$)) for
For the second condition of (A5-4) we use again the simplifying assumptions ((D${(\zeta)}$)) for
For the last condition of (A5-4) we use first the simplifying assumptions ((D${(\zeta)}$)) for
(C.1)The last term is the third condition of (A5-3) and therefore we already know how to tread this term. On the first term of (C.1) we apply the simplifying assumptions ((D${(\zeta)}$)) for
For the remaining term of (C.1) the use of ((D${(\zeta)}$)) for
Altogether we have
For the first condition of (A5-5) we start with the use of the simplifying assumption ((D${(\zeta)}$)) for
For the second condition of (A5-5) the use of ((D${(\zeta)}$)) for
For the last condition of (A5-5) we apply the simplifying assumption ((D${(\zeta)}$)) for
For the first condition of (A5-6) we use the simplifying assumption ((D${(\zeta)}$)) for
To the second condition of (A5-6) we apply the simplifying assumption ((D${(\zeta)}$)) for
The application of the simplifying assumption ((D${(\zeta)}$)) for
For the condition (A5-7) we use the simplifying assumption ((D${(\zeta)}$)) for
Altogether we have derived the additional order conditions with the use of the simplifying assumptions
and (B${(p)}$) for
D Proof of Theorem 3.9
Full proof of Theorem 3.9.
We follow the same ideas as in Appendix C. Note that the simplifying condition (B${(p)}$) up to order
For the first additional order condition of (A6-1) we use the definition of
For the second order condition of (A6-1) we use the definition of
For the third condition of (A6-1) we use the definition of
For the first condition of (A6-2) we use the definition of
For the second condition of (A6-2) we use the definition of
For the third condition of (A6-2) we use the definition of
For the first condition of (A6-3) we use the definition of
For the second condition of (A6-3) we use the definition of
For the third condition of (A6-3) we use the definition of
For the first condition of (A6-4) we use ((D${(\zeta)}$)) for
For the second condition of (A6-4) we use ((D${(\zeta)}$)) for
For the third condition of (A6-4) we use ((D${(\zeta)}$)) for
For the first condition of (A6-5) we use ((D${(\zeta)}$)) for
For the second condition of (A6-5) we use ((D${(\zeta)}$)) for
For the third condition of (A6-5) we use ((D${(\zeta)}$)) for
Instead of ((C${(\eta)}$)) for
For the first condition of (A6-6) we use ((D${(\zeta)}$)) for
For the second condition of (A6-6) we use ((D${(\zeta)}$)) for
For the third condition of (A6-6) we use ((D${(\zeta)}$)) for
For the first condition of (A6-7) we use ((D${(\zeta)}$)) for
For the second condition of (A6-7) we use ((D${(\zeta)}$)) for
For the third condition of (A6-7) we use ((D${(\zeta)}$)) for
For the first condition of (A6-8) we use ((D${(\zeta)}$)) for
For the second condition of (A6-8) we use ((D${(\zeta)}$)) for
As we have no additional
For the second sum we use ((D${(\zeta)}$)) for
Together we have shown
For the third condition of (A6-8) we use ((D${(\zeta)}$)) for
For the first condition of (A6-9) we use ((D${(\zeta)}$)) for
For the second condition of (A6-9) we use ((D${(\zeta)}$)) for
For the third condition of (A6-9) we use ((D${(\zeta)}$)) for
For the first condition of (A6-10) we use ((D${(\zeta)}$)) for
For the second condition of (A6-10) we use ((D${(\zeta)}$)) for
For the third condition of (A6-10) we use ((D${(\zeta)}$)) for
For the first condition of (A6-11) we use ((D${(\zeta)}$)) for
For the second condition of (A6-11) we use ((D${(\zeta)}$)) for
For the third condition of (A6-11) we use ((D${(\zeta)}$)) for
For the first condition of (A6-12) we use ((D${(\zeta)}$)) for
For the second condition of (A6-12) we use ((D${(\zeta)}$)) for
For the third condition of (A6-12), we use ((C${(\eta)}$)) for
For the first condition of (A6-13), we use ((D${(\zeta)}$)) for
For the second condition of (A6-13), we use ((D${(\zeta)}$)) for
For the third condition of (A6-13), we use ((D${(\zeta)}$)) for
For the first condition of (A6-14), we use ((D${(\zeta)}$)) for
For the second condition of (A6-14), we use ((C${(\eta)}$)) for
For the last condition of (A6-14), we use ((D${(\zeta)}$)) for
For the first condition of (A6-15) we use ((D${(\zeta)}$)) for
(D.1)For the first term we use ((D${(\zeta)}$)) for
For the second term of (D.1), we use ((D${(\zeta)}$)) for
Altogether we have
For the second condition of (A6-15), we use ((D${(\zeta)}$)) for
For the last condition of (A6-15), we use ((D${(\zeta)}$)) for
For the first condition of (A6-16) we use ((D${(\zeta)}$)) for
For the second condition of (A6-16) we use ((D${(\zeta)}$)) for
For the last condition of (A6-16) we use ((D${(\zeta)}$)) for
For the first condition of (A6-17) we use ((D${(\zeta)}$)) for
For the second condition of (A6-17) we use ((D${(\zeta)}$)) for
For the last condition of (A6-17) we use ((D${(\zeta)}$)) for
For the first condition of (A6-18) we use ((D${(\zeta)}$)) for
For the second condition of (A6-18) we use ((D${(\zeta)}$)) for
For the third condition of (A6-18) we use ((D${(\zeta)}$)) for
For the first condition of (A6-19) we use ((D${(\zeta)}$)) for
For the second condition of (A6-19) we use ((D${(\zeta)}$)) for
For the third condition of (A6-19) we use ((D${(\zeta)}$)) for
For the first condition of (A6-20) we use ((D${(\zeta)}$)) for
For the second condition of (A6-20) we use ((D${(\zeta)}$)) for
For the last condition of (A6-20) we use ((D${(\zeta)}$)) for
For the first condition of (A6-21) we use ((D${(\zeta)}$)) for
For the second condition of (A6-21) we use ((D${(\zeta)}$)) for
For the first condition of (A6-22) we use ((D${(\zeta)}$)) for
For the second condition of (A6-22) we use ((D${(\zeta)}$)) for
For the first condition of (A6-23) we use ((D${(\zeta)}$)) for
For the second condition of (A6-23) we use ((D${(\zeta)}$)) for
For the first condition of (A6-24) we use ((D${(\zeta)}$)) for
For the second condition of (A6-24) we use ((D${(\zeta)}$)) for
For the first condition of (A6-25) we use ((D${(\zeta)}$)) for
For the second condition of (A6-25) we use ((D${(\zeta)}$)) for
For the first condition of (A6-26) we use ((D${(\zeta)}$)) for
For the second condition of (A6-26) we use ((C${(\eta)}$)) for
For the condition (A6-27) we use ((D${(\zeta)}$)) for
Altogether we have derived the additional order conditions with the use of the simplifying assumptions
and (B${(p)}$) for
References
[1] T. Apel and T. G. Flaig, Crank–Nicolson schemes for optimal control problems with evolution equations, SIAM J. Numer. Anal. 50 (2012), no. 3, 1484–1512. 10.1137/100819333Search in Google Scholar
[2] R. Becker, D. Meidner and B. Vexler, Efficient numerical solution of parabolic optimization problems by finite element methods, Optim. Methods Softw. 22 (2007), no. 5, 813–833. 10.1080/10556780701228532Search in Google Scholar
[3] J. F. Bonnans and J. Laurent-Varin, Computation of order conditions for symplectic partitioned Runge–Kutta schemes with application to optimal control, Rapport de recherche RR–5398 2004, http://hal.inria.fr/docs/00/07/06/05/PDF/RR-5398.pdf. Search in Google Scholar
[4] J. F. Bonnans and J. Laurent-Varin, Computation of order conditions for symplectic partitioned Runge–Kutta schemes with application to optimal control, Numer. Math. 103 (2006), no. 1, 1–10. 10.1007/s00211-005-0661-ySearch in Google Scholar
[5] T. Dupont and R. Scott, Polynomial approximation of functions in Sobolev spaces, Math. Comp. 34 (1980), no. 150, 441–463. 10.1090/S0025-5718-1980-0559195-7Search in Google Scholar
[6] T. G. Flaig, Discretization strategies for optimal control problems with parabolic partial differential equations, PhD thesis, Universität der Bundeswehr München, 2013. Search in Google Scholar
[7] W. W. Hager, Rates of convergence for discrete approximations to unconstrained control problems, SIAM J. Numer. Anal. 13 (1976), no. 4, 449–472. 10.1137/0713040Search in Google Scholar
[8] W. W. Hager, Runge–Kutta methods in optimal control and the transformed adjoint system, Numer. Math. 87 (2000), no. 2, 247–282. 10.1007/s002110000178Search in Google Scholar
[9] E. Hairer, C. Lubich and G. Wanner, Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations, 2nd ed., Springer Ser. Comput. Math. 31, Springer, Berlin, 2006. Search in Google Scholar
[10] E. Hairer, S. P. Nørsett and G. Wanner, Solving Ordinary Differential Equations. I. Nonstiff Problems, Springer Ser. Comput. Math. 8, Springer, Berlin, 1987. 10.1007/978-3-662-12607-3Search in Google Scholar
[11] E. Hairer and G. Wanner, Solving Ordinary Differential Equations. II. Stiff and Differential-Algebraic Problems, 2nd ed., Springer Ser. Comput. Math. 14, Springer, Berlin, 1996. 10.1007/978-3-642-05221-7_1Search in Google Scholar
[12] M. Herty, L. Pareschi and S. Steffensen, Implicit-explicit Runge-Kutta schemes for numerical discretization of optimal control problems, SIAM J. Numer. Anal. 51 (2013), no. 4, 1875–1899. 10.1137/120865045Search in Google Scholar
[13] L. S. Hou, O. Imanuvilov and H.-D. Kwon, Eigen series solutions to terminal-state tracking optimal control problems and exact controllability problems constrained by linear parabolic PDEs, J. Math. Anal. Appl. 313 (2006), no. 1, 284–310. 10.1016/j.jmaa.2005.02.067Search in Google Scholar
[14] J. Lang and J. G. Verwer, W-methods in optimal control, Numer. Math. 124 (2013), no. 2, 337–360. 10.1007/s00211-013-0516-xSearch in Google Scholar
[15] P. Lasaint and P.-A. Raviart, On a finite element method for solving the neutron transport equation, Mathematical Aspects of Finite Elements in Partial Differential Equations, Academic Press, New York (1974), 89–123. 10.1016/B978-0-12-208350-1.50008-XSearch in Google Scholar
[16] J.-L. Lions, Optimal Control of Systems Governed by Partial Differential Equations, Grundlehren Math. Wiss. 170, Springer, New York, 1971. 10.1007/978-3-642-65024-6Search in Google Scholar
[17] D. Meidner and B. Vexler, A priori error estimates for space-time finite element discretization of parabolic optimal control problems. I. Problems without control constraints, SIAM J. Control Optim. 47 (2008), no. 3, 1150–1177. 10.1137/070694016Search in Google Scholar
[18] D. Meidner and B. Vexler, A priori error analysis of the Petrov–Galerkin Crank–Nicolson scheme for parabolic optimal control problems, SIAM J. Control Optim. 49 (2011), no. 5, 2183–2211. 10.1137/100809611Search in Google Scholar
[19] A. Rösch, Error estimates for parabolic optimal control problems with control constraints, Z. Anal. Anwend. 23 (2004), no. 2, 353–376. 10.4171/ZAA/1203Search in Google Scholar
[20] S. Steffensen, M. Herty and L. Pareschi, Numerical methods for the optimal control of scalar conservation laws, System Modeling and Optimization, IFIP Adv. Inf. Commun. Technol. 391, Springer, Heidelberg (2013), 136–144. 10.1007/978-3-642-36062-6_14Search in Google Scholar
[21] F. Tröltzsch, Optimale Steuerung partieller Differentialgleichungen - Theorie, Verfahren und Anwendungen, Vieweg, Wiesbaden, 2005. 10.1007/978-3-322-96844-9Search in Google Scholar
© 2023 Walter de Gruyter GmbH, Berlin/Boston