In this paper, we study simulation-based optimization algorithms for solving discrete time optimal stopping problems. Using large deviation theory for the increments of empirical processes, we derive optimal convergence rates for the value function estimate and show that they cannot be improved in general. The rates derived provide a guide to the choice of the number of simulated paths needed in optimization step, which is crucial for the good performance of any simulation-based optimization algorithm. Finally, we present a numerical example of solving optimal stopping problem arising in finance that illustrates our theoretical findings.
Publié le : 2011-02-15
Classification:
Optimal stopping,
simulation-based algorithms,
exponential inequalities,
empirical processes,
δ-entropy with bracketing,
60J25,
91B28
@article{1292598032,
author = {Belomestny, Denis},
title = {On the rates of convergence of simulation-based optimization algorithms for optimal stopping problems},
journal = {Ann. Appl. Probab.},
volume = {21},
number = {1},
year = {2011},
pages = { 215-239},
language = {en},
url = {http://dml.mathdoc.fr/item/1292598032}
}
Belomestny, Denis. On the rates of convergence of simulation-based optimization algorithms for optimal stopping problems. Ann. Appl. Probab., Tome 21 (2011) no. 1, pp. 215-239. http://gdmltest.u-ga.fr/item/1292598032/