Solving Optimal Stopping Problems via Randomization and Empirical Dual Optimization

• 成果类型: Article
• 署名作者: Belomestny, Denis; Bender, Christian; Schoenmakers, John
• 署名单位: University of Duisburg Essen; Saarland University; Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1306
• 发表日期: 2023
• 页码: 1454-1480
• 关键词: pricing american options; Concentration inequality; algorithms; simulation

摘要

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.