American Institute of Mathematical Sciences

Advanced
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

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, 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-17. 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-2734. 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-4159. 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-63. 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-54. 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-558. 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-1893. 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-1135. 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-80. 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-4316. 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-163. 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, J. Numer. Anal., 26 (2006), 188-212. 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-357. 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-3150. 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-317. 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-17. 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-2431. 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-122.  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-339. 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-1462. 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-1630. 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, Springer, New York, 2006.  Google Scholar

[24]

H. Föllmer and P. Leukert, Quantile hedging, SIAM, 3 (1999), 251-273. 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-342. 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-410. 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-650.  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-16. 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-399. 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, New York, 2001, Second edition. 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-957. 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, Ser. I, 340 (2005), 499-502. 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-49. doi: 10.1016/0021-9991(88)90002-2.  Google Scholar

[34]

R. Rubinstein and D. Kroese, Simulation and the Monte Carlo Method, Wiley, 2008, Second edition.  Google Scholar

[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.  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-17. 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-2734. 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-4159. 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-63. 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-54. 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-558. 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-1893. 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-1135. 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-80. 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-4316. 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-163. 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, J. Numer. Anal., 26 (2006), 188-212. 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-357. 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-3150. 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-317. 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-17. 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-2431. 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-122.  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-339. 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-1462. 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-1630. 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, Springer, New York, 2006.  Google Scholar

[24]

H. Föllmer and P. Leukert, Quantile hedging, SIAM, 3 (1999), 251-273. 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-342. 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-410. 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-650.  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-16. 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-399. 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, New York, 2001, Second edition. 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-957. 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, Ser. I, 340 (2005), 499-502. 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-49. doi: 10.1016/0021-9991(88)90002-2.  Google Scholar

[34]

R. Rubinstein and D. Kroese, Simulation and the Monte Carlo Method, Wiley, 2008, Second edition.  Google Scholar

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

[1]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, 2021, 15 (2) : 315-338. doi: 10.3934/ipi.2020070
[2]

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

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, 2008, 21 (4) : 1047-1069. doi: 10.3934/dcds.2008.21.1047
[4]

Yoshikazu Giga, Hiroyoshi Mitake, Hung V. Tran. Remarks on large time behavior of level-set mean curvature flow equations with driving and source terms. Discrete & Continuous Dynamical Systems - B, 2020, 25 (10) : 3983-3999. doi: 10.3934/dcdsb.2019228
[5]

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

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

Tetsuya Ishiwata, Takeshi Ohtsuka. Numerical analysis of an ODE and a level set methods for evolving spirals by crystalline eikonal-curvature flow. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 893-907. doi: 10.3934/dcdss.2020390
[8]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, 2021, 15 (3) : 387-413. doi: 10.3934/ipi.2020073
[9]

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

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

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

Ugo Bessi. The stochastic value function in metric measure spaces. Discrete & Continuous Dynamical Systems, 2017, 37 (4) : 1819-1839. doi: 10.3934/dcds.2017076
[13]

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

Philippe Chartier, Ander Murua, Jesús María Sanz-Serna. A formal series approach to averaging: Exponentially small error estimates. Discrete & Continuous Dynamical Systems, 2012, 32 (9) : 3009-3027. doi: 10.3934/dcds.2012.32.3009
[15]

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

Peter Frolkovič, Viera Kleinová. A new numerical method for level set motion in normal direction used in optical flow estimation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 851-863. doi: 10.3934/dcdss.2020347
[17]

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

Sergio Amat, Pablo Pedregal. On a variational approach for the analysis and numerical simulation of ODEs. Discrete & Continuous Dynamical Systems, 2013, 33 (4) : 1275-1291. doi: 10.3934/dcds.2013.33.1275
[19]

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, 2010, 28 (3) : 1151-1164. doi: 10.3934/dcds.2010.28.1151
[20]

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

2019 Impact Factor: 1.338

Tools

Metrics

  • PDF downloads (79)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences