Solving Optimal Stopping Problems via Randomization and Empirical Dual Optimization. Belomestny, D., Bender, C., & Schoenmakers, J. Mathematics of Operations Research, 0(0):null, 0.
Solving Optimal Stopping Problems via Randomization and Empirical Dual Optimization [link]Paper  doi  abstract   bibtex   
In this paper, we consider optimal stopping problems in their dual form. In this way, the optimal stopping problem can be reformulated as a problem of stochastic average approximation (SAA) that can be solved via linear programming. By randomizing the initial value of the underlying process, we enforce solutions with zero variance while preserving the linear programming structure of the problem. A careful analysis of the randomized SAA algorithm shows that it enjoys favorable properties such as faster convergence rates and reduced complexity compared with the nonrandomized procedure. We illustrate the performance of our algorithm on several benchmark examples.
@article{doi:10.1287/moor.2022.1306,
author = {Belomestny, Denis and Bender, Christian and Schoenmakers, John},
title = {Solving Optimal Stopping Problems via Randomization and Empirical Dual Optimization},
journal = {Mathematics of Operations Research},
volume = {0},
number = {0},
pages = {null},
year = {0},
doi = {10.1287/moor.2022.1306},
URL = {https://doi.org/10.1287/moor.2022.1306},
eprint = {https://doi.org/10.1287/moor.2022.1306},
abstract = { In this paper, we consider optimal stopping problems in their dual form. In this way, the optimal stopping problem 
can be reformulated as a problem of stochastic average approximation (SAA) that can be solved via linear programming. 
By randomizing the initial value of the underlying process, we enforce solutions with zero variance while preserving the linear 
programming structure of the problem. A careful analysis of the randomized SAA algorithm shows that it enjoys favorable properties 
such as faster convergence rates and reduced complexity compared with the nonrandomized procedure. We illustrate the performance 
of our algorithm on several benchmark examples. }
}

Downloads: 0