Deep splitting method for parabolic PDEs. (English) Zbl 1501.65054
Summary: In this paper, we introduce a numerical method for nonlinear parabolic partial differential equations (PDEs) that combines operator splitting with deep learning. It divides the PDE approximation problem into a sequence of separate learning problems. Since the computational graph for each of the subproblems is comparatively small, the approach can handle extremely high dimensional PDEs. We test the method on different examples from physics, stochastic control, and mathematical finance. In all cases, it yields very good results in up to 10,000 dimensions with short run times.
MSC:
| 65M22 | Numerical solution of discretized equations for initial value and initial-boundary value problems involving PDEs |
| 68T07 | Artificial neural networks and deep learning |
| 60H35 | Computational methods for stochastic equations (aspects of stochastic analysis) |
| 65C05 | Monte Carlo methods |
| 35K15 | Initial value problems for second-order parabolic equations |
| 35K55 | Nonlinear parabolic equations |
| 91G20 | Derivative securities (option pricing, hedging, etc.) |
| 91G60 | Numerical methods (including Monte Carlo methods) |
| 93E20 | Optimal stochastic control |
Keywords:
nonlinear partial differential equations; splitting-up method; neural networks; deep learningReferences:
| [1] | V. Bally and G. Pagès, A quantization algorithm for solving multi-dimensional discrete-time optimal stopping problems, Bernoulli, 9 (2003), pp. 1003-1049. · Zbl 1042.60021 |
| [2] | C. Beck, S. Becker, P. Grohs, N. Jaafari, and A. Jentzen, Solving the Kolmogorov PDE by means of deep learning, J. Sci. Comput., 88 (2021), 73. · Zbl 1490.65006 |
| [3] | C. Beck, W. E, and A. Jentzen, Machine learning approximation algorithms for high-dimensional fully nonlinear partial differential equations and second-order backward stochastic differential equations, J. Nonlinear Sci., 29 (2019), pp. 1563-1619. · Zbl 1442.91116 |
| [4] | C. Beck, M. Hutzenthaler, A. Jentzen, and B. Kuckuck, An Overview on Deep Learning-Based Approximation Methods for Partial Differential Equations, preprint, https://arxiv.org/abs/2012.12348, 2020. |
| [5] | S. Becker, R. Braunwarth, M. Hutzenthaler, A. Jentzen, and P. von Wurstemberger, Numerical simulations for full history recursive multilevel Picard approximations for systems of high-dimensional partial differential equations, Commun. Comput. Phys., 28 (2020), pp. 2109-2138. · Zbl 1473.65251 |
| [6] | S. Becker, P. Cheridito, and A. Jentzen, Deep optimal stopping, J. Mach. Learn. Res., 20 (2019), 74. · Zbl 1495.60029 |
| [7] | C. Bender and R. Denk, A forward scheme for backward SDEs, Stochastic Process. Appl., 117 (2007), pp. 1793-1812. · Zbl 1131.60054 |
| [8] | C. Bender, N. Schweizer, and J. Zhuo, A primal-dual algorithm for BSDEs, Math. Finance, 27 (2017), pp. 866-901. · Zbl 1423.91008 |
| [9] | Y. Bengio, Learning deep architectures for AI, Found. Trends Mach. Learn., 2 (2009), pp. 1-127. · Zbl 1192.68503 |
| [10] | J. Berg and K. Nyström, A unified deep artificial neural network approach to partial differential equations in complex geometries, Neurocomputing, 317 (2018), pp. 28-41. |
| [11] | J. Berner, P. Grohs, and A. Jentzen, Analysis of the generalization error: Empirical risk minimization over deep artificial neural networks overcomes the curse of dimensionality in the numerical approximation of Black-Scholes partial differential equations, SIAM J. Math. Data Sci., 2 (2020), pp. 631-657, https://doi.org/10.1137/19M125649X. · Zbl 1480.60191 |
| [12] | B. Bouchard and N. Touzi, Discrete-time approximation and Monte-Carlo simulation of backward stochastic differential equations, Stochastic Process. Appl., 111 (2004), pp. 175-206. · Zbl 1071.60059 |
| [13] | D. Braess, Finite Elements: Theory, Fast Solvers, and Applications in Elasticity Theory, 3rd ed., Cambridge University Press, Cambridge, UK, 2007. · Zbl 1180.65146 |
| [14] | Q. Chan-Wai-Nam, J. Mikael, and X. Warin, Machine learning for semi linear PDEs, J. Sci. Comput., 79 (2019), pp. 1667-1712. · Zbl 1433.68332 |
| [15] | J.-F. Chassagneux, Linear multistep schemes for BSDEs, SIAM J. Numer. Anal., 52 (2014), pp. 2815-2836, https://doi.org/10.1137/120902951. · Zbl 1326.65017 |
| [16] | J.-F. Chassagneux and D. Crisan, Runge-Kutta schemes for backward stochastic differential equations, Ann. Appl. Probab., 24 (2014), pp. 679-720. · Zbl 1303.60045 |
| [17] | J.-F. Chassagneux and A. Richou, Numerical stability analysis of the Euler scheme for BSDEs, SIAM J. Numer. Anal., 53 (2015), pp. 1172-1193, https://doi.org/10.1137/140977047. · Zbl 1311.93088 |
| [18] | J.-F. Chassagneux and A. Richou, Numerical simulation of quadratic BSDEs, Ann. Appl. Probab., 26 (2016), pp. 262-304. · Zbl 1334.60129 |
| [19] | D. Crisan and K. Manolarakis, Probabilistic methods for semilinear partial differential equations. Applications to finance, M2AN Math. Model. Numer. Anal., 44 (2010), pp. 1107-1133. · Zbl 1210.65011 |
| [20] | D. Crisan and K. Manolarakis, Solving backward stochastic differential equations using the cubature method: Application to nonlinear pricing, SIAM J. Financial Math., 3 (2012), pp. 534-571, https://doi.org/10.1137/090765766. · Zbl 1259.65005 |
| [21] | D. Crisan and K. Manolarakis, Second order discretization of backward SDEs and simulation with the cubature method, Ann. Appl. Probab., 24 (2014), pp. 652-678. · Zbl 1303.60046 |
| [22] | D. Crisan, K. Manolarakis, and N. Touzi, On the Monte Carlo simulation of BSDEs: An improvement on the Malliavin weights, Stochastic Process. Appl., 120 (2010), pp. 1133-1158. · Zbl 1193.65005 |
| [23] | T. Deck and S. Kruse, Parabolic differential equations with unbounded coefficients-a generalization of the parametrix method, Acta Appl. Math., 74 (2002), pp. 71-91. · Zbl 1021.35042 |
| [24] | F. Delarue and S. Menozzi, A forward-backward stochastic algorithm for quasi-linear PDEs, Ann. Appl. Probab., 16 (2006), pp. 140-184. · Zbl 1097.65011 |
| [25] | P. Dörsek, Semigroup splitting and cubature approximations for the stochastic Navier-Stokes equations, SIAM J. Numer. Anal., 50 (2012), pp. 729-746, https://doi.org/10.1137/110833841. · Zbl 1247.60090 |
| [26] | J. Douglas, Jr., J. Ma, and P. Protter, Numerical methods for forward-backward stochastic differential equations, Ann. Appl. Probab., 6 (1996), pp. 940-968. · Zbl 0861.65131 |
| [27] | W. E, J. Han, and A. Jentzen, Deep learning-based numerical methods for high-dimensional parabolic partial differential equations and backward stochastic differential equations, Commun. Math. Stat., 5 (2017), pp. 349-380. · Zbl 1382.65016 |
| [28] | W. E, M. Hutzenthaler, A. Jentzen, and T. Kruse, Multilevel Picard iterations for solving smooth semilinear parabolic heat equations, Partial Differ. Equ. Appl., to appear. · Zbl 1418.65149 |
| [29] | W. E, M. Hutzenthaler, A. Jentzen, and T. Kruse, On multilevel Picard numerical approximations for high-dimensional nonlinear parabolic partial differential equations and high-dimensional nonlinear backward stochastic differential equations, J. Sci. Comput., 79 (2019), pp. 1534-1571. · Zbl 1418.65149 |
| [30] | W. E and B. Yu, The deep Ritz method: A deep learning-based numerical algorithm for solving variational problems, Commun. Math. Stat., 6 (2018), pp. 1-12. · Zbl 1392.35306 |
| [31] | D. Elbrächter, P. Grohs, A. Jentzen, and C. Schwab, DNN expression rate analysis of high-dimensional PDEs: Application to option pricing, Constr. Approx., (2021), https://doi.org/10.1007/s00365-021-09541-6. · Zbl 1500.35009 |
| [32] | A.-m. Farahmand, S. Nabi, and D. N. Nikovski, Deep reinforcement learning for partial differential equation control, in Proceedings of the American Control Conference (ACC), 2017, pp. 3120-3127. |
| [33] | M. Fujii, A. Takahashi, and M. Takahashi, Asymptotic expansion as prior knowledge in deep learning method for high dimensional BSDEs, Asia-Pac., 26 (2019), pp. 391-408. · Zbl 1422.91694 |
| [34] | X. Glorot and Y. Bengio, Understanding the difficulty of training deep feedforward neural networks, in Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, 2010, pp. 249-256. |
| [35] | E. Gobet and C. Labart, Solving BSDE with adaptive control variate, SIAM J. Numer. Anal., 48 (2010), pp. 257-277, https://doi.org/10.1137/090755060. · Zbl 1208.60055 |
| [36] | E. Gobet and J.-P. Lemor, Numerical Simulation of BSDEs Using Empirical Regression Methods: Theory and Practice, preprint, https://arxiv.org/abs/0806.4447, 2008. |
| [37] | E. Gobet, J.-P. Lemor, and X. Warin, A regression-based Monte Carlo method to solve backward stochastic differential equations, Ann. Appl. Prob., 15 (2005), pp. 2172-2202. · Zbl 1083.60047 |
| [38] | E. Gobet, J. G. López-Salas, P. Turkedjiev, and C. Vázquez, Stratified regression Monte-Carlo scheme for semilinear PDEs and BSDEs with large scale parallelization on GPUs, SIAM J. Sci. Comput., 38 (2016), pp. C652-C677, https://doi.org/10.1137/16M106371X. · Zbl 1352.65008 |
| [39] | E. Gobet and P. Turkedjiev, Approximation of backward stochastic differential equations using Malliavin weights and least-squares regression, Bernoulli, 22 (2016), pp. 530-562. · Zbl 1339.60094 |
| [40] | E. Gobet and P. Turkedjiev, Linear regression MDP scheme for discrete backward stochastic differential equations under general conditions, Math. Comp., 85 (2016), pp. 1359-1391. · Zbl 1344.60067 |
| [41] | L. Goudenege, A. Molent, and A. Zanette, Machine learning for pricing American options in high-dimensional Markovian and non-Markovian models, Quant. Finance, 20 (2020), pp. 573-591. · Zbl 1466.91339 |
| [42] | W. Grecksch and H. Lisei, Approximation of stochastic nonlinear equations of Schrödinger type by the splitting method, Stochastic Anal. Appl., 31 (2013), pp. 314-335. · Zbl 1271.60073 |
| [43] | P. Grohs, F. Hornung, A. Jentzen, and P. von Wurstemberger, A proof that artificial neural networks overcome the curse of dimensionality in the numerical approximation of Black-Scholes partial differential equations, Mem. Amer. Math. Soc., to appear. · Zbl 07679303 |
| [44] | I. Gyöngy and N. Krylov, On the rate of convergence of splitting-up approximations for SPDEs, in Stochastic Inequalities and Applications, Birkhäuser, Basel, 2003, pp. 301-321. · Zbl 1038.60057 |
| [45] | I. Gyöngy and N. Krylov, On the splitting-up method and stochastic partial differential equations, Ann. Probab., 31 (2003), pp. 564-591. · Zbl 1028.60058 |
| [46] | M. Hairer, M. Hutzenthaler, and A. Jentzen, Loss of regularity for Kolmogorov equations, Ann. Probab., 43 (2015), pp. 468-527. · Zbl 1322.35083 |
| [47] | J. Han, A. Jentzen, and W. E, Solving high-dimensional partial differential equations using deep learning, Proc. Natl. Acad. Sci. USA, 115 (2018), pp. 8505-8510. · Zbl 1416.35137 |
| [48] | J. Han and J. Long, Convergence of the deep BSDE method for coupled FBSDEs, Probab. Uncertain. Quant. Risk, 5 (2020), pp. 1-33. · Zbl 1454.60105 |
| [49] | P. Henry-Labordère, Counterparty Risk Valuation: A Marked Branching Diffusion Approach, preprint, https://arxiv.org/abs/1203.2369, 2012. |
| [50] | P. Henry-Labordere, Deep Primal-Dual Algorithm for BSDEs: Applications of Machine Learning to CVA and IM, preprint, SSRN-id3071506, 2017. |
| [51] | P. Henry-Labordère, N. Oudjane, X. Tan, N. Touzi, and X. Warin, Branching diffusion representation of semilinear PDEs and Monte Carlo approximation, Ann. Inst. Henri Poincaré Probab. Stat., 55 (2019), pp. 184-210. · Zbl 1467.60067 |
| [52] | P. Henry-Labordère, X. Tan, and N. Touzi, A numerical algorithm for a class of BSDEs via the branching process, Stochastic Process. Appl., 124 (2014), pp. 1112-1140. · Zbl 1301.60084 |
| [53] | T. P. Huijskens, M. J. Ruijter, and C. W. Oosterlee, Efficient numerical Fourier methods for coupled forward-backward SDEs, J. Comput. Appl. Math., 296 (2016), pp. 593-612. · Zbl 1336.65010 |
| [54] | C. Huré, H. Pham, and X. Warin, Some Machine Learning Schemes for High-Dimensional Nonlinear PDEs, preprint, https://arxiv.org/abs/1902.01599v1, 2019. · Zbl 1440.60063 |
| [55] | M. Hutzenthaler, A. Jentzen, T. Kruse, and T. A. Nguyen, A proof that rectified deep neural networks overcome the curse of dimensionality in the numerical approximation of semilinear heat equations, Partial Differ. Equ. Appl., 1 (2020), pp. 1-34. · Zbl 1455.65200 |
| [56] | M. Hutzenthaler, A. Jentzen, T. Kruse, T. A. Nguyen, and P. von Wurstemberger, Overcoming the curse of dimensionality in the numerical approximation of semilinear parabolic partial differential equations, Proc. A, 476 (2020), 20190630. · Zbl 1469.60220 |
| [57] | M. Hutzenthaler, A. Jentzen, and P. von Wurstemberger, Overcoming the curse of dimensionality in the approximative pricing of financial derivatives with default risks, Electron. J. Probab., 25 (2020), pp. 1-73. · Zbl 1469.60220 |
| [58] | M. Hutzenthaler and T. Kruse, Multilevel Picard approximations of high-dimensional semilinear parabolic differential equations with gradient-dependent nonlinearities, SIAM J. Numer. Anal., 58 (2020), pp. 929-961, https://doi.org/10.1137/17M1157015. |
| [59] | S. Ioffe and C. Szegedy, Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift, preprint, https://arxiv.org/abs/1502.03167, 2015. |
| [60] | A. Jacquier and M. Oumgari, Deep PPDEs for Rough Local Stochastic Volatility, preprint, https://arxiv.org/abs/1906.02551v1, 2019. |
| [61] | A. Jentzen, D. Salimova, and T. Welti, Proof that deep artificial neural networks overcome the curse of dimensionality in the numerical approximation of Kolmogorov partial differential equations with constant diffusion and nonlinear drift coefficients, Commun. Math. Sci., 19 (2021), pp. 1167-1205. · Zbl 1475.65157 |
| [62] | D. Kingma and J. Ba, Adam: A Method for Stochastic Optimization, preprint, https://arxiv.org/abs/1412.6980, 2014. |
| [63] | A. Klenke, Probability Theory: A Comprehensive Course, 2nd ed., Universitext, Springer, London, 2014. · Zbl 1295.60001 |
| [64] | P. E. Kloeden and E. Platen, Numerical Solution of Stochastic Differential Equations, Appl. Math. (N. Y.) 23, Springer-Verlag, Berlin, 1992. · Zbl 0752.60043 |
| [65] | N. V. Krylov, Lectures on Elliptic and Parabolic Equations in Hölder Spaces, Grad. Stud. Math. 12, American Mathematical Society, Providence, RI, 1996. · Zbl 0865.35001 |
| [66] | N. V. Krylov, On Kolmogorov’s equations for finite-dimensional diffusions, in Stochastic PDE’s and Kolmogorov Equations in Infinite Dimensions (Cetraro, 1998), Lecture Notes in Math. 1715, Springer, Berlin, 1999, pp. 1-63. · Zbl 0943.60070 |
| [67] | G. Kutyniok, P. Petersen, M. Raslan, and R. Schneider, A Theoretical Analysis of Deep Neural Networks and Parametric PDEs, https://arxiv.org/abs/1904.00377, 2019. |
| [68] | C. Labart and J. Lelong, A parallel algorithm for solving BSDEs, Monte Carlo Methods Appl., 19 (2013), pp. 11-39. · Zbl 1263.65005 |
| [69] | S. Larsson and V. Thomée, Partial Differential Equations with Numerical Methods, Texts Appl. Math. 45, Springer-Verlag, Berlin, 2003. · Zbl 1025.65002 |
| [70] | Y. LeCun, Y. Bengio, and G. Hinton, Deep learning, Nature, 521 (2015), pp. 436-444. |
| [71] | J.-P. Lemor, E. Gobet, and X. Warin, Rate of convergence of an empirical regression method for solving generalized backward stochastic differential equations, Bernoulli, 12 (2006), pp. 889-916. · Zbl 1136.60351 |
| [72] | A. Lionnet, G. dos Reis, and L. Szpruch, Time discretization of FBSDE with polynomial growth drivers and reaction-diffusion PDEs, Ann. Appl. Probab., 25 (2015), pp. 2563-2625. · Zbl 1342.65011 |
| [73] | Z. Long, Y. Lu, X. Ma, and B. Dong, PDE-Net: Learning PDEs from data, in Proceedings of the International Conference on Machine Learning, 2018, pp. 3208-3216. |
| [74] | K. O. Lye, S. Mishra, and D. Ray, Deep learning observables in computational fluid dynamics, J. Comput. Phys., 410 (2020), 109339. · Zbl 1436.76051 |
| [75] | J. Ma, P. Protter, J. San Martín, and S. Torres, Numerical method for backward stochastic differential equations, Ann. Appl. Probab., 12 (2002), pp. 302-316. · Zbl 1017.60074 |
| [76] | J. Ma, P. Protter, and J. M. Yong, Solving forward-backward stochastic differential equations explicitly-a four step scheme, Probab. Theory Related Fields, 98 (1994), pp. 339-359. · Zbl 0794.60056 |
| [77] | J. Ma and J. Yong, Forward-Backward Stochastic Differential Equations and Their Applications, Lecture Notes in Math. 1702, Springer-Verlag, Berlin, 1999. · Zbl 0927.60004 |
| [78] | M. Magill, F. Qureshi, and H. de Haan, Neural networks trained to solve differential equations learn general representations, in Advances in Neural Information Processing Systems, MIT Press, Cambridge, MA, 2018, pp. 4075-4085. |
| [79] | G. Maruyama, Continuous Markov processes and stochastic equations, Rend. Circ. Mat. Palermo (2), 4 (1955), pp. 48-90. · Zbl 0053.40901 |
| [80] | H. P. McKean, Application of Brownian motion to the equation of Kolmogorov-Petrovskii-Piskunov, Comm. Pure Appl. Math., 28 (1975), pp. 323-331. · Zbl 0316.35053 |
| [81] | G. N. Mil’shtein, Approximate integration of stochastic differential equations, Theory Probab. Appl., 19 (1975), pp. 557-562, https://doi.org/10.1137/1119062. · Zbl 0314.60039 |
| [82] | G. N. Milstein and M. V. Tretyakov, Numerical algorithms for forward-backward stochastic differential equations, SIAM J. Sci. Comput., 28 (2006), pp. 561-582, https://doi.org/10.1137/040614426. · Zbl 1114.60054 |
| [83] | G. N. Milstein and M. V. Tretyakov, Discretization of forward-backward stochastic differential equations and related quasi-linear parabolic equations, IMA J. Numer. Anal., 27 (2007), pp. 24-44. · Zbl 1109.65009 |
| [84] | G. N. Milstein and M. V. Tretyakov, Solving parabolic stochastic partial differential equations via averaging over characteristics, Math. Comp., 78 (2009), pp. 2075-2106. · Zbl 1198.65033 |
| [85] | H. Pham, Feynman-Kac representation of fully nonlinear PDEs and applications, Acta Math. Vietnam., 40 (2015), pp. 255-269. · Zbl 1322.60133 |
| [86] | M. Raissi, Deep hidden physics models: Deep learning of nonlinear partial differential equations, J. Mach. Learn. Res., 19 (2018), pp. 932-955. · Zbl 1439.68021 |
| [87] | M. J. Ruijter and C. W. Oosterlee, A Fourier cosine method for an efficient computation of solutions to BSDEs, SIAM J. Sci. Comput., 37 (2015), pp. A859-A889, https://doi.org/10.1137/130913183. · Zbl 1314.65011 |
| [88] | M. J. Ruijter and C. W. Oosterlee, Numerical Fourier method and second-order Taylor scheme for backward SDEs in finance, Appl. Numer. Math., 103 (2016), pp. 1-26. · Zbl 1386.91166 |
| [89] | A. Ruszczynski and J. Yao, A Dual Method for Backward Stochastic Differential Equations with Application to Risk Valuation, preprint, https://arxiv.org/abs/1701.06234, 2017. |
| [90] | J. Sirignano and K. Spiliopoulos, DGM: A deep learning algorithm for solving partial differential equations, J. Comput. Phys., 375 (2018), pp. 1339-1364. · Zbl 1416.65394 |
| [91] | V. V. Skorokhod, Branching diffusion processes, Theory Probab. Appl., 9 (1964), pp. 445-449, https://doi.org/10.1137/1109059. · Zbl 0264.60058 |
| [92] | D. W. Stroock, Lectures on Topics in Stochastic Differential Equations, Tata Inst. Fund. Res. Lectures on Math. and Phys. 68, Tata Institute of Fundamental Research, Bombay; Springer-Verlag, Berlin, New York, 1982. · Zbl 0516.60065 |
| [93] | V. Thomée, Galerkin Finite Element Methods for Parabolic Problems, Springer Ser. Comput. Math. 25, Springer-Verlag, Berlin, 1997. · Zbl 0884.65097 |
| [94] | P. Turkedjiev, Two algorithms for the discrete time approximation of Markovian backward stochastic differential equations under local conditions, Electron. J. Probab., 20 (2015), 50. · Zbl 1322.60139 |
| [95] | S. Watanabe, On the branching process for Brownian particles with an absorbing boundary, J. Math. Kyoto Univ., 4 (1965), pp. 385-398. · Zbl 0134.34401 |
| [96] | J. Zhang, A numerical scheme for BSDEs, Ann. Appl. Probab., 14 (2004), pp. 459-488. · Zbl 1056.60067 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
