Numerical approximation of BSDEs using local polynomial drivers and branching processes

Bruno Bouchard; Xiaolu Tan; Xavier Warin; Yiyi Zou

doi:10.1515/mcma-2017-0116

Published by De Gruyter November 3, 2017

Numerical approximation of BSDEs using local polynomial drivers and branching processes

Bruno Bouchard , Xiaolu Tan , Xavier Warin and Yiyi Zou

From the journal Monte Carlo Methods and Applications

https://doi.org/10.1515/mcma-2017-0116

Showing a limited preview of this publication:

Abstract

We propose a new numerical scheme for Backward Stochastic Differential Equations (BSDEs) based on branching processes. We approximate an arbitrary (Lipschitz) driver by local polynomials and then use a Picard iteration scheme. Each step of the Picard iteration can be solved by using a representation in terms of branching diffusion systems, thus avoiding the need for a fine time discretization. In contrast to the previous literature on the numerical resolution of BSDEs based on branching processes, we prove the convergence of our numerical scheme without limitation on the time horizon. Numerical simulations are provided to illustrate the performance of the algorithm.

Keywords: BSDE; Monte Carlo methods; branching process

MSC 2010: 65C05; 60J60; 60J85; 60H35

Funding statement: Bruno Bouchard and Xavier Warin acknowledge the financial support of ANR project CAESARS (ANR-15-CE05-0024). Xiaolu Tan acknowledges the financial support of the ERC 321111 Rofirm, the ANR Isotace (ANR-12-MONU-0013), and the Chairs Financial Risks (Risk Foundation, sponsored by Société Générale) and Finance and Sustainable Development (IEF sponsored by EDF and CA). Xavier Warin is supported in part by the ANR project CAESARS (ANR-15-CE05-0024). This work has benefited from the financial support of the Initiative de Recherche “Méthodes non-linéaires pour la gestion des risques financiers” sponsored by AXA Research Fund.

A Appendix

A.1 Technical lemmas

Lemma A.1.

The ordinary differential equation η′⁢(t)=∑ℓ=0ℓ∘2⁢Cℓ∘⁢η⁢(t)ℓ with initial condition η⁢(0)=M>0 has a unique solution on [0,h∘] for

(A.1)h∘:=(ℓ∘-1)⁢(1-M)++(1∨M)-(ℓ∘-1)(ℓ∘+1)⁢(ℓ∘-1)⁢2⁢Cℓ∘.

Moreover, it is bounded on [0,h∘] by

(A.2)Mh∘:=max⁡(1,((1∨M)1-ℓ∘+(ℓ∘-1)⁢(1-M)+-h∘⁢ℓ∘⁢(ℓ∘-1)⁢2⁢Cℓ∘)(1-ℓ∘)-1).

Consequently, one has, for all t∈[0,h∘],

(A.3)𝔼⁢[(∏k∈𝒦tMF¯⁢(t-Tk-))⁢(∏k∈𝒦¯t∖𝒦t2⁢Cℓ∘pξk⁢ρ⁢(δk))]≤η⁢(t)≤Mh∘.

Proof.

(i) We first claim that

(A.4)∫MMh∘d⁢y2⁢Cℓ∘⁢(1+y+⋯+yℓ∘)≥h∘.

Then, for every t∈[0,h∘], there is some constant M⁢(t)≤Mh∘<∞ such that

∫MM⁢(t)d⁢y2⁢Cℓ∘⁢(1+y+⋯+yℓ∘)=t=∫0t𝑑s.

This means that (M⁢(t))t∈[0,h∘] is a bounded solution (and hence the unique solution) of η′⁢(t)=∑ℓ=0ℓ∘2⁢Cℓ∘⁢η⁢(t)ℓ with initial condition η⁢(0)=M>0. In particular, it is bounded by Mh∘.

(ii) Let us now prove (A.4). Notice that yk≤1∨yℓ∘ for any y≥0 and k=0,…,ℓ∘. Then it is enough to prove that

(A.5)∫MMh∘(1∧1yℓ∘)⁢𝑑y≥h∘⁢(ℓ∘+1)⁢2⁢Cℓ∘.

By direct computation, the left-hand side of (A.5) equals

