Overcoming the curse of dimensionality in the numerical approximation of parabolic partial differential equations with gradient-dependent nonlinearities

Introduction

Partial differential equations (PDEs) play a prominent role in the modeling of many real world phenomena. For instance, PDEs appear in financial engineering in models for the pricing of financial derivatives, PDEs emerge in biology in models that aim to better understand biodiversity in ecosystems, PDEs such as the Schrödinger equation appear in quantum physics to describe the wave function of a quantum-mechanical system, PDEs are used in operations research to characterize the value function of control problems, PDEs provide solutions for backward stochastic differential equations (BSDEs) which itself appear in several models from applications, and stochastic PDEs such as the Zakai equation or the Kushner equation appear in nonlinear filtering problems to describe the density of the state of a physical system with only partial information available. The PDEs in the above named models contain often nonlinearities and are typically high-dimensional, where, e.g., in the models from financial engineering the dimension of the PDE usually corresponds to the number of financial assets in the associated hedging or trading portfolio, where, e.g., in models that aim to better understand biodiversity the dimension of the PDE corresponds to the number of traits of the considered species in the considered ecosystem, where, e.g., in quantum physics the dimension of the PDE is, loosely speaking, three times the number of electrons in the considered physical system, where, e.g., in optimal control problems the dimension of the PDE is determined by the dimension of the state space of the control problem, and where, e.g., in nonlinear filtering problems the dimension of the PDE corresponds to the degrees of freedom in the considered physical system.

The remainder of this article is organized as follows. In Section 2 we establish a few identities and upper bounds for certain iterated deterministic integrals. The results of Section 2 are then used in Section 3 in which we introduce and analyze the considered MLP approximation methods. In Section 4 we establish suitable a priori bounds for exact solutions of PDEs of the form (2). In Section 5 we combine the findings of Sections 3 and 4 to etablish in Theorem 5.2 below the main approximation result of this article.

Analysis of certain deterministic iterated integrals

In this section we establish in Corollary 2.5 below an upper bound for products of certain independent random variables. Corollary 2.5 below is a central ingredient in our error analysis for MLP approximations in Section 3 below. Our proof of Corollary 2.5 employs a few elementary identities and estimates for certain deterministic iterated integrals which are provided in Lemma 2.1, Lemma 2.2, and Corollary 2.3 below.

Induction thus proves (5). This completes the proof of Lemma 2.1. ∎

This establishes (8). The proof of Lemma 2.2 is thus completed. ∎

2 Estimates for certain deterministic iterated integrals

First, observe that Wendel’s inequality for the gamma function (see, e.g., Wendel and Qi [53, Section 2.1]) ensures that for all $x\in(0,\infty)$, $s\in$ it holds that

This establishes (12). The proof of Corollary 2.3 is thus completed. ∎

3 Estimates for products of certain independent random variables

This together with (18) proves (17). The proof of Lemma 2.4 is thus completed. ∎

This establishes (24) in the base case $k=j+1$. For the induction step $\{2,3\ldots,j+1\}\ni k+1\rightsquigarrow k\in\{1,2,\ldots,j\}$ assume that there exists $k\in\{1,2,\ldots,j\}$ which satisfies that

This completes the induction step. Induction hence proves (24).

Inequality (29), Corollary 2.3 (applied with $\beta=\frac{p}{2}$ and $\gamma=p-1$ in the notation of Corollary 2.3) together with $\frac{p}{2}\in[\alpha(p-1),\alpha(p-1)+1]$, and the fact that $(\frac{p}{2}-\alpha(p-1))(1-(\frac{p}{2}-\alpha(p-1)))\leq\frac{1}{4}$ show that

This together with $\alpha(p-1)-\frac{p}{2}+1\leq p-1-\frac{p}{2}+1=\frac{p}{2}$ implies (22). The proof of Corollary 2.5 is thus completed. ∎

Full-history recursive multilevel Picard approximation methods

