A quantization algorithm for solving multidimensional discrete-time optimal stopping problems (Q1431527)

The authors propose 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}\). The backward quantization tree algorithm is derived and some a priori \(L^p\)-error bounds are established. Then the extension of the competetive learning vector quantization algorithm to Markov chains is presented to process the numerical optimization of the grids and the computation of their transition weights. A comparison with the finite-element method is carried out. The above results are applied to the discretization of reflected backward stochastic differential equations with some a priori error bounds, when the diffusion is uniformly elliptic. Numerical illustration is given: the pricing of American style exchange options.