Source-linked AI summary
A Probabilistic Numerical Method for Fully Nonlinear Parabolic PDEs
Arash Fahim, Nizar Touzi, Xavier Warin
TL;DR
The paper develops a probabilistic numerical scheme for fully nonlinear parabolic PDEs without requiring smooth solutions or backward stochastic differential equations. It proves convergence to the unique viscosity solution under comparison assumptions and analyzes discretization and Monte Carlo approximation errors, while numerical experiments show diffusion choices trade accuracy against computational cost.
Problem
Existing probabilistic schemes require conditional expectations and may involve unavailable gradient and Hessian terms, while convergence without smooth PDE solutions needs justification.
Method
The paper combines Monte Carlo simulation, finite-difference time discretization, and estimators for conditional expectations to construct an implementable scheme.
Results
The scheme converges to the unique bounded viscosity solution under comparison assumptions, with analyses of discretization and Monte Carlo approximation errors.
Takeaways & Limitations
The method provides a probabilistic numerical approach for fully nonlinear PDEs, but diffusion selection affects both numerical quality and computational cost.
Takeaways & Limitations
The paper does not experiment with time- and state-dependent diffusion choices that could follow classical importance sampling.
Abstract
from arXiv · showhide
We consider the probabilistic numerical scheme for fully nonlinear PDEs suggested in \cite{cstv}, and show that it can be introduced naturally as a combination of Monte Carlo and finite differences scheme without appealing to the theory of backward stochastic differential equations. Our first main result provides the convergence of the discrete-time approximation and derives a bound on the discretization error in terms of the time step. An explicit implementable scheme requires to approximate the conditional expectation operators involved in the discretization. This induces a further Monte Carlo error. Our second main result is to prove the convergence of the latter approximation scheme, and to derive an upper bound on the approximation error. Numerical experiments are performed for the approximation of the solution of the mean curvature flow equation in dimensions two and three, and for two and five-dimensional (plus time) fully-nonlinear Hamilton-Jacobi-Bellman equations arising in the theory of portfolio optimization in financial mathematics.
1. Introduction.
The paper develops a probabilistic approximation for fully nonlinear PDEs without backward stochastic differential equations, targeting viscosity solutions that need not be smooth. It proves convergence and error bounds for both discrete-time and implementable Monte Carlo schemes, while identifying restrictions on the underlying diffusion.
- Method: The scheme is presented naturally without backward stochastic differential equations by decomposing it into Monte Carlo, PDE evaluation along diffusion paths, and finite-difference steps.The Monte Carlo step isolates the linear generator of an underlying diffusion, splitting the PDE into linear and nonlinear parts.
- Main results: The analysis targets fully nonlinear PDEs with viscosity solutions rather than requiring smoothness, proving convergence toward the unique viscosity solution and estimating approximation error.The assumptions require a comparison result in the sense of viscosity solutions.
- Discrete-time approximation: The discrete-time approximation converges for general nonlinear PDEs, with error bounds established for a class of Hamilton-Jacobi-Bellman PDEs.This is the paper’s first main result.
- Implementable scheme: The implementable scheme incorporates Monte Carlo error, for which convergence is likewise proved for general nonlinear PDEs and approximation-error bounds are provided for Hamilton-Jacobi-Bellman PDEs.Conditional expectations in the discretization must be further approximated to obtain an implementable scheme.
- Limitations: The convergence results require a uniformly elliptic underlying diffusion, and the diffusion coefficient must satisfy an additional condition described later in the paper.The authors regard uniform ellipticity as potentially relaxable in future work.
2. Discretization.
This section derives the probabilistic numerical scheme directly from the PDE discretization, without using backward stochastic differential equations. Integration by parts removes gradient and Hessian evaluations, yielding a mixed Monte Carlo–finite differences algorithm.
- Direct derivation: The scheme is obtained by direct manipulation of the PDE discretization without appealing to backward stochastic differential equations.The construction uses a Brownian motion, Euler time discretization, conditional expectations, and Riemann-integral approximation.
- Scheme properties: The discretization is well-defined for exponentially growing terminal data g and Lipschitz nonlinearity F, with spatial differentiations interpreted distributionally.Gaussian smoothing provides weak gradients and Hessians, and the exponential-growth property propagates through time steps.
- Integration by parts: Integration by parts eliminates the gradient and Hessian of the next-time value function from the backward iteration.The original algorithm requires Dv_h(t_i+1, ·) and D^2v_h(t_i+1, ·), while Lemma 2.1 replaces them through Gaussian and Hermite-polynomial identities.
- Finite-difference interpretation: The choice of drift and diffusion defines the underlying diffusion, while the remaining nonlinearity is handled by classical finite differences.The diffusion choice is arbitrary for the construction, although later convergence results impose restrictions on the diffusion coefficient.
- Algorithm interpretation: The resulting method is a mixed Monte Carlo–finite differences algorithm, using an underlying diffusion for Monte Carlo and integration by parts for finite-difference approximations.Binomial and trinomial random walks induce centered finite-difference approximations for the gradient and Hessian, respectively.
3. Asymptotics of the discrete-time approximation.
The discrete-time Monte Carlo–Finite Differences scheme converges to the unique bounded viscosity solution under structural assumptions and PDE comparison. For HJB equations, its discretization error has explicit rates under HJB and the stronger HJB+ condition.
- 3. Asymptotics of the discrete-time approximation.: Theorem 3.6 establishes convergence to the unique bounded viscosity solution when Assumption F, coefficient conditions, invertibility of σ, and comparison for bounded functions hold.For every bounded Lipschitz terminal function g, a bounded limit v exists and is unique as a viscosity solution.
- 3. Asymptotics of the discrete-time approximation.: The sufficient condition that the diffusion dominate the nonlinearity in γ may be non-sharp and can yield poor performance when absent.The paper notes uncertainty about necessity, while numerical experiments reveal poor performance without this condition.
- 3. Asymptotics of the discrete-time approximation.: Under HJB, the approximation satisfies v − vh ≤ Ch1/4, while HJB+ provides a two-sided bound involving h1/10.The final condition g is assumed bounded and Lipschitz-continuous, and C > 0 is a constant.
- 3. Asymptotics of the discrete-time approximation.: The rate can improve in specific examples, including the linear case, where the convergence rate is improved to √.The paper also relates the HJB rates to classical spatial discretization rates |∆x|1/2 and |∆x|1/5.
- 3. Asymptotics of the discrete-time approximation.: The discrete approximations remain uniformly bounded in h when g is L∞-bounded and are uniformly Lipschitz in x.A discrete Gronwall argument gives |vh(ti, .)|∞≤CeCT with C independent of h.
2. Assume vh(t + h, .) is Lipschitz with constant Lt+h. Then
Under the stated assumptions, the scheme preserves the terminal condition and yields temporal regularity for v_h. The analysis compares v_h with a monotone transformed scheme, controls their difference by O(h), and derives convergence-rate bounds, including an O(h^1/2) bound in a smooth linear case.
- The scheme preserves the terminal condition as the time step h tends to zero.
- v_h is 1/2-Hölder continuous in time uniformly with respect to h.
- The transformed scheme differs from v_h by O(h), reducing the error analysis to comparing v_h with the solution v.
- The scheme satisfies a comparison estimate that controls interior differences through terminal discrepancies and source-term differences.The bound uses the factor e^β(T−t_i) and the terminal and source discrepancies shown in (3.21).
4. Probabilistic Numerical Scheme.
This section analyzes the implementable probabilistic numerical scheme obtained by estimating conditional expectations with finite samples. It establishes convergence to the unique viscosity solution, an Lp rate, and applications to mean curvature flow.
- Probabilistic Numerical Scheme: The scheme replaces the expectation operator with an estimator based on sample size N, enabling an implementable numerical method.The section investigates how sample size N affects the estimator’s asymptotic behavior.
- Probabilistic Numerical Scheme: Under Assumptions E and F, PDE comparison, and suitable relationships between N and h, the approximation converges to the unique viscosity solution v.The convergence statement is established for almost every underlying sample under the theorem’s assumptions.
- Probabilistic Numerical Scheme: ∥v − v̂h∥p ≤ Ch1/10 provides the stated Lp-bound on the rate of convergence for bounded Lipschitz final conditions.The result applies to the HJB nonlinearity setting with a regression operator satisfying Assumption E and an appropriately chosen sample size Nh.
- Applications: The method is applied to mean curvature flow, including spherical initial data with an explicit solution and a geometric example in space dimension 2.These applications illustrate the Monte Carlo–finite differences scheme in front propagation problems.
5. Numerical Results.
Numerical experiments apply the Monte Carlo–finite differences method to mean curvature flow and fully nonlinear HJB equations. Across examples, scheme 2 generally performs better, while diffusion choice strongly affects accuracy, convergence, and computational cost.
- Numerical schemes: Two representations yield distinct finite-sample schemes after conditional expectations are approximated, and both are evaluated numerically.The schemes are distinguished by the representation used for the Hessian.
- Mean curvature flow: The surface-reconstruction algorithm stops when the location is within 0.01 accuracy and is designed to handle geometries beyond the known spherical case.It uses dichotomic gradient descent based on estimated gradients, although the gradient is unnecessary when the surface is known to remain spherical.
- Diffusion choice: Small diffusion can produce poor or biased results, whereas scheme 2 shows better convergence; large diffusion requires finer meshes and more particles.For σ = 0.2, errors increased as the time step shrank, while the diffusion-dominance condition may be sharp.
- Overall numerical performance: Across experiments, scheme 2 performs better in results and computation time for a fixed particle count, independently of the regression method.A thirty-million-particle experiment converged with low variance toward an exact solution near −0.258, with one calculation taking 5100 seconds for 20 time steps.