Home » Publications

A quantization algorithm for solving multidimensional optimal stopping problems, preprint

TitleA quantization algorithm for solving multidimensional optimal stopping problems, preprint
Publication TypeConference Paper
Year of Publication2001
AuthorsVlad Bally, and Gilles Pagès
Conference NameUniversity de Paris VI
Abstract

A new grid method for computing the Snell envelope of a function of an $ \mathbb{R}^d $-valued simulatable Markov chain $ (X_k)_{0\leq k\leq n} $ is proposed. (This is a typical nonlinear problem that cannot be solved by the standard Monte Carlo method.) Every $ X_k $ is replaced by a 'quantized approximation' $ \widehat{X}_k $ taking its values in a grid $ \Gamma_k $ of size $ N_k $. The $ n $ grids and their transition probability matrices form a discrete tree on which a pseudo-Snell envelope is devised by mimicking the regular dynamic programming formula. Using the quantization theory of random vectors, we show the existence of a set of optimal grids, given the total number $ N $ of elementary $ \mathbb{R}^d $-valued quantizers. A recursive stochastic gradient algorithm, based on simulations of ($ X_k)_{0\leq k\leq n} $, yields these optimal grids and their transition probability matrices. Some a priori error estimates based on the $ L^p $-quantization errors $ |X_k - \widehat{X}_k|^p $ are established. These results are applied to the computation of the Snell envelope of a diffusion approximated by its (Gaussian) Euler scheme. We apply these results to provide a discretization scheme for reflected backward stochastic differential equations. Finally, a numerical experiment is carried out on a two-dimensional American option pricing problem.