In this section we introduce and analyze a class of new MLP approximation methods for nonlinear heat equations with gradient-dependent nonlinearities. In the main result of this section, Proposition 3.5 in Subsection 3.3 below, we provide a detailed error analysis for these new MLP approximation methods. We will employ Proposition 3.5 in our proofs of the approximation results in Section 5 below (cf. Corollary 5.1, Theorem 5.2, and Corollary 5.4 in Section 5 below).

2 Properties of MLP approximations

This establishes Item (vi). The proof of Lemma 3.2 is thus completed. ∎

it holds for all $\theta\in\Theta$, $q\in[1,\infty)$, $\nu\in\{1,2,\ldots,d+1\}$ that

The Cauchy-Schwarz inequality, the Lipschitz property (31) of $g$, Jensen’s inequality, and the scaling property of Brownian motion yield for all $\theta\in\Theta$, $q\in[1,\infty)$, $\nu\in\{1,2,\ldots,d+1\}$ that

Observe that (LABEL:eq:def:U) and Jensen’s inequality ensure that for all $\theta\in\Theta$, $q\in[1,p)$, $t\in[0,T)$, $s\in[t,T)$, $\nu\in\{1,2,\ldots,d+1\}$ it holds that

This, Hutzenthaler et al. [39, Corollary 2.5] together with Lemma 3.2, Item (i), and the induction hypothesis (46) yield for all $\theta\in\Theta$, $q\in[1,p)$, $t\in[0,T)$, $\nu\in\{1,2,\ldots,d+1\}$ that

Furthermore, Jensen’s inequality, the Lipschitz property (31) of $f$, (LABEL:b38:eq3), and assumption (39) yield that for all $\theta\in\Theta$, $q\in[1,p)$, $t\in[0,T)$ it holds that

This, (LABEL:eq:prepa), and assumption (39) implies that for all $\theta\in\Theta$, $q\in[1,p)$, $t\in[0,T)$, $\nu\in\{1,2,\ldots,d+1\}$ it holds that

This and (LABEL:b38:eq3) finish the induction step. Induction hence proves Item (ii).

This establishes Item (iii). The proof of Lemma 3.3 is thus completed. ∎

3 Error analysis for MLP approximations

proves (LABEL:eq:estimate.L2error). This finishes the proof of Lemma 3.4. ∎

and assume for all $s\in(0,1)$ that $\rho(s)=\frac{1-\alpha}{s^{\alpha}}$. Then

Throughout this proof let $C_{1}\in[0,\infty)$ satisfy

Note that the fact that $p\in[2,\infty)$ and the fact that $\alpha\in\left(\frac{p-2}{2(p-1)},\frac{p}{2(p-1)}\right)$ imply that $\frac{p}{2}\in[\alpha(p-1),\alpha(p-1)+1]$ and that $\alpha\in(0,1)$. This, (67), (31), and Corollary 2.5 (with $p=2$ in the notation of Corollary 2.5) show that for all $j\in\{0,1,\ldots,n-1\}$, $\nu_{1},\nu_{2},\ldots,\nu_{j}\in\{1,2,\ldots,d+1\}$ it holds that

The facts that $\Gamma\left(\frac{p+1}{2}\right)\geq\Gamma\left(\frac{3}{2}\right)=\frac{\sqrt{\pi}}{2}$, that $\frac{2(p-1)}{p}\geq 1$, and that $\alpha\leq 1$ prove that

Corollary 2.5 and the facts that $p\geq 2$ and $\alpha>\frac{p-2}{2(p-1)}$ prove that

Moreover, it holds for all $r\in[1,2)$ that

Combing Lemma 3.4, (70), (72), and (73) proves that

Combining this with (LABEL:eq:glob.error.aux1) proves that

This and the facts that $2\sqrt{C_{1}}\|L\|_{1}\leq 2\sqrt{C_{1}}\max\{1,\|L\|_{1}\}\leq C$, $p\geq 2$, and $C\geq 1$ imply that

Combining (LABEL:eq:glob.error.aux2), (80), and (81) shows that

This completes the proof of Proposition 3.5. ∎

Regularity analysis for solutions of certain differential equations

The error analysis in Subsection 3.3 above provides upper bounds for the approximation errors of the MLP approximations in (LABEL:eq:def:U). The established upper bounds contain certain norms of the unknown exact solutions of the PDEs which we intend to approximate; see, e.g., the right-hand side of (LABEL:eq:ub_error_thm) in Proposition 3.5 in Subsection 3.3 above for details. In Lemma 4.2 below we establish suitable upper bounds for these norms of the unknown exact solutions of the PDEs which we intend to approximate. In our proof of Lemma 4.2 we employ certain a priori estimates for solutions of BSDEs which we establish in the essentially well-known result in Lemma 4.2 below (see, e.g., El Karoui et al. [19, Proposition 2.1 and Equation (2.12)] for results related to Lemma 4.2 below).

Next (86), (87), and a telescoping sum imply for all $s\in[t,T]$ that

Next note that assumption (83) ensures that $\sup_{s\in[t,T]}\|B_{s}\|^{2}\leq\sum_{j=2}^{d+1}(L_{j})^{2}$. This and an exponential martingale argument imply that

This proves (85). The proof of Lemma 4.1 is thus completed. ∎

2 Regularity analysis for solutions of partial differential equations (PDEs)

This, (113), (114), (115), (116), and Lemma 4.1 prove that

The proof of Lemma 4.2 is thus completed. ∎

Overall complexity analysis for MLP approximation methods

and let $\mathfrak{C}\in[0,\infty)$ be the real number given by

If $N>2$ it follows from (137), (136) and (138) that

Combining this with (139) and (140) proves that

This establishes (LABEL:eq:fin_cor). The proof of Corollary 5.1 is thus completed. ∎

2 Qualitative complexity analysis for MLP approximation methods

Throughout this proof let $p=\frac{2\alpha}{\beta+2\alpha-1}$. Note that the fact that $0<\beta<1-\alpha$ ensures that $p>\frac{2\alpha}{1-\alpha+2\alpha-1}=2$. Moreover, observe that the fact that $p=\frac{2\alpha}{\beta+2\alpha-1}$ demonstrates that

If $\alpha>\frac{1}{2}$, then it holds that $1-\alpha<\frac{p}{2(p-1)}$. Moreover, if $\alpha>\frac{1}{2}$ the fact that $\beta>0$ implies that $p<\frac{2\alpha}{2\alpha-1}$ and hence $1-\alpha>\frac{p-2}{2(p-1)}$. If $\alpha<\frac{1}{2}$, then it holds that $1-\alpha>\frac{p-2}{2(p-1)}$. Moreover, if $\alpha<\frac{1}{2}$ the fact that $\beta>\frac{1-2\alpha}{1-\alpha}$ implies that $p<\frac{2\alpha}{\frac{1-2\alpha}{1-\alpha}+2\alpha-1}=\frac{1-\alpha}{\frac{1}{2}-\alpha}$ and hence $1-\alpha<\frac{p}{2(p-1)}$. Furthermore, it holds that $\frac{p-2}{2(p-1)}<\frac{1}{2}<\frac{p}{2(p-1)}$. To summarize, it holds that

proves (148). The proof of Theorem 5.2 is thus completed. ∎

it holds for all $i\in\{1,2,\ldots,d\}$ that

Note that for all $i\in\{1,2,\ldots,d\}$ it holds that

This proves item (i). Moreover, observe that item (i) establishes item (ii). The proof of Lemma 5.3 is thus completed. ∎

This project has been partially supported by the Deutsche Forschungsgesellschaft (DFG) via RTG 2131 High-dimensional Phenomena in Probability – Fluctuations and Discontinuity and via research grant HU 1889/6-1.

References