(Mh∘-M)⁢𝟏{Mh∘≤1}+((1-M)++1ℓ∘-1⁢((1∨M)1-ℓ∘-Mh∘1-ℓ∘))⁢𝟏{Mh∘>1}.

When h∘ satisfies (A.1), it is easy to check that (A.5) holds true.

(iii) We now prove (A.3). Recall that 𝒦¯tn denotes the collection of all particles in 𝒦¯t of generation n. Set

χtn:=(∏k∈⋃j=1n𝒦tjMF¯⁢(t-Tk-))⁢(∏k∈⋃j=1n(𝒦¯tj∖𝒦tj)2⁢Cℓ∘pξk⁢ρ⁢(δk))⁢(∏k∈𝒦¯tn+1η⁢(t-Tk-)).

Since 𝒦¯tn has only finite number of particles, the random variable χtn is uniformly bounded. Then by exactly the same arguments as in (A.6) and (A.7) below, and by repeating this argument over n, one has

η⁢(t)=M+∫0t∑ℓ=0ℓ∘2⁢Cℓ∘⁢η⁢(s)ℓ⁢d⁢s=𝔼⁢[χt1]=𝔼⁢[χtn] for all ⁢n≥1.

It follows by Fatou’s Lemma that

𝔼⁢[(∏k∈𝒦tMF¯⁢(t-Tk-))⁢(∏k∈𝒦¯t∖𝒦t2⁢Cℓ∘pξk⁢ρ⁢(δk))]=𝔼⁢[limn→∞⁡χtn]≤limn→∞⁡𝔼⁢[χtn]=η⁢(t),

as desired. ∎

For completeness, we provide here the proof the representation formula of Proposition 2.5 and of the technical lemma that was used in the proof of Proposition 2.8.

Proposition A.2.

The representation formula of Proposition 2.5 holds.

Proof.

We only provide the proof on [tNh-1,T], the general result is obtained by induction. It is true by construction when m is equal to 0. Let us now fix m≥1.

First, Lemma A.1 shows that the random variable Vt,xm is integrable.

Next, set (1)+:={(1,j),j≤ℓ∘}∩𝒦¯T and define 𝒦t⁢(1):=𝒦t∩(1)+ and 𝒦¯t⁢(1):=𝒦¯t∩(1)+. For ease of notations, we write Xx:=Xx,((1)). Then, for all (t,x)∈[tNh-1,T]×ℝd,

𝔼⁢[Vt,xm]=𝔼⁢[g⁢(XT-tx)F¯⁢(T-t)⁢𝟏{T(1)≥T-t}]+𝔼⁢[𝟏{T(1)<T-t}⁢∑j=1j∘aj,ξ(1)⁢(XT(1)x)⁢φj⁢(vm-1⁢(t+T(1),XT(1)x))pξ(1)⁢ρ⁢(δ(1))⁢Rt,xm],

where

Rt,xm:=(∏k∈𝒦T-t⁢(1)Gt,x⁢(k))⁢(∏k∈𝒦¯T-t⁢(1)∖𝒦T-t⁢(1)At,xm⁢(k))

satisfies

𝔼[Rt,xm|ℱT(1)]=∏k∈(1)+vm(t+T(1),XT(1)t,x)=[vm(t+T(1),XT(1)x)]ξ(1)

by (2.12). On the other hand, (2.11) and (2.12) imply

(A.6)𝔼⁢[g⁢(XT-tx)F¯⁢(T-t)⁢𝟏{T(1)≥T-t}]=𝔼⁢[g⁢(XT-tx)]

and

𝔼⁢[𝟏{T(1)<T-t}⁢∑j=1j∘aj,ξ(1)⁢(XT(1)x)⁢φj⁢(vm-1⁢(t+T(1),XT(1)x))pξ(1)⁢ρ⁢(δ(1))⁢[vm⁢(t+T(1),XT(1)x)]ξ(1)]

=𝔼⁢[∫0T-t∑j=1j∘aj,ξ(1)⁢(Xsx)⁢φj⁢(vm-1⁢(t+s,Xsx))pξ(1)⁢[vm⁢(t+s,Xsx)]ξ(1)⁢𝑑s]

=𝔼⁢[∫0T-t∑j=1j∘∑ℓ≤ℓ∘aj,ℓ⁢(Xsx)⁢φj⁢(vm-1⁢(t+s,Xsx))⁢[vm⁢(t+s,Xsx)]ℓ⁢d⁢s]

(A.7)=𝔼⁢[∫0T-tfℓ∘⁢(Xsx,vm⁢(t+s,Xsx),vm-1⁢(t+s,Xsx))⁢𝑑s].

Combining the above implies that

vm(t,Xt)=𝔼[g(XT)+∫tTfℓ∘(Xs,vm(s,Xs),vm-1(s,Xs))ds|ℱt],

and the required result follows by induction. ∎

Lemma A.3.

Let (xi,yi)i≤I be a sequence of real numbers. Then

|∏i=1Ixi-∏i=1Iyi|≤∑i∈I(|xi-yi|⁢∏j≠imax⁡(|xj|,|yj|)).

Proof.

It suffices to observe that

∏i=1Ixi-∏i=1Iyi=(x1-y1)⁢∏i=2Ixi+y1⁢(∏i=2Ixi-∏i=2Iyi),

and to proceed by induction. ∎

Proposition A.4.

Let c1,c2,c3≥0, and let (umi)m≥0,i≥0 be a sequence such that

umi≤c1⁢um-1i+c2⁢umi+1+c3 for ⁢m≥1,i<Nh.

Then

umi≤c1m⁢u0i+∑i′=1Nh-i(∑j1=1m∑j2=1j1⋯⁢∑ji′=1ji′-1c1m⁢c2i′⁢u0i+i′)+c3⁢(∑i=1mc1i+∑i′=2Nh-i(∑j1=1m∑j2=1j1⋯⁢∑ji′=1ji′-1c1m-ji′⁢c2i′-1)).

Proof.

We have

umi≤(c1)m⁢u0i+∑j=1m(c1)m-j⁢(c2⁢umi+1+c3).

The required result then follows from a simple induction. ∎

A.2 More on the error analysis for the abstract numerical approximation

The regression error ℰ⁢(𝔼^) in Assumption 2.6 depends essentially on the regularity of vm. Here we prove that vm⁢(t,x) is Hölder in t and Lipschitz in x under additional conditions, and provide some estimates on the corresponding coefficients. Given ϕ:[0,T]×ℝd→ℝ, denote

[ϕ]ti:=sup(t,x)≠(t′,x′)∈[ti,ti+1]×𝐗⁡|ϕ⁢(t,x)-ϕ⁢(t′,x′)||t-t′|12+|x-x′|.

Since (μ,σ) is assumed to be Lipschitz, it is clear that there exists LX>0 such that

∥Xtx-Xt′x′∥𝐋2≤LX⁢(|t′-t|+|x′-x|)

for all (t,x),(t′,x′)∈[0,T]×𝐗.

Proposition A.5.

Suppose that x↦g⁢(x) and x↦fℓ∘⁢(x,y,y′) are uniformly Lipschitz with Lipschitz constants Lg and Lf. Let β and λ1,λ2>0 be such that L2λ22⁢T<1 and β≥2⁢L1+Lf⁢λ12+L2⁢λ22. Then, for all m≥1 and i≤Nh,

[vm]ti≤Lv:=(1+LX)⁢LX⁢(Lg2+Lfβ⁢λ12)⁢eβ⁢T(1-L2λ22⁢T)+2⁢(1+ℓ∘)⁢Cℓ⁢(1∨(Mh∘)ℓ∘)⁢h∘.

Proof.

For ease of notations, we provide the proof for t=0 only.

(i) Let x1,x2∈ℝd, set Ym,1:=vm⁢(⋅,Xx1) and Ym,2:=vm⁢(⋅,Xx2), and denote Δ⁢Ym:=Ym,1-Ym,2 and Δ⁢X:=Xx1-Xx2, where Xx1 (respectively Xx2) denotes the solution of SDE (2.1) with initial condition X0=x1 (respectively X0=x2). By using the same arguments as in the proof of Theorem 2.4, it follows that, for any β≥2⁢L1+Lf⁢λ12+L2⁢λ22, one has

(A.8)𝔼⁢[eβ⁢t⁢(Δ⁢Ytm+1)2]≤𝔼⁢[eβ⁢T⁢(Δ⁢YTm+1)2]+Lfλ12⁢𝔼⁢[∫tTeβ⁢s⁢|Δ⁢Xs|2⁢𝑑s]+L2λ22⁢𝔼⁢[∫tTeβ⁢s⁢(Δ⁢Ysm)2⁢𝑑s]

and then

𝔼⁢[∫0Teβ⁢t⁢(Δ⁢Ytm+1)2⁢𝑑t]≤T⁢𝔼⁢[eβ⁢T⁢(Δ⁢YTm+1)2]+T⁢Lfλ12⁢𝔼⁢[∫0Teβ⁢s⁢|Δ⁢Xs|2⁢𝑑s]+T⁢L2λ22⁢𝔼⁢[∫0Teβ⁢t⁢(Δ⁢Ytm)2⁢𝑑t]

≤T⁢eβ⁢T⁢(Lg2+Lfβ⁢λ12)⁢LX2⁢|x1-x2|2+T⁢L2λ22⁢𝔼⁢[∫0Teβ⁢t⁢(Δ⁢Ytm)2⁢𝑑t].

Since L2λ22⁢T<1, this induces that

𝔼⁢[∫0Teβ⁢t⁢(Δ⁢Ytm+1)2⁢𝑑t]≤T⁢eβ⁢T⁢(Lg2+Lfβ⁢λ12)⁢LX2⁢|x1-x2|21-L2λ22⁢T.

By plugging the above estimates into (A.8), it follows that

(Δ⁢Y0m)2≤L^v2⁢|x1-x2|2 with L^v2:=(Lg2+Lfβ⁢λ12)⁢LX2⁢eβ⁢T1-L2λ22⁢T.

(ii) For the Hölder property of vm, it is enough to notice that for t≤h∘,

|vm⁢(0,x)-vm⁢(t,x)|≤𝔼⁢[|vm⁢(t,Xtx)-vm⁢(t,x)|+∫0t|f⁢(Xsx,Ysm,Ysm-1)|⁢𝑑s]

≤L^v⁢LX⁢t+2⁢(1+ℓ∘)⁢Cℓ⁢(1∨(Mh∘)ℓ∘)⁢t,

where the last inequality follows from the Lipschitz property of vm in x and the fact that Ym is uniformly bounded by Mh∘. We hence conclude the proof. ∎

References

[1] V. Bally and P. Pages, Error analysis of the quantization algorithm for obstacle problems, Stochastic Process. Appl. 106 (2003), no. 1, 1–40. 10.1016/S0304-4149(03)00026-7Search in Google Scholar

[2] C. Bender and R. Denk, A forward scheme for backward SDEs, Stochastic Process. Appl. 117 (2007), no. 12, 1793–1812. 10.1016/j.spa.2007.03.005Search in Google Scholar

[3] M. Bossy, N. Champagnat, H. Leman, S. Maire, L. Violeau and M. Yvinec, Monte Carlo methods for linear and non-linear Poisson–Boltzmann equation, ESAIM Proc. Surv. 48 (2015), 420–446. 10.1051/proc/201448020Search in Google Scholar

[4] B. Bouchard and N. Touzi, Discrete-time approximation and Monte-Carlo simulation of backward stochastic differential equations, Stochastic Process. Appl. 111 (2004), no. 2, 175–206. 10.1016/j.spa.2004.01.001Search in Google Scholar

[5] B. Bouchard and X. Warin, Monte-Carlo valuation of American options: Facts and new algorithms to improve existing methods, Numerical Methods in Finance, Springer Proc. Math. 12, Springer, Heidelberg (2012), 215–255. 10.1007/978-3-642-25746-9_7Search in Google Scholar

[6] H.-J. Bungartz, Concepts for higher order finite elements on sparse grids, Proceedings of the Third International Conference on Spectral and High Order Methods, University of Houston, Houston (1996), 159–170. Search in Google Scholar

[7] H.-J. Bungartz and M. Griebel, Sparse grids, Acta Numer. 13 (2004), 147–269. 10.1017/S0962492904000182Search in Google Scholar

[8] C. de Boor, A Practical Guide to Splines, Appl. Math. Sci. 27, Springer, New York, 1978. 10.1007/978-1-4612-6333-3Search in Google Scholar

[9] N. El Karoui, S. Peng and M. C. Quenez, Backward stochastic differential equations in finance, Math. Finance 7 (1997), no. 1, 1–71. 10.1111/1467-9965.00022Search in Google Scholar

