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

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

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.

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

[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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Continuous Dynamical Systems, 2012, 32 (9) : 3009-3027. doi: 10.3934/dcds.2012.32.3009
[15]

Konstantinos Chrysafinos, Efthimios N. Karatzas. Symmetric error estimates for discontinuous Galerkin approximations for an optimal control problem associated to semilinear parabolic PDE's. Discrete and Continuous Dynamical Systems - B, 2012, 17 (5) : 1473-1506. doi: 10.3934/dcdsb.2012.17.1473
[16]

Wolf-Jürgen Beyn, Raphael Kruse. Two-sided error estimates for the stochastic theta method. Discrete and Continuous Dynamical Systems - B, 2010, 14 (2) : 389-407. doi: 10.3934/dcdsb.2010.14.389
[17]

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

Sergio Amat, Pablo Pedregal. On a variational approach for the analysis and numerical simulation of ODEs. Discrete and 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 and 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 and Optimization, 2016, 6 (4) : 473-490. doi: 10.3934/naco.2016021

2021 Impact Factor: 1.588

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy