Pathwise Optimization for Optimal Stopping Problems

Vijay V. Desai (), Vivek F. Farias () and Ciamac C. Moallemi ()
Additional contact information
Vijay V. Desai: Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Vivek F. Farias: MIT Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
Ciamac C. Moallemi: Graduate School of Business, Columbia University, New York, New York 10027

Management Science, 2012, vol. 58, issue 12, 2292-2308

Abstract: We introduce the pathwise optimization (PO) method, a new convex optimization procedure to produce upper and lower bounds on the optimal value (the "price") of a high-dimensional optimal stopping problem. The PO method builds on a dual characterization of optimal stopping problems as optimization problems over the space of martingales, which we dub the martingale duality approach. We demonstrate via numerical experiments that the PO method produces upper bounds of a quality comparable with state-of-the-art approaches, but in a fraction of the time required for those approaches. As a by-product, it yields lower bounds (and suboptimal exercise policies) that are substantially superior to those produced by state-of-the-art methods. The PO method thus constitutes a practical and desirable approach to high-dimensional pricing problems. Furthermore, we develop an approximation theory relevant to martingale duality approaches in general and the PO method in particular. Our analysis provides a guarantee on the quality of upper bounds resulting from these approaches and identifies three key determinants of their performance: the quality of an input value function approximation, the square root of the effective time horizon of the problem, and a certain spectral measure of "predictability" of the underlying Markov chain. As a corollary to this analysis we develop approximation guarantees specific to the PO method. Finally, we view the PO method and several approximate dynamic programming methods for high-dimensional pricing problems through a common lens and in doing so show that the PO method dominates those alternatives. This paper was accepted by Wei Xiong, stochastic models and simulation.

Keywords: dynamic programming; optimal control; optimal stopping; American options; Bermudian options (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (29)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.1120.1551 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:58:y:2012:i:12:p:2292-2308

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().