LP valuation of exotic American options exploiting structure

ABSTRACT The numerical solution of American financial option pricing problems is investigated using a novel formulation of the valuation problem as a linear program (LP) introduced elsewhere by Dempster and Hutton. By exploiting the structure of the constraint matrices derived from standard Black-Scholes 'vanilla' problems, a fast and accurate revised simplex method is obtained which performs at most a linear number of pivots in the temporal discretization. When empirically compared with projected successive over- relaxation (PSOR) or a commercial LP solver, the new method is faster for all the vanilla problems tested. Utilizing this method, the authors value discretely sampled Asian and lookback American options and show that path-dependent PDE problems can be solved in 'desktop' solution times. It is concluded that LP solution techniques, which are robust to parameter changes, can be tuned to provide fast efficient valuation methods for finite-difference approximations to many vanilla and exotic option valuation problems.