Solving Optimal Stopping Problems via Randomization and Empirical Dual Optimization

Denis Belomestny (), Christian Bender () and John Schoenmakers ()
Additional contact information
Denis Belomestny: Department of Mathematics, University of Duisburg-Essen, 47057 Duisburg, Germany
Christian Bender: Department of Mathematics, Saarland University, 66123 Saarbrücken, Germany
John Schoenmakers: Weierstrass Institute for Applied Analysis and Stochastics, 10117 Berlin, Germany

Mathematics of Operations Research, 2023, vol. 48, issue 3, 1454-1480

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.

Keywords: Primary: 91G60; secondary: 65G05; 60G40; optimal stopping; duality; stochastic average approximation; randomization (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1306 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:3:p:1454-1480

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().