Linear programming approach to the optimal stopping of singular stochastic processes

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 prices 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.

Keywords:

• Optimal stopping
• Singular processes
• Linear programming
• Regime switching
• Lookback option
• Martingale problem

MSC 2000 Classifications::

• 60G40
• 60J55
• 90C05

Acknowledgements

This research has been supported in part by the US National Security Agency under Grant Agreement Number H98230-05-1-0062. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation herein.