| In this dissertation, numerical algorithms for solving forward backward stochastic differential equations (FBSDEs) and forward backward stochastic differential equations with jumps (FBSDEJs) are systematically studied, especially on the highly accurate ones. Since the original work [54], in which Pardoux and Peng obtained the existence and u-niqueness of the adapted solution for nonlinear backward stochastic differential equation (BSDE), FBSDEs have been extensively investigated by many researchers, both in the-oretical and practical areas. Coincidentally, Duffle and Epstein [26] also independently introduce a special type of BSDE in their economic study. Shortly after in [58], Peng in-troduced the so-called nonlinear Feynman-Kac formula, which established a relationship between the parabolic partial differential equations (PDEs) and FBSDEs. According to this famous formula, a branch of numerical methods for FBSDEs are carried out through a PDE approach. On the other hand, another branch of numerical methods are devel-oped from analysing and discretizing the FBSDEs themselves, which is also the focus of this article.First of all, inspired by the prediction-correction method, we propose explicit numer-ical schemes for solving both FBSDEs and FBSDEJs in decoupled case by introducing a new Gaussian process and a new compensated Poisson random measure. For these two explicit schemes, error estimates and convergence analysis are established. Then we rigorously prove that the accuracy of the explicit schemes can be of second order. From our analysis, however, to achieve high-order convergence for the numerical solu-tions of BSDE, we have to guarantee the corresponding numerical schemes for solving forward stochastic differential equation (SDE) or stochastic differential equation with jumps (SDEJ) also attain high-order convergence in the weak sense. These requirements of high-order numerical methods for SDE or SDEJ bring enormous difficulties to the applications of the proposed schemes, especially in the high-dimensional case. That’s because, on one hand, the high-order schemes for solving SDE or SDEJ are very compli-cated and difficult to practice in high-dimensional case. On the other hand, people are only interested in the solutions of BSDE in most practical problems. The SDE or SDEJ are just models describing the state variables such as the stock prices. Therefore, the high-order numerical schemes for SDE or SDEJ cost us too much but benefit us little in return. Thus we are interested in the following question,Can we still expect a high-order numerical solution of BSDE if we numerically solve the corresponding forward SDE or SDEJ by some simple numerical schemes? As our research continues, we find that the generator of diffusion processes has a kind of local property. Then by carefully approximating the generators in the reference ordinary differential equations (ODEs) which we obtained from the BSDE, we propose a new kind of multi-step schemes for solving coupled FBSDEs. The most important feature of the multi-step schemes is that the numerical solutions of BSDE can achieve high-order convergence when the Euler method is used to solve the corresponding forward SDE. Such results are obviously promising because the Euler method for SDE is the simplest scheme and can be easily extended to the high-dimensional case. For the generator of jump-diffusion processes, the similar local property can be obtained, which inspire us to propose a kind of multi-step schemes for solving coupled FBSDEJs. In these multi-step schemes, the numerical solutions of BSDEJ are able to remain high-order convergence, when the forward SDEJ is numerically solved by the Euler scheme with only one possible jump. Thus we give a positive answer to the above question.The features of the proposed multi-step schemes laid foundations for developing high-order numerical schemes for high-dimensional FBSDEs. The remaining issue is to build an efficient spatial discretization and deal with the related high-dimensional inter-polations and integrations. To accomplish these goals, we use the sparse grid method to discretize the high-dimensional space and the sparse grid quadrature rule to approximate the high-dimensional integrations. For the associated high dimensional interpolations, we adopt a spectral expansion of functions in polynomial spaces with respect to the spatial variables, and use the sparse grid approximations to recover the expansion coef-ficients. The FFT algorithm is used to speed up the recovery procedure, and the entire algorithm admits efficient and high accurate approximations in high-dimensions. With all the above efforts, we propose an efficient fully-discrete high-order numerical algorith- m for solving high-dimensional FBSDEs and carry out several numerical experiments to demonstrate the accuracy and efficiency.At last, we investigate numerical algorithms for solving stochastic optimal control in an FBSDE approach. According to the generalized stochastic maximum principle, we convert the stochastic optimal control problem into a system of coupled FBSDEs with an external optimality condition. Then by considering the algorithms for optimization and FBSDEs, we introduce a general algorithm for solving stochastic optimal control problems. According to the features of the problem, it is difficult to obtain a high-order approximation for the state equation (SDE). So we pick the proposed multi-step schemes, which are able to achieve high-order convergence relying on the Euler approximation for forward SDE, and build a second-order algorithm without any refinement of the time partition.The main innovations of this thesis could be summarized as follows.1. Inspired by the prediction-correction method, explicit schemes for solving decoupled FBSDEs and FBSDEJs are proposed, which avoid the iterative procedures for solving Yt and are rigorously proved to be of second order.2. New kinds of multi-step schemes for solving coupled FBSDEs and FBSDEJs are developed. By investigating the FBSDEs and FBSDEJs in a brand new way, we obtain several first order ODEs as our reference equations. Taking advantage of the local properties of diffusion processes and jump-diffusion processes, we are able to achieve high-order convergence for the solutions of BSDE when the Euler method is used to solve the associated forward SDE or SDEJ.3. Based on the new multi-step scheme for solving FBSDEs, we introduce a high-order algorithm for solving high-dimensional FBSDEs by using the spectral sparse grid method and the corresponding fast transform.4. Propose a general algorithm for solving stochastic optimal control problems in an FBSDE approach. Then by carefully selecting the numerical algorithm for solving FBSDEs, we build a second-order algorithm, which performs well in many financial and economic problems.In what follows, we briefly introduce the main contents of each chapter.In Chapter 1, we review our research background and motivations for developing numerical methods for solving FBSDEs and FBSDEJs.In Chapter 2, some basic knowledge about FBSDEs and FBSDEJs are introduced as our preliminaries.In this work, we consider the following FBSDEs on a filtered complete probability space (Ω, F, F, P) with F={Ft}0≤<≤T, where Ft is the natural filtration of the standard d-dimensional Brownian motion Wt=(Wt1,..., Wtd)T. where t ∈ [0,T] with T> 0 being the deterministic terminal time, ξ∈FT is the terminal condition for BSDE, b:Ω× [0, T] ×Rq×Rp×Rp×R[×d'Rq and σ:Ω× [0,T] × Rq×Rp×Rp×d'Rq×d are referred to the drift and diffusion coefficients respectively,f:Ω×[0.T] ×Rq×Rp×Rp×d'Rp is called the generator of BSDE and (Xt, Yt, Zt):[0,T]×Ω'Rq×Rp×RP×d is the unknown. A triple (Xt,Yt,Zt) is called an L2-adapted solution of the FBSDEs(37) if it is Ft-adapted, square integrable, and satisfies (37). The FBSDEs (37) is called decoupled if b and σ are independent of Yt and Zt.For the FBSDEJs, we introduce a new filtered probability space (Ω,F,F,P).The filtration F={Ft}0≤t≤T is assumed to be complete, right continuous and generated by the following two murually independent stochastic processes,1.{Ws},0≤s≤t:the d-dimensional Brownian motion.2.μ(A, [0, s]),0≤s≤t, A∈ε:a Poisson random measure on E×[0, T], where ε is the Borel set of E.Then we introduce the FBSDEJs on (Ω,F,F,P), where (?)s:=(Xs, Ys, Zs, Γs) is the unknown, withΓt=∫EUt(e)η(e)λ(de) and η:E'R being a bounded function.In Chapter 3, we propose the prediction-correction schemes for solving FBSDEs and FBSDEJs, and rigorously prove the convergence rates of the schemes can be second-order.In the first place, we introduce a new stochastic process △Wtn,s, Then according to the reference equations we derived, we propose the following prediction-correction scheme for solving FBSDEs. Scheme 1. Given the random variables X0, YN and ZN, for n=N-1,...,1,0 solve for the random variables Yn and Zn from By the convergence analysis, we obtain the following theorem. Theorem 1. Under some regular assumptions, for sufficiently small time step △t, we have the estimate for 0≤n≤N-1, where β and γ depend on the convergence rate of the SDE scheme in the weak sense, C is a positive constant depending on c0 and L, C1 is a positive constant depending on c0, T and L, C2 is also a positive constant depending on c0, T, L, K, the initial value of X0, and the upper bounds of the derivatives of b, σ, f and φ.From this theorem, we can see that if the numerical schemes for solving SDE can achieve second-order convergence (in weak sense), our proposed scheme is second-order for solv-ing Yt and Zt.Analogously for the FBSDEJs, we need another stochastic process △μtn,s* besides where p(r)= 2-3/△tn(r-tn). Then we obtain three reference equations by analysing the FBSDEJs, from which we propose the following scheme. Scheme 2. Assume that the initial condition X0 of the forward SDEJ and the terminal condition (YN, ZN,ΓN) of the BSDEJ are known. Then, for n=N-1,...,0, solve (Yn,Zn,Γn) by By analysing the truncation errors in the above scheme, we get the following theorem. Theorem 2. Under some assumptions for the coefficients of FBSDEJs, for sufficiently small time step At, we have where α,β,γ depend on the convergence rate of the SDEJ scheme in the weak sense, C> 0 depends only on c0 and L, C1> 0 depends on c0, T and L, and C2> 0 depends on c0, T, L, K, X0 and the upper bounds of the derivatives of b, σ, c, f and φ. Similarly, we can draw the conclusion that if we want the solutions of BSDEJ attain second-order convergence, the numerical schemes we used for the forward SDEJ have to be second-order in the weak sense. Although the numerical schemes for solving SDE and SDEJs have been intensively studied for decades, the high-order schemes are still very complicated and expensive to practice, especially in the high-dimensional case. Particularly for the SDEJ, we have to consider more and more possible jumps as the demanded order of convergence increasing, which makes our schemes more complicated. The theoretical results and numerical schemes proposed in this chapter have are of great significance in the following aspects.1. We build two second-order numerical schemes for solving FBSDEs and FBSDEJs, which are both totally explicit in solving Yt. For most of other high-order numerical schemes, they require some iterative procedure to solve Yt from a nonlinear equation. The proposed explicit schemes allow us to get rid of the iterative procedure and make our algorithm more effective.2. Through the error analysis, we rigorously prove the explicit schemes can achieve second-order convergence, which highly rely on a second-order numerical scheme (in weak sense) for forward SDE. This dependency appears in almost all the numer-ical schemes for FBSDEs and FBSDEJs. To deal with this problem, we have to investigate the equations and propose schemes in a different perspective.In Chapter 4, we study the FBSDEs in a brand new way. According to the two reference ODEs we obtain, we propose a new kind of multi-step schemes for solving coupled FBSDEs. Motivated by the local property of the generator of diffusion processes, In these schemes, the Euler method is used to solve the forward SDE, but the numerical solutions of the BSDE are still of high-order accuracy.First of all, we introduce the definition of the generator of diffusion processes. Let the diffusion process Xt satisfy the following SDE,Then we define the generator of Xt on g as follows,The generator Atx has the following property, where L0 is defined as,From the above analysis, we have the following theorem. Theorem 3. Let to< t be a fixed time, and x0∈R9 be a fixed space point. If Moreover, the following identity holds where Xt is a diffusion process satisfyingFrom the above theorem, we can see the value of Atxf(t, x) only relies on the values of the derivatives of b, σ and f at (t,x), which is the reason we call this property a local one. Combined this local property and the following two reference ODEs we derive, after we introduce the space discretization Dhn for each time level tn, we propose our multi-step scheme for coupled FBSDEs.From our numerical experiments, we conclude that our schemes is stable for 1≤k≤6. And the k-step scheme can achieve a k-order convergence. Our research in this chapter possesses the following innovations,1. We obtain two reference ODEs by investigating the FBSDEs in a brand new way. Then we establish the equivalence relation between the first-order derivative term in the ODEs and the generator of diffusion processes.2. According to the local property of the generator of diffusion processes, we have more options for the SDE schemes in the approximation of the derivative, among which the Euler scheme is the simplest one. This feature makes us successfully get the high-order convergence for the BSDE solutions, while the Euler scheme is applied to the forward equation. Numerical schemes for FBSDEs with this kind of property are proposed for the first time and of course very promising.In Chapter 5, by the local property of the generator of jump-diffusion processes, we develop a kind of multi-step schemes for solving FBSDEJs. Premised on a high-order convergence for the solutions of BSDEJ, we are able to use not only the Euler scheme for the SDEJ, but also the Euler scheme with only one jump.Let Xt be an Rd valued jump-diffusion process, for a given measurable function g: [0,T]×Rd ' R, the generator Atx of Xt on g is defined by,From our analysis, for the following two processes,their generators on g are the same, i.e.,Based on the above results and the three reference ODEs, we propose our multi-step schemes for solving FBSDEJs.Scheme 4. For a fixed positive integer k≤6, assume that YN-i and ZN-i are known for i=0,1,..., k-1. Then let n=N-k,...,0 and numerically solve Yn=Yn(Xn), Zn=Zn(Xn) and Γn= Γn(Xn) through the following equations,From the results of several numerical experiments, we conclude that the proposed schemes are stable and of high-order convergence. And the multi-step schemes also perform well for nonlocal problems with a singular kernel. The significance of the results in this chapter is listed in the following,1. The numerical schemes proposed in this chapter enable us to get a high-order conver-gence for the solutions of BSDEJs, while the Euler method with one jump is applied to solve the forward SDEJ.2. FBSDEJs have important applications in the nonlocal problems. The multi-step schemes in this chapter also maintain high-order convergence when dealing with nonlocal problems with a singular kernal.In Chapter 6, based on the multi-step schemes for FBSDEs proposed in Chapter 4, we construct an efficient algorithm for solving high-dimensionalFBSDEs by means of spectral sparse grid method. By carefully selecting the basis functions and sparse grid points, the fast transform for recovering the expansion coefficients improve our algorithm’s efficiency a lot.In this chapter, we give a basic introduction for constructing high-dimensional sparse grids by the idea in [72]. We start with considering a sequence of grids{χi}i=1∞ in R, Then we build the q-dimensional sparse grid via where p≥q is an integer, i=(i1,...,ig) is a multi index. The sequence of one-dimensional grids {χi}i=1∞ is called nested if it satisfies χ1 (?) χ2…(?)χk(?)…. To approximate the functions in high-dimensional space, we choose a set of basis functions{φ(x)k}k=0∞ which are usually orthogonal polynomials. Then for nested grids, a set of basis functions {φ(x)k}k=0∞ is called hierarchical if Thus, in case a nested sparse grid and the corresponding hierarchical bases are used, we can build the following interpolation operator for functions f in R9, When we use the nested sparse grids and hierarchical basis functions, the following fast transform can be used to obtain the expansion coefficients,{bk}k∈Iqp.-Algorithm 1. Fast transform on sparse gridBased on this fast transform, we get an efficient approximation for high-dimensional functions. Then combined with the Gauss quadrature rule on sparse grid, we propose the following numerical algorithm for solving high-dimensional FBSDEs.By this algorithm, we numerically solve many examples including a 6-dimensional cou-pled FBSDEs. The numerical results confirm the efficiency and high-order convergence of the proposed algorithm. There are some innovations for the research in this chapter,1. For the first time, the spectral sparse grid method is applied to solve high-dimensional FBSDEs. When we use the nested sparse grid and hierarchical basis functions, the fast transforms increase the efficiency of our algorithm a lot.2. It is the first time we obtain a high-order numerical algorithms for solving high-dimensional FBSDEs. Although Monte Carlo or least square method is a good way to deal with the curse of dimensionality, its low accuracy becomes a great obstacle to build a high-order algorithm. On the other hand, the only feasible numerical scheme for high-dimensional SDE is the Euler scheme in nowadays. Therefore, the new kind of multi-step schemes proposed in Chapter lays a solid foundation for our research.Finally in Chapter 7, we convert the stochastic optimal control prob-lem into a system of FBSDEs with an external optimality condition by the stochastic maximum principle. Then we develop a general algorithm for solv-ing this FBSDEs system. By selecting the algorithms for optimization and the numerical schemes for FBSDEs, we obtan a second-order algorithm for stochastic optimal control problems.In this chapter, we consider the stochastic optimal control problem with the follow- ing state equation, where Wt=(W1,t..., Wm,t)T is a d-dimensional Brownian motion, at is the control pro-cess. Our objective is to minimize the following cost functional J(α) over the admissible control set u, where the control In this work, at is assumed to be a function of the state variable, i.e., αt=α(t,Xt), which is reasonable and practical in many applications. An admissible control α. is called optimal, usually denoted by α*, if it makes the cost functional J(α.) attains its minimum value, i.e., According to the generalized stochastic maximum principle, we convert the above s-tochastic optimal control problem into the following FBSDEs system with an external optimality condition. with the optimality condition,To propose a algorithm for solving this FBSDEs system, we need both the algorithms for optimization and numerical schemes for FBSDEs, which are expressed by the two mappings ALG.OPTIM and ALG.FBSDE respectively. Based on this two mappings, we propose a general algorithm for solving the stochastic optimal control problems. In this general algorithm, ρl is a positive real number changing over l. Pn, Qn, Yn, Zn and αn* are the numerical solutions of Ptn, Qtn, Qtn, Ztn and αln* respectively. Pn+, Qn+, Yn+, Zn+ and αn+* are the known conditions defined as Then our remaining work is to choose the algorithms for optimization and FBSDEs to build a specific algorithm for stochastic optimal control problems.In stochastic optimal control problems, the drift and diffusion coefficients of the state equation both contain αt, which is an unknown process. This feature makes it dif-ficult to use high-order schemes for solving the state equation. Therefore, if we want to obtain a high-order convergence for at and Yt, we have to choose some FBSDEs schemes which do not rely on a high-order approach for the forward SDE. The multi-step schemes proposed in Chapter 4 possess this property, which is a good choice for stochastic op-timal control problems. For the algorithm for optimization, we use the simple gradient projection method. Let the mapping ALG.FBSDE.Ms-k and ALG.OPTIM.GP denote our k-step scheme for FBSDEs and gradient projection algorithm for optimization respec-tively. Then we get the following second-order algorithm for stochastic optimal control problems.In this algorithm ALG.FBSDE.Eu stands for the Euler method for FBSDEs, which is used in our first solving step to get the terminal condition for ALG.FBSDE.Ms-2. This algorithm also has a good performance dealing with practical problems in finance and economics. The innovations of our research in this chapter can be summarized as follows.1. It is the first time that a. general algorithm is proposed for solving stochastic optinial control problems in an FBSDEs approach. In this algorithm, we can choose different algorithms for optimizations and different numerical schemes for FBSDEs according to the features of different problems.2. According to the features of stochastic optimal control problems, we choose the multi-step scheme proposed in Chapter 4 for solving the FBSDEs, which makes our algorithm attain second-order convergence. The second-order algorithm is a complete one because we don’t require extra terminal conditions to initialize or a finer mesh on the time interval. |
PDF Full Text Request