@conference {4,
title = {A quantization algorithm for solving multidimensional optimal stopping problems, preprint},
booktitle = {University de Paris VI},
year = {2001},
pages = {1003{\textendash}1049},
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 {\textquoteright}quantized approximation{\textquoteright} $\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.},
author = {Vlad Bally and Gilles Pag{\`e}s}
}