[10] S. M. Ermakov, V. V. Nekrutkin and A. S. Sipin, Random Processes for Classical Equations of Mathematical Physics, Math. Appl. (Soviet Series) 34, Kluwer Academic Publishers, Dordrecht, 1989. 10.1007/978-94-009-2243-3Search in Google Scholar

[11] T. Gerstner and M. Griebel, Dimension-adaptive tensor-product quadrature, Computing 71 (2003), no. 1, 65–87. 10.1007/s00607-003-0015-5Search in Google Scholar

[12] H. Gevret, J. Lelong and X. Warin, The StOpt library documentation, preprint (2016), https://hal.archives-ouvertes.fr/hal-01361291. Search in Google Scholar

[13] H. Gevret, J. Lelong and X. Warin, The StOpt library, preprint, https://gitlab.com/stochastic-control/StOpt. Search in Google Scholar

[14] E. Gobet, J.-P. Lemor and X. Warin, A regression-based Monte Carlo method to solve backward stochastic differential equations, Ann. Appl. Probab. 15 (2005), no. 3, 2172–2202. 10.1214/105051605000000412Search in Google Scholar

[15] M. Griebel, Adaptive sparse grid multilevel methods for elliptic PDEs based on finite differences, Computing 61 (1998), no. 2, 151–179. 10.1007/BF02684411Search in Google Scholar

[16] P. Henry-Labordère, Cutting CVA’s complexity, Risk 25 (2012), no. 7, 67–67. Search in Google Scholar

[17] P. Henry-Labordere, N. Oudjane, X. Tan, N. Touzi and X. Warin, Branching diffusion representation of semilinear PDEs and Monte Carlo approximation, preprint (2016), https://arxiv.org/abs/1603.01727. 10.1214/17-AIHP880Search in Google Scholar

[18] 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), no. 2, 1112–1140. 10.1016/j.spa.2013.10.005Search in Google Scholar

[19] J. Ma and J. Zhang, Representation theorems for backward stochastic differential equations, Ann. Appl. Probab. 12 (2002), no. 4, 1390–1418. 10.1214/aoap/1037125868Search in Google Scholar

[20] H. P. McKean, Application of Brownian motion to the equation of Kolmogorov–Petrovskii–Piskunov, Comm. Pure Appl. Math. 28 (1975), no. 3, 323–331. 10.1002/cpa.3160280302Search in Google Scholar

[21] E. Pardoux and S. G. Peng, Adapted solution of a backward stochastic differential equation, Systems Control Lett. 14 (1990), no. 1, 55–61. 10.1016/0167-6911(90)90082-6Search in Google Scholar

[22] A. Rasulov, G. Raimova and M. Mascagni, Monte Carlo solution of Cauchy problem for a nonlinear parabolic equation, Math. Comput. Simulation 80 (2010), no. 6, 1118–1123. 10.1016/j.matcom.2009.12.009Search in Google Scholar

[23] A. V. Skorokhod, Branching diffusion processes, Theory Probab. Appl. 9 (1964), no. 3, 445–449. 10.1137/1109059Search in Google Scholar

[24] X. Warin, Adaptive sparse grids for time dependent Hamilton–Jacobi–Bellman equations in stochastic control, preprint (2014), https://arxiv.org/abs/1408.4267. Search in Google Scholar

[25] X. Warin, Some non-monotone schemes for time dependent Hamilton–Jacobi–Bellman equations in stochastic control, J. Sci. Comput. 66 (2016), no. 3, 1122–1147. 10.1007/s10915-015-0057-9Search in Google Scholar

[26] S. Watanabe, On the branching process for Brownian particles with an absorbing boundary, J. Math. Kyoto Univ. 4 (1965), 385–398. 10.1215/kjm/1250524667Search in Google Scholar

Received: 2017-7-28

Accepted: 2017-10-5

Published Online: 2017-11-3

Published in Print: 2017-12-1

Numerical approximation of BSDEs using local polynomial drivers and branching processes

Abstract

A Appendix

A.1 Technical lemmas

Lemma A.1.

Proof.

Proposition A.2.

Proof.

Lemma A.3.

Proof.

Proposition A.4.

Proof.

A.2 More on the error analysis for the abstract numerical approximation

Proposition A.5.

Proof.

References

Journal and Issue

Articles in the same Issue