Solving Optimal Stopping Problems via Randomization and Empirical Dual Optimization
将最优停止问题的对偶形式转化为随机平均逼近问题，通过随机化初始值实现零方差解，并利用线性规划求解，算法收敛更快、复杂度更低。
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. Funding: This work was supported by the Deutsche Forschungsgemeinschaft via the MATH+ Cluster of Excellence [Project AA4-2].