Numerical methods for high-dimensional optimal stopping problems

Abstract

Optimal stopping problems aim to determine the best time to stop sequentially observed stochastic processes, which have broad applications in mathematical finance. The high dimensionality of underlying processes brings great computational challenges with traditional methods due to the curse of dimensionality. This thesis collects my works on grid-based, probabilistic, and primal-dual methods for optimal stopping.

For moderately high-dimensional problems, sparse grid polynomial interpolation is employed. This approach proposes a novel transformation with bubble functions to tackle difficulties with unbounded domains. A by-product is reducing the computational complexity of boundary points that account for the majority of interpolation points in a hypercube. The interpolation functions have been proven to have bounded mixed derivatives up to certain orders, thereby providing theoretical guarantees for using the sparse grid.

Next, for higher dimensions, the probabilistic approach is researched. Using a martingale representation of conditional expectation, we develop a gradient-enhanced least squares Monte Carlo method. It achieves higher accuracy but nearly identical computational cost compared to classical least squares Monte Carlo. The approximation error estimate is established regarding the best approximation error in weighted $H^1$ space, the statistical error of solving discrete least squares problems, and the time step size.

To further quantify computational error bounds, a deep primal-dual backward stochastic differential equation method is proposed. In this framework, the novel loss function includes a martingale part, facilitating training and leading to the fast evaluation of dual bounds. The resulting duality gap measures the approximation error of neural networks.

Various numerical examples demonstrate the advantages of the proposed methods. In particular, optimal stopping problems with up to 200-dimensional underlying processes are tested.