Error estimates for second order Hamilton-Jacobi-Bellman equations.Approximation of probabilistic reachable sets

Mohamed Assellaou; Olivier Bokanowski; Hasnaa Zidani

doi:10.3934/dcds.2015.35.3933

Article Contents

2015, Volume 35, Issue 9: 3933-3964. Doi: 10.3934/dcds.2015.35.3933

This issue Previous Article Ergodicity conditions for zero-sum games Next Article Large deviations for some fast stochastic volatility models by viscosity methods

Error estimates for second order Hamilton-Jacobi-Bellman equations. Approximation of probabilistic reachable sets

1.
Unité des mathématiques appliquées (UMA), ENSTA ParisTech, 828 Bd Maréchaux, 91120 Palaiseau
2.
Laboratoire Jacques-Louis Lions, UMR 7598, Université Paris-Diderot (Paris 7), UFR de Mathématiques - 5 rue Thomas Mann, 75205 Paris CEDEX 13

Received: May 2014

Revised: November 2014

Published: May 2017

Abstract / Introduction Related Papers Cited by

Abstract

This work deals with numerical approximations of unbounded and discontinuous value functions associated to some stochastic control problems. We derive error estimates for monotone schemes based on a Semi-Lagrangian method (or more generally in the form of a Markov chain approximation). A motivation of this study consists in approximating chance-constrained reachability sets. The latters will be characterized as level sets of a discontinuous value function associated to an adequate stochastic control problem. A precise analysis of the level-set approach is carried out and some numerical simulations are given to illustrate the approach.

Keywords:

Error estimates for HJB equations,
numerical approximation,
unbounded and discontinuous value function,
chance constraints,
level-set approach,
stochastic reachability analysis.

Mathematics Subject Classification: Primary: 65M15, 93E20; Secondary: 49L25.

Citation:

Related Papers

Cited by

References

[1]	A. Abate, S. Amin, M. Prandini, J. Lygeros and S. Sastry, Computational approaches to reachability analysis of stochastic hybrid systems, Hybrid Systems, 4416 (2007), 4-17.doi: 10.1007/978-3-540-71493-4_4.
[2]	A. Abate, M. Prandini, J. Lygeros and S. Sastry, Probabilistic reachability and safety for controlled discrete time stochastic hybrid systems, Automatica, 44 (2008), 2724-2734.doi: 10.1016/j.automatica.2008.03.027.
[3]	M. Althoff, O. Stursberg and M. Buss, Safety assessement of autonomous cars using verification techniques, American Control Conference, (2007), 4154-4159.doi: 10.1109/ACC.2007.4282809.
[4]	M. Althoff, O. Stursberg and M. Buss, Safety assessement for stochastic linear systems using enclosing hulls of probability density functions, European Control Conference, 625-630.
[5]	S. Amin, A. Abate, M. Prandini, S. Sastry and J. Lygeros, Reachability analysis for controlled discrete time stochastic hybrid systems, in Lecture Notes in Computer Science LNCS, 3927 (2006), 49-63.doi: 10.1007/11730637_7.
[6]	G. Barles and E. R. Jakobsen, On the convergence rate of approximation schemes for Hamilton-Jacobi-Bellman equations, ESAIM:M2AN, 36 (2002), 33-54.doi: 10.1051/m2an:2002002.
[7]	G. Barles and E. R. Jakobsen, Error bounds for monotone approximation schemes for Hamilton-Jacobi-Bellman equations, SIAM J. Numer. Anal., 43 (2005), 540-558.doi: 10.1137/S003614290343815X.
[8]	G. Barles and E. R. Jakobsen, Error bounds for monotone approximation schemes for parabolic Hamilton-Jacobi-Bellman equations, Mathematics of Computations, 76 (2007), 1861-1893.doi: 10.1090/S0025-5718-07-02000-5.
[9]	I. H. Biswas, E. R. Jakobsen and K. H. Karlsen, Difference quadrature schemes for nonlinear degenerate parabolic integro-pde, SIAM J. Numer. Anal., 48 (2010), 1110-1135.doi: 10.1137/090761501.
[10]	I. H. Biswas, E. R. Jakobsen and K. H. Karlsen, Viscosity solutions for a system of integro-pdes and connections to optimal switching and control of jump-diffusion processes, Applied mathematics and optimization, 62 (2010), 47-80.doi: 10.1007/s00245-009-9095-8.
[11]	O. Bokanowski, N. Forcadel and H. Zidani, Reachability and minimal times for state constrained nonlinear problems without any controllability assumption, SIAM J. Control and Optimization. Doi: 10.1137/090762075, 48 (2010), 4292-4316.doi: 10.1137/090762075.
[12]	O. Bokanowski, A. Picarelli and H. Zidani, Dynamic programming and error estimates for stochastic control problems with maximum cost, Applied Math. and Optimization, 71 (2015), 125-163.doi: 10.1007/s00245-014-9255-3.
[13]	J. Bonnans, S. Maroso and H. Zidani, Error bounds for stochastic differential games: The adverse stopping case, IMA, J. Numer. Anal., 26 (2006), 188-212.doi: 10.1093/imanum/dri034.
[14]	J. Bonnans, S. Maroso and H. Zidani, Error estimates for a stochastic impulse control problem, Applied. Math. and Optimisation, 55 (2007), 327-357.doi: 10.1007/s00245-006-0865-2.
[15]	B. Bouchard, R. Elie and N. Touzi, Stochastic target problems with controlled loss, SIAM, 48 (2008), 3123-3150.doi: 10.1137/08073593X.
[16]	A. Briani, F. Camilli and H. Zidani, Approximation schemes for monotone systems of nonlinear second order partial differential equations: convergence result and error estimate, Differential Equations and Applications, 4 (2012), 297-317.doi: 10.7153/dea-04-18.
[17]	L. Caffarelli and P. E. Souganidis, A rate of convergence for monotone finite difference approximations to fully nonlinear uniformly elliptic pde, Comm. Pure Appl. Math., 61 (2008), 1-17.doi: 10.1002/cpa.20208.
[18]	F. Camilli and E. R. Jakobsen, A finite element like scheme for integro-partial differential Hamilton-Jacobi-Bellman equations, SIAM J. Numer. Anal., 47 (2009), 2407-2431.doi: 10.1137/080723144.
[19]	F. Camilli and M. Falcone, An approximation scheme for the optimal control of diffusion processes, RAIRO Modél. Math. Anal. Numér., 29 (1995), 97-122.
[20]	F. Da Lio and O. Ley, Uniqueness results for convex Hamilton-Jacobi equations under $p>1$ growth conditions on data, Applied Math. and Optimization, 63 (2011), 309-339.
[21]	K. Debrabant and E. R. Jakobsen, Semi-Lagrangian schemes for linear and fully non-linear diffusion equations, Mathematics of Computations, 82 (2013), 1433-1462.doi: 10.1090/S0025-5718-2012-02632-9.
[22]	F. Delarue and S. Menozzi, Density estimates for a random noise propagating through a chain of differential equations, J. Funct. Anal., 259 (2010), 1577-1630.doi: 10.1016/j.jfa.2010.05.002.
[23]	W. H. Fleming and M. H. Soner, Controlled Markov Processes and Viscosity Solutions, vol. 25 of Stochastic Modelling and Applied Probability, 2nd edition, Springer, New York, 2006.
[24]	H. Föllmer and P. Leukert, Quantile hedging, SIAM, 3 (1999), 251-273.doi: 10.1007/s007800050062.
[25]	D. Goreac and O.-S. Serea, Mayer and optimal stopping stochastic control problems with discontinuous cost, J. Math. Anal. Appl., 380 (2011), 327-342.doi: 10.1016/j.jmaa.2011.02.039.
[26]	N. V. Krylov, Mean value theorems for stochastic integrals, Ann. Probab., 29 (2001), 385-410.doi: 10.1214/aop/1008956335.
[27]	N. Krylov, On the rate of convergence of finite difference approximation for Bellman's equation, St. Petersburg Math. J., 9 (1998), 639-650.
[28]	N. Krylov, On the rate of convergence of finite-difference approximations for Bellman's equations with variable coefficients, Probability Theory and Related Fields, 117 (2000), 1-16.doi: 10.1007/s004400050264.
[29]	N. Krylov, On the rate of convergence for finite-difference approximations for bellman equations with lipschitz coefficients, Applied Mathematics and Optimization, 52 (2005), 365-399.doi: 10.1007/s00245-005-0832-3.
[30]	H. Kushner and P. Dupuis, Numerical Methods for Stochastic Control Problems in Continuous Time, vol. 24 of Applications of mathematics, Springer, New York, 2001, Second edition.doi: 10.1007/978-1-4613-0007-6.
[31]	I. Mitchell, A. Bayen and C. Tomlin, A time-dependent Hamiliton-Jacobi formulation of reachable sets for continuous dynamic games, IEEE Transactions on automatic control, 50 (2005), 947-957.doi: 10.1109/TAC.2005.851439.
[32]	R. Munos and H. Zidani, Consistency of a simple multidimensional scheme for hjb equations, C. R. Acad. Sci. Paris, Ser. I, 340 (2005), 499-502.doi: 10.1016/j.crma.2005.02.001.
[33]	S. Osher and J. A. Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys., 79 (1988), 12-49.doi: 10.1016/0021-9991(88)90002-2.
[34]	R. Rubinstein and D. Kroese, Simulation and the Monte Carlo Method, Wiley, 2008, Second edition.
[35]	J. Yong and X. Y. Zhou, Stochastic Controls: Hamiltonian Systems and HJB Equations, Stochastic Modelling and Applied Probability, Springer, Paris, 1999.doi: 10.1007/978-1-4612-1466-3.