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

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

September 2015, 35(9): 3933-3964. doi: 10.3934/dcds.2015.35.3933

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

Mohamed Assellaou ^1, , Olivier Bokanowski ^2, and Hasnaa Zidani ^1,

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

Received May 2014 Revised November 2014 Published April 2015

Abstract
Related Papers

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: stochastic reachability analysis., numerical approximation, unbounded and discontinuous value function, level-set approach, chance constraints, Error estimates for HJB equations.

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

Citation: Mohamed Assellaou, Olivier Bokanowski, Hasnaa Zidani. Error estimates for second order Hamilton-Jacobi-Bellman equations. Approximation of probabilistic reachable sets. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 3933-3964. doi: 10.3934/dcds.2015.35.3933

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. doi: 10.1007/978-3-540-71493-4_4. Google Scholar
[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. doi: 10.1016/j.automatica.2008.03.027. Google Scholar
[3]	M. Althoff, O. Stursberg and M. Buss, Safety assessement of autonomous cars using verification techniques,, American Control Conference, (2007), 4154. doi: 10.1109/ACC.2007.4282809. Google Scholar
[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. Google Scholar
[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. doi: 10.1007/11730637_7. Google Scholar
[6]	G. Barles and E. R. Jakobsen, On the convergence rate of approximation schemes for Hamilton-Jacobi-Bellman equations,, ESAIM:M2AN, 36 (2002), 33. doi: 10.1051/m2an:2002002. Google Scholar
[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. doi: 10.1137/S003614290343815X. Google Scholar
[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. doi: 10.1090/S0025-5718-07-02000-5. Google Scholar
[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. doi: 10.1137/090761501. Google Scholar
[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. doi: 10.1007/s00245-009-9095-8. Google Scholar
[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. doi: 10.1137/090762075. Google Scholar
[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. doi: 10.1007/s00245-014-9255-3. Google Scholar
[13]	J. Bonnans, S. Maroso and H. Zidani, Error bounds for stochastic differential games: The adverse stopping case,, IMA, 26 (2006), 188. doi: 10.1093/imanum/dri034. Google Scholar
[14]	J. Bonnans, S. Maroso and H. Zidani, Error estimates for a stochastic impulse control problem,, Applied. Math. and Optimisation, 55 (2007), 327. doi: 10.1007/s00245-006-0865-2. Google Scholar
[15]	B. Bouchard, R. Elie and N. Touzi, Stochastic target problems with controlled loss,, SIAM, 48 (2008), 3123. doi: 10.1137/08073593X. Google Scholar
[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. doi: 10.7153/dea-04-18. Google Scholar
[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. doi: 10.1002/cpa.20208. Google Scholar
[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. doi: 10.1137/080723144. Google Scholar
[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. Google Scholar
[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. Google Scholar
[21]	K. Debrabant and E. R. Jakobsen, Semi-Lagrangian schemes for linear and fully non-linear diffusion equations,, Mathematics of Computations, 82 (2013), 1433. doi: 10.1090/S0025-5718-2012-02632-9. Google Scholar
[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. doi: 10.1016/j.jfa.2010.05.002. Google Scholar
[23]	W. H. Fleming and M. H. Soner, Controlled Markov Processes and Viscosity Solutions, vol. 25 of Stochastic Modelling and Applied Probability,, 2nd edition, (2006). Google Scholar
[24]	H. Föllmer and P. Leukert, Quantile hedging,, SIAM, 3 (1999), 251. doi: 10.1007/s007800050062. Google Scholar
[25]	D. Goreac and O.-S. Serea, Mayer and optimal stopping stochastic control problems with discontinuous cost,, J. Math. Anal. Appl., 380 (2011), 327. doi: 10.1016/j.jmaa.2011.02.039. Google Scholar
[26]	N. V. Krylov, Mean value theorems for stochastic integrals,, Ann. Probab., 29 (2001), 385. doi: 10.1214/aop/1008956335. Google Scholar
[27]	N. Krylov, On the rate of convergence of finite difference approximation for Bellman's equation,, St. Petersburg Math. J., 9 (1998), 639. Google Scholar
[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. doi: 10.1007/s004400050264. Google Scholar
[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. doi: 10.1007/s00245-005-0832-3. Google Scholar
[30]	H. Kushner and P. Dupuis, Numerical Methods for Stochastic Control Problems in Continuous Time, vol. 24 of Applications of mathematics,, Springer, (2001). doi: 10.1007/978-1-4613-0007-6. Google Scholar
[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. doi: 10.1109/TAC.2005.851439. Google Scholar
[32]	R. Munos and H. Zidani, Consistency of a simple multidimensional scheme for hjb equations,, C. R. Acad. Sci. Paris, 340* (2005), 499. doi: 10.1016/j.crma.2005.02.001. Google Scholar*
[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. doi: 10.1016/0021-9991(88)90002-2. Google Scholar
[34]	R. Rubinstein and D. Kroese, Simulation and the Monte Carlo Method,, Wiley, (2008). Google Scholar
[35]	J. Yong and X. Y. Zhou, Stochastic Controls: Hamiltonian Systems and HJB Equations,, Stochastic Modelling and Applied Probability, (1999). doi: 10.1007/978-1-4612-1466-3. Google Scholar

show all references

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. doi: 10.1007/978-3-540-71493-4_4. Google Scholar
[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. doi: 10.1016/j.automatica.2008.03.027. Google Scholar
[3]	M. Althoff, O. Stursberg and M. Buss, Safety assessement of autonomous cars using verification techniques,, American Control Conference, (2007), 4154. doi: 10.1109/ACC.2007.4282809. Google Scholar
[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. Google Scholar
[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. doi: 10.1007/11730637_7. Google Scholar
[6]	G. Barles and E. R. Jakobsen, On the convergence rate of approximation schemes for Hamilton-Jacobi-Bellman equations,, ESAIM:M2AN, 36 (2002), 33. doi: 10.1051/m2an:2002002. Google Scholar
[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. doi: 10.1137/S003614290343815X. Google Scholar
[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. doi: 10.1090/S0025-5718-07-02000-5. Google Scholar
[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. doi: 10.1137/090761501. Google Scholar
[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. doi: 10.1007/s00245-009-9095-8. Google Scholar
[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. doi: 10.1137/090762075. Google Scholar
[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. doi: 10.1007/s00245-014-9255-3. Google Scholar
[13]	J. Bonnans, S. Maroso and H. Zidani, Error bounds for stochastic differential games: The adverse stopping case,, IMA, 26 (2006), 188. doi: 10.1093/imanum/dri034. Google Scholar
[14]	J. Bonnans, S. Maroso and H. Zidani, Error estimates for a stochastic impulse control problem,, Applied. Math. and Optimisation, 55 (2007), 327. doi: 10.1007/s00245-006-0865-2. Google Scholar
[15]	B. Bouchard, R. Elie and N. Touzi, Stochastic target problems with controlled loss,, SIAM, 48 (2008), 3123. doi: 10.1137/08073593X. Google Scholar
[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. doi: 10.7153/dea-04-18. Google Scholar
[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. doi: 10.1002/cpa.20208. Google Scholar
[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. doi: 10.1137/080723144. Google Scholar
[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. Google Scholar
[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. Google Scholar
[21]	K. Debrabant and E. R. Jakobsen, Semi-Lagrangian schemes for linear and fully non-linear diffusion equations,, Mathematics of Computations, 82 (2013), 1433. doi: 10.1090/S0025-5718-2012-02632-9. Google Scholar
[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. doi: 10.1016/j.jfa.2010.05.002. Google Scholar
[23]	W. H. Fleming and M. H. Soner, Controlled Markov Processes and Viscosity Solutions, vol. 25 of Stochastic Modelling and Applied Probability,, 2nd edition, (2006). Google Scholar
[24]	H. Föllmer and P. Leukert, Quantile hedging,, SIAM, 3 (1999), 251. doi: 10.1007/s007800050062. Google Scholar
[25]	D. Goreac and O.-S. Serea, Mayer and optimal stopping stochastic control problems with discontinuous cost,, J. Math. Anal. Appl., 380 (2011), 327. doi: 10.1016/j.jmaa.2011.02.039. Google Scholar
[26]	N. V. Krylov, Mean value theorems for stochastic integrals,, Ann. Probab., 29 (2001), 385. doi: 10.1214/aop/1008956335. Google Scholar
[27]	N. Krylov, On the rate of convergence of finite difference approximation for Bellman's equation,, St. Petersburg Math. J., 9 (1998), 639. Google Scholar
[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. doi: 10.1007/s004400050264. Google Scholar
[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. doi: 10.1007/s00245-005-0832-3. Google Scholar
[30]	H. Kushner and P. Dupuis, Numerical Methods for Stochastic Control Problems in Continuous Time, vol. 24 of Applications of mathematics,, Springer, (2001). doi: 10.1007/978-1-4613-0007-6. Google Scholar
[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. doi: 10.1109/TAC.2005.851439. Google Scholar
[32]	R. Munos and H. Zidani, Consistency of a simple multidimensional scheme for hjb equations,, C. R. Acad. Sci. Paris, 340* (2005), 499. doi: 10.1016/j.crma.2005.02.001. Google Scholar*
[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. doi: 10.1016/0021-9991(88)90002-2. Google Scholar
[34]	R. Rubinstein and D. Kroese, Simulation and the Monte Carlo Method,, Wiley, (2008). Google Scholar
[35]	J. Yong and X. Y. Zhou, Stochastic Controls: Hamiltonian Systems and HJB Equations,, Stochastic Modelling and Applied Probability, (1999). doi: 10.1007/978-1-4612-1466-3. Google Scholar

[1]	Esther Klann, Ronny Ramlau, Wolfgang Ring. A Mumford-Shah level-set approach for the inversion and segmentation of SPECT/CT data. Inverse Problems & Imaging, 2011, 5 (1) : 137-166. doi: 10.3934/ipi.2011.5.137
[2]	Mariane Bourgoing. Viscosity solutions of fully nonlinear second order parabolic equations with $L^1$ dependence in time and Neumann boundary conditions. Existence and applications to the level-set approach. Discrete & Continuous Dynamical Systems - A, 2008, 21 (4) : 1047-1069. doi: 10.3934/dcds.2008.21.1047
[3]	Mikhail Gusev. On reachability analysis for nonlinear control systems with state constraints. Conference Publications, 2015, 2015 (special) : 579-587. doi: 10.3934/proc.2015.0579
[4]	Jeremiah Birrell. A posteriori error bounds for two point boundary value problems: A green's function approach. Journal of Computational Dynamics, 2015, 2 (2) : 143-164. doi: 10.3934/jcd.2015001
[5]	Weidong Zhao, Jinlei Wang, Shige Peng. Error estimates of the $\theta$-scheme for backward stochastic differential equations. Discrete & Continuous Dynamical Systems - B, 2009, 12 (4) : 905-924. doi: 10.3934/dcdsb.2009.12.905
[6]	Gerard Gómez, Josep–Maria Mondelo, Carles Simó. A collocation method for the numerical Fourier analysis of quasi-periodic functions. II: Analytical error estimates. Discrete & Continuous Dynamical Systems - B, 2010, 14 (1) : 75-109. doi: 10.3934/dcdsb.2010.14.75
[7]	Xiaoying Han, Jinglai Li, Dongbin Xiu. Error analysis for numerical formulation of particle filter. Discrete & Continuous Dynamical Systems - B, 2015, 20 (5) : 1337-1354. doi: 10.3934/dcdsb.2015.20.1337
[8]	Ugo Bessi. The stochastic value function in metric measure spaces. Discrete & Continuous Dynamical Systems - A, 2017, 37 (4) : 1819-1839. doi: 10.3934/dcds.2017076
[9]	Juan Li, Wenqiang Li. Controlled reflected mean-field backward stochastic differential equations coupled with value function and related PDEs. Mathematical Control & Related Fields, 2015, 5 (3) : 501-516. doi: 10.3934/mcrf.2015.5.501
[10]	Philippe Chartier, Ander Murua, Jesús María Sanz-Serna. A formal series approach to averaging: Exponentially small error estimates. Discrete & Continuous Dynamical Systems - A, 2012, 32 (9) : 3009-3027. doi: 10.3934/dcds.2012.32.3009
[11]	Wolf-Jürgen Beyn, Raphael Kruse. Two-sided error estimates for the stochastic theta method. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 389-407. doi: 10.3934/dcdsb.2010.14.389
[12]	Konstantinos Chrysafinos, Efthimios N. Karatzas. Symmetric error estimates for discontinuous Galerkin approximations for an optimal control problem associated to semilinear parabolic PDE's. Discrete & Continuous Dynamical Systems - B, 2012, 17 (5) : 1473-1506. doi: 10.3934/dcdsb.2012.17.1473
[13]	Sun-Yung Alice Chang, Xi-Nan Ma, Paul Yang. Principal curvature estimates for the convex level sets of semilinear elliptic equations. Discrete & Continuous Dynamical Systems - A, 2010, 28 (3) : 1151-1164. doi: 10.3934/dcds.2010.28.1151
[14]	Sergio Amat, Pablo Pedregal. On a variational approach for the analysis and numerical simulation of ODEs. Discrete & Continuous Dynamical Systems - A, 2013, 33 (4) : 1275-1291. doi: 10.3934/dcds.2013.33.1275
[15]	Yongchao Liu, Hailin Sun, Huifu Xu. An approximation scheme for stochastic programs with second order dominance constraints. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 473-490. doi: 10.3934/naco.2016021
[16]	Xiantao Xiao, Jian Gu, Liwei Zhang, Shaowu Zhang. A sequential convex program method to DC program with joint chance constraints. Journal of Industrial & Management Optimization, 2012, 8 (3) : 733-747. doi: 10.3934/jimo.2012.8.733
[17]	Uwe Helmke, Jens Jordan, Julia Lieb. Probability estimates for reachability of linear systems defined over finite fields. Advances in Mathematics of Communications, 2016, 10 (1) : 63-78. doi: 10.3934/amc.2016.10.63
[18]	Kim S. Bey, Peter Z. Daffer, Hideaki Kaneko, Puntip Toghaw. Error analysis of the p-version discontinuous Galerkin method for heat transfer in built-up structures. Communications on Pure & Applied Analysis, 2007, 6 (3) : 719-740. doi: 10.3934/cpaa.2007.6.719
[19]	Hiroshi Watanabe. Solvability of boundary value problems for strongly degenerate parabolic equations with discontinuous coefficients. Discrete & Continuous Dynamical Systems - S, 2014, 7 (1) : 177-189. doi: 10.3934/dcdss.2014.7.177
[20]	Kexue Li. Effects of the noise level on nonlinear stochastic fractional heat equations. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-24. doi: 10.3934/dcdsb.2019065

2018 Impact Factor: 1.143

American Institute of Mathematical Sciences