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

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

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.
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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[15]

B. Bouchard, R. Elie and N. Touzi, Stochastic target problems with controlled loss,, SIAM, 48 (2008), 3123. 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. 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. 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. 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.

[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.

[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.

[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.

[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).

[24]

H. Föllmer and P. Leukert, Quantile hedging,, SIAM, 3 (1999), 251. 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. doi: 10.1016/j.jmaa.2011.02.039.

[26]

N. V. Krylov, Mean value theorems for stochastic integrals,, Ann. Probab., 29 (2001), 385. 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.

[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.

[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.

[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.

[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.

[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.

[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.

[34]

R. Rubinstein and D. Kroese, Simulation and the Monte Carlo Method,, Wiley, (2008).

[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.

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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[15]

B. Bouchard, R. Elie and N. Touzi, Stochastic target problems with controlled loss,, SIAM, 48 (2008), 3123. 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. 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. 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. 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.

[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.

[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.

[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.

[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).

[24]

H. Föllmer and P. Leukert, Quantile hedging,, SIAM, 3 (1999), 251. 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. doi: 10.1016/j.jmaa.2011.02.039.

[26]

N. V. Krylov, Mean value theorems for stochastic integrals,, Ann. Probab., 29 (2001), 385. 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.

[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.

[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.

[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.

[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.

[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.

[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.

[34]

R. Rubinstein and D. Kroese, Simulation and the Monte Carlo Method,, Wiley, (2008).

[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.

[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]

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

[14]

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

[15]

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

[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]

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

[19]

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

[20]

G. Wei, P. Clifford. Analysis and numerical approximation of a class of two-way diffusions. Communications on Pure & Applied Analysis, 2003, 2 (1) : 91-99. doi: 10.3934/cpaa.2003.2.91

2017 Impact Factor: 1.179

Metrics

  • PDF downloads (6)
  • HTML views (0)
  • Cited by (2)

[Back to Top]