Convergence rates of symplectic Pontryagin approximations in optimal control theory
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 40 (2006) no. 1, p. 149-173

Many inverse problems for differential equations can be formulated as optimal control problems. It is well known that inverse problems often need to be regularized to obtain good approximations. This work presents a systematic method to regularize and to establish error estimates for approximations to some control problems in high dimension, based on symplectic approximation of the hamiltonian system for the control problem. In particular the work derives error estimates and constructs regularizations for numerical approximations to optimally controlled ordinary differential equations in ${\Re }^{d}$, with non smooth control. Though optimal controls in general become non smooth, viscosity solutions to the corresponding Hamilton-Jacobi-Bellman equation provide good theoretical foundation, but poor computational efficiency in high dimensions. The computational method here uses the adjoint variable and works efficiently also for high dimensional problems with $d\gg 1$. Controls can be discontinuous due to a lack of regularity in the hamiltonian or due to colliding backward paths, i.e. shocks. The error analysis, for both these cases, is based on consistency with the Hamilton-Jacobi-Bellman equation, in the viscosity solution sense, and a discrete Pontryagin principle: the bi-characteristic hamiltonian ODE system is solved with a ${𝒞}^{2}$ approximate hamiltonian. The error analysis leads to estimates useful also in high dimensions since the bounds depend on the Lipschitz norms of the hamiltonian and the gradient of the value function but not on $d$ explicitly. Applications to inverse implied volatility estimation, in mathematical finance, and to a topology optimization problem are presented. An advantage with the Pontryagin based method is that the Newton method can be applied to efficiently solve the discrete nonlinear hamiltonian system, with a sparse jacobian that can be calculated explicitly.

DOI : https://doi.org/10.1051/m2an:2006002
Classification:  49M29,  49L25
Keywords: optimal control, Hamilton-Jacobi, hamiltonian system, Pontryagin principle
@article{M2AN_2006__40_1_149_0,
author = {Sandberg, Mattias and Szepessy, Anders},
title = {Convergence rates of symplectic Pontryagin approximations in optimal control theory},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
publisher = {EDP-Sciences},
volume = {40},
number = {1},
year = {2006},
pages = {149-173},
doi = {10.1051/m2an:2006002},
zbl = {1091.49027},
mrnumber = {2223508},
language = {en},
url = {http://www.numdam.org/item/M2AN_2006__40_1_149_0}
}

Sandberg, Mattias; Szepessy, Anders. Convergence rates of symplectic Pontryagin approximations in optimal control theory. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 40 (2006) no. 1, pp. 149-173. doi : 10.1051/m2an:2006002. http://www.numdam.org/item/M2AN_2006__40_1_149_0/

[1] Y. Achdou and O. Pironneau, Volatility smile by multilevel least square. Int. J. Theor. Appl. Finance 5 (2002) 619-643. | Zbl 1107.91319

[2] G. Barles, Solutions de viscosité des équations de Hamilton-Jacobi. Springer-Verlag, Paris. Math. Appl. (Berlin) 17 (1994). | MR 1613876 | Zbl 0819.35002

[3] G. Barles and E. Jakobsen, On the convergence rate of approximation schemes for Hamilton-Jacobi-Bellman equations. ESAIM: M2AN 36 (2002) 33-54. | Numdam | Zbl 0998.65067

[4] E. Barron and R. Jensen, The Pontryagin maximum principle from dynamic programming and viscosity solutions to first-order partial differential equations. Trans. Amer. Math. Soc. 298 (1986) 635-641. | Zbl 0618.49011

[5] M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, with appendices by M. Falcone and P. Soravia, Systems and Control: Foundations and Applications. Birkhäuser Boston, Inc., Boston, MA (1997). | MR 1484411 | Zbl 0890.49011

[6] P. Cannarsa and H. Frankowska, Some characterizations of the optimal trajectories in control theory. SIAM J. Control Optim. 29 (1991) 1322-1347. | Zbl 0744.49011

[7] P. Cannarsa, A. Mennucci and C. Sinestrari, Regularity results for solutions of a class of Hamilton-Jacobi equations. Arch. Rational Mech. Anal. 140 (1997) 197-223. | Zbl 0901.70013

[8] J. Carlsson, M. Sandberg and A. Szepessy, Symplectic Pontryagin approximations for optimal design

[9] M. Crandall and P.-L. Lions, Viscosity solutions of Hamilton-Jacobi equations. Trans. Amer. Math. Soc. 277 (1983) 1-42. | Zbl 0599.35024

[10] M. Crandall and P.-L. Lions, Two approximations of solutions of Hamilton-Jacobi equations. Math. Comp. 43 (1984) 1-19. | Zbl 0556.65076

[11] M. Crandall, L.C. Evans and P.-L. Lions, Some properties of viscosity solutions of Hamilton-Jacobi equations. Trans. Amer. Math. Soc. 282 (1984) 487-502. | Zbl 0543.35011

[12] B. Dupire, Pricing with a smile. Risk (1994) 18-20.

[13] H. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems. Kluwer Academic Publishers Group, Dordrecht. Math. Appl. 375 (1996). | MR 1408680 | Zbl 0859.65054

[14] L.C. Evans, Partial Differential Equations. Graduate Studies in Mathematics, 19. American Mathematical Society, Providence, RI (1998). | MR 1625845 | Zbl 0902.35002

[15] M. Falcone and R. Ferretti, Semi-Lagrangian schemes for Hamilton-Jacobi equations, discrete representation formulae and Godunov methods. J. Comput. Phys. 175 (2002) 559-575. | Zbl 1007.65060

[16] H. Frankowska, Contigent cones to reachable sets of control systems. SIAM J. Control Optim. 27 (1989) 170-198. | Zbl 0671.49030

[17] R. Glowinski and J.-L. Lions, Exact and approximate controllability for distributed parameter systems. Acta numerica (1994), 269-378, Acta Numer., Cambridge Univ. Press, Cambridge (1994). | Zbl 0838.93013

[18] R. Glowinski and J.-L. Lions, Exact and approximate controllability for distributed parameter systems. Acta numerica (1995), 159-333, Acta Numer., Cambridge Univ. Press, Cambridge (1995). | Zbl 0838.93014

[19] E. Harrier, C. Lubich and G. Wanner, Geometric Numerical Integrators: Structure Preserving Algorithms for Ordinary Differential Equations, Springer (2002). | MR 1904823 | Zbl 0994.65135

[20] C.-T. Lin and E. Tadmor, ${L}^{1}$-stability and error estimates for approximate Hamilton-Jacobi solutions. Numer. Math. 87 (2001) 701-735. | Zbl 0977.65059

[21] B. Mohammadi and O. Pironneau, Applied Shape Optimization for Fluids. Numerical Mathematics and Scientific Computation. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York (2001). | MR 1835648 | Zbl 0970.76003

[22] P. Pedregal, Optimization, relaxation and Young measures. Bull. Amer. Math. Soc. (N.S.) 36 (1999) 27-58. | Zbl 0916.49011

[23] E. Polak, Optimization, Algorithms and Consistent Approximations, Springer-Verlag, New York. Appl. Math. Sci. 124. (1997). | MR 1454128 | Zbl 0899.90148

[24] L.S. Pontryagin, V.G. Boltyanskii, R.V. Gamkrelidze and E.F. Mishchenko, The Mathematical Theory of Optimal Processes, Pergamon Press (1964). | MR 186436 | Zbl 0117.31702

[25] M. Sandberg, Convergence rates for Euler approximation of non convex differential inclusions, work in progress.

[26] M. Sandberg, Convergence rates for Symplectic Euler approximations of the Ginzburg-Landau equation, work in progress.

[27] P. Souganidis, Existence of viscosity solutions of Hamilton-Jacobi equations. J. Differential Equations 56 (1985) 345-390. | Zbl 0506.35020

[28] A. Subbotin, Generalized Solutions of First-Order PDEs. The Dynamical Optimization Perspective. Translated from the Russian. Systems & Control: Foundations & Applications. Birkhäuser Boston, Inc., Boston, MA (1995). | MR 1320507 | Zbl 0820.35003

[29] C. Vogel, Computational Methods for Inverse Problems. Frontiers in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (2002). | MR 1928831 | Zbl 1008.65103

[30] L.C. Young, Lectures on the Calculus of Variations and Optimal Control Theory. Saunders Co., Philadelphia-London-Toronto, Ont. (1969). | MR 259704 | Zbl 0177.37801