Linear regression MDP scheme for discrete backward stochastic differential equations under general conditions

Gobet, Emmanuel; Turkedjiev, Plamen

doi:10.1090/mcom/3013

Linear regression MDP scheme for discrete backward stochastic differential equations under general conditions
HTML articles powered by AMS MathViewer

by Emmanuel Gobet and Plamen Turkedjiev PDF

Math. Comp. 85 (2016), 1359-1391 Request permission

Abstract:

We design a numerical scheme for solving the Multi-step Forward Dynamic Programming (MDP) equation arising from the time-discretization of backward stochastic differential equations. The generator is assumed to be locally Lipschitz, which includes some cases of quadratic drivers. When the large sequence of conditional expectations is computed using empirical least-squares regressions, under general conditions we establish an upper bound error as the average, rather than the sum, of local regression errors only, suggesting that our error estimation is tight. Despite the nested regression problems, the interdependency errors are justified to be at most of the order of the statistical regression errors (up to logarithmic factor). Finally, we optimize the algorithm parameters, depending on the dimension and on the smoothness of value functions, in the limit as the time mesh size goes to zero and we compute the complexity needed to achieve a given accuracy. Numerical experiments are presented illustrating theoretical convergence estimates.

References

Vlad Bally, Gilles Pagès, and Jacques Printems, A quantization tree method for pricing and hedging multidimensional American options, Math. Finance 15 (2005), no. 1, 119–168. MR 2116799, DOI 10.1111/j.0960-1627.2005.00213.x
Tarik Ben Zineb and Emmanuel Gobet, Preliminary control variates to improve empirical regression methods, Monte Carlo Methods Appl. 19 (2013), no. 4, 331–354. MR 3139313, DOI 10.1515/mcma-2013-0015
Christian Bender and Robert Denk, A forward scheme for backward SDEs, Stochastic Process. Appl. 117 (2007), no. 12, 1793–1812. MR 2437729, DOI 10.1016/j.spa.2007.03.005
Christian Bender and Thilo Moseler, Importance sampling for backward SDEs, Stoch. Anal. Appl. 28 (2010), no. 2, 226–253. MR 2739557, DOI 10.1080/07362990903546405
C. Bender and J. Steiner, Least-squares Monte Carlo for BSDEs, Numerical Methods in Finance (R. Carmona, P. Del Moral, P. Hu, and N. Oudjane, eds.), Series: Springer Proceedings in Mathematics, Vol. 12, 2012, pp. 257–289.
E. Benhamou, E. Gobet, and M. Miri, Smart expansion and fast calibration for jump diffusions, Finance Stoch. 13 (2009), no. 4, 563–589. MR 2519844, DOI 10.1007/s00780-009-0102-3
Bruno Bouchard and Nizar Touzi, Discrete-time approximation and Monte-Carlo simulation of backward stochastic differential equations, Stochastic Process. Appl. 111 (2004), no. 2, 175–206. MR 2056536, DOI 10.1016/j.spa.2004.01.001
Philippe Briand and Céline Labart, Simulation of BSDEs by Wiener chaos expansion, Ann. Appl. Probab. 24 (2014), no. 3, 1129–1171. MR 3199982, DOI 10.1214/13-AAP943
J. F. Chassagneux and A. Richou, Numerical simulation of quadratic BSDEs, Available at http://arxiv.org/abs/1307.5741 (2013).
Dan Crisan and François Delarue, Sharp derivative bounds for solutions of degenerate semi-linear partial differential equations, J. Funct. Anal. 263 (2012), no. 10, 3024–3101. MR 2973334, DOI 10.1016/j.jfa.2012.07.015
D. Crisan and K. Manolarakis, Solving backward stochastic differential equations using the cubature method: application to nonlinear pricing, SIAM J. Financial Math. 3 (2012), no. 1, 534–571. MR 2968045, DOI 10.1137/090765766
F. Delarue and G. Guatteri, Weak existence and uniqueness for forward-backward SDEs, Stochastic Process. Appl. 116 (2006), no. 12, 1712–1742. MR 2307056, DOI 10.1016/j.spa.2006.05.002
N. El Karoui, S. Hamadène, and A. Matoussi, Backward stochastic differential equations and applications, Indifference Pricing: Theory and Applications (R. Carmona, ed.), Springer-Verlag, 2008, pp. 267–320.
N. El Karoui, S. Peng, and M. C. Quenez, Backward stochastic differential equations in finance, Math. Finance 7 (1997), no. 1, 1–71. MR 1434407, DOI 10.1111/1467-9965.00022
Christel Geiss, Stefan Geiss, and Emmanuel Gobet, Generalized fractional smoothness and $L_p$-variation of BSDEs with non-Lipschitz terminal condition, Stochastic Process. Appl. 122 (2012), no. 5, 2078–2116. MR 2921973, DOI 10.1016/j.spa.2012.02.006
Emmanuel Gobet and Céline Labart, Error expansion for the discretization of backward stochastic differential equations, Stochastic Process. Appl. 117 (2007), no. 7, 803–829. MR 2330720, DOI 10.1016/j.spa.2006.10.007
Emmanuel Gobet and Céline Labart, Solving BSDE with adaptive control variate, SIAM J. Numer. Anal. 48 (2010), no. 1, 257–277. MR 2608369, DOI 10.1137/090755060
E. Gobet and J. P. Lemor, Numerical simulation of BSDEs using empirical regression methods: theory and practice, Proceedings of the Fifth Colloquium on BSDEs (29th May - 1st June 2005, Shangai) (Available at http://hal.archives-ouvertes.fr/hal-00291199/fr/), 2006.
Emmanuel Gobet, Jean-Philippe Lemor, and Xavier Warin, A regression-based Monte Carlo method to solve backward stochastic differential equations, Ann. Appl. Probab. 15 (2005), no. 3, 2172–2202. MR 2152657, DOI 10.1214/105051605000000412
Emmanuel Gobet and Azmi Makhlouf, $\textbf {L}_2$-time regularity of BSDEs with irregular terminal functions, Stochastic Process. Appl. 120 (2010), no. 7, 1105–1132. MR 2639740, DOI 10.1016/j.spa.2010.03.003
E. Gobet and P. Turkedjiev, Linear regression MDP scheme for discrete backward stochastic differential equations under general conditions, Available on https://hal.archives-ouvertes.fr/hal-00642685v2 (2013).
E. Gobet and P. Turkedjiev, Approximation of BSDEs using Malliavin weights and least-squares regression, To appear in Bernoulli (2015).
Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
L. Gyorfi, M. Kohler, A. Krzyzak, and H. Walk, A Distribution-free Theory of Nonparametric Regression, Springer Series in Statistics, 2002.
Ying Hu, Peter Imkeller, and Matthias Müller, Utility maximization in incomplete markets, Ann. Appl. Probab. 15 (2005), no. 3, 1691–1712. MR 2152241, DOI 10.1214/105051605000000188
Peter Imkeller and Gonçalo Dos Reis, Path regularity and explicit convergence rate for BSDE with truncated quadratic growth, Stochastic Process. Appl. 120 (2010), no. 3, 348–379. MR 2584898, DOI 10.1016/j.spa.2009.11.004
Jean-Philippe Lemor, Emmanuel Gobet, and Xavier Warin, Rate of convergence of an empirical regression method for solving generalized backward stochastic differential equations, Bernoulli 12 (2006), no. 5, 889–916. MR 2265667, DOI 10.3150/bj/1161614951
Jin Ma, Philip Protter, Jaime San Martín, and Soledad Torres, Numerical method for backward stochastic differential equations, Ann. Appl. Probab. 12 (2002), no. 1, 302–316. MR 1890066, DOI 10.1214/aoap/1015961165
T. Moseler, A Picard-type iteration for backward stochastic differential equations: convergence and importance sampling, Ph.D. thesis, Fachbereich Mathematik und Statistik der Universität Konstanz, 2010.
Marc Potters, Jean-Philippe Bouchaud, and Dragan Sestovic, Hedged Monte-Carlo: low variance derivative pricing with objective probabilities, Phys. A 289 (2001), no. 3-4, 517–525. MR 1805291, DOI 10.1016/S0378-4371(00)00554-9
A. Richou, étude théorique et numérique des équations différentielles stochastiques rétrogrades, Ph.D. thesis, Université Rennes 1, 2010.
Adrien Richou, Numerical simulation of BSDEs with drivers of quadratic growth, Ann. Appl. Probab. 21 (2011), no. 5, 1933–1964. MR 2884055, DOI 10.1214/10-AAP744
Richard Rouge and Nicole El Karoui, Pricing via utility maximization and entropy, Math. Finance 10 (2000), no. 2, 259–276. INFORMS Applied Probability Conference (Ulm, 1999). MR 1802922, DOI 10.1111/1467-9965.00093
P. Turkedjiev, Numerical methods for backward stochastic differential equations of quadratic and locally Lipschitz type, Ph.D. thesis, Mathematisch-Naturwissenschaftlichen Fakultät II der Humboldt-Universität zu Berlin, available at http://edoc.hu-berlin.de/dissertationen/turkedjiev-plamen-2013-04-30/PDF/turkedjiev.pdf, 2013.
P. Turkedjiev, Two algorithms for the discrete time approximation of Markovian backward stochastic differential equations under local conditions, In revision for Electronic Journal of Probability, available on http://hal.archives-ouvertes.fr/hal-00862848 (2013).
Jianfeng Zhang, A numerical scheme for BSDEs, Ann. Appl. Probab. 14 (2004), no. 1, 459–488. MR 2023027, DOI 10.1214/aoap/1075828058