2021/03/04 by Bradley Sturt, Sturt, Bradley
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computational Finance (q-fin.CP) #FOS: Economics and business #FOS: Mathematics #Optimization and Control (math.OC) #Risk and Portfolio Optimization #Stochastic processes and financial applications
paper · pdf · doi:10.48550/arxiv.2103.03300
openalex publication_date 2021/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Optimal stopping is a fundamental class of stochastic dynamic optimization\nproblems with numerous applications in finance and operations management. We\nintroduce a new approach for solving computationally-demanding stochastic\noptimal stopping problems with known probability distributions. The approach\nuses simulation to construct a robust optimization problem that approximates\nthe stochastic optimal stopping problem to any arbitrary accuracy; we then\nsolve the robust optimization problem to obtain near-optimal Markovian stopping\nrules for the stochastic optimal stopping problem.\n In this paper, we focus on designing algorithms for solving the robust\noptimization problems that approximate the stochastic optimal stopping\nproblems. These robust optimization problems are challenging to solve because\nthey require optimizing over the infinite-dimensional space of all Markovian\nstopping rules. We overcome this challenge by characterizing the structure of\noptimal Markovian stopping rules for the robust optimization problems. In\nparticular, we show that optimal Markovian stopping rules for the robust\noptimization problems have a structure that is surprisingly simple and\nfinite-dimensional. We leverage this structure to develop an exact\nreformulation of the robust optimization problem as a zero-one bilinear program\nover totally unimodular constraints. We show that the bilinear program can be\nsolved in polynomial time in special cases, establish computational complexity\nresults for general cases, and develop polynomial-time heuristics by relating\nthe bilinear program to the maximal closure problem from graph theory.\nNumerical experiments demonstrate that our algorithms for solving the robust\noptimization problems are practical and can outperform state-of-the-art\nsimulation-based algorithms in the context of widely-studied stochastic optimal\nstopping problems from high-dimensional option pricing.\n