Linear Programming Approach to the Optimal Stopping

Abstract. Optimal stopping of stochastic processes having both absolutely continuous and singular behavior (with respect to time) can be equivalently formulated as an infinite-dimensional linear program over a collection of measures. These measures represent the occupation measures of the process (up to a stopping time) with respect to “regular time ” and “singular time ” and the distribution of the process when it is stopped. Such measures corresponding to the process and stopping time are characterized by an adjoint equation involving the absolutely continuous and singular generators of the process. This general linear programming formulation is shown to be numerically tractable through three examples, each of which seeks to determine the stopping rule for a perpetual lookback put option using different dynamics for the asset price. Exact solutions are determined in the cases that the asset price are given by a drifted Brownian motion and a geometric Brownian motion. Numerical results for the more realistic model of a regime switching geometric Brownian motion are also presented, demonstrating that the linear programming methodology is numerically tractable for models whose theoretical solutions are very difficult to obtain