Abstract
In the Black-Scholes-Merton model, as well as in more general stochastic models in finance, the price of an American option solves a parabolic variational inequality. When the variational inequality is discretized, one obtains a linear complementarity problem (LCP) that must be solved at each time step. This paper presents an algorithm for the solution of these types of LCPs that is significantly faster than the methods currently used in practice. The new algorithm is a two-phase method that combines the active-set identification properties of the projected successive over relaxation (SOR) iteration with the second-order acceleration of a (recursive) reduced-space phase. We show how to design the algorithm so that it exploits the structure of the LCPs arising in these financial applications and present numerical results that show the effectiveness of our approach.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 813-825 |
| Number of pages | 13 |
| Journal | Optimization Methods and Software |
| Volume | 26 |
| Issue number | 4-5 |
| DOIs | |
| State | Published - Aug 2011 |
Funding
The authors are grateful to Jong-Shi Pang for his comments and advice during the preparation of this manuscript. L. Feng was supported by National Science Foundation grant CMMI-0927367. V. Linetsky was supported by National Science Foundation grant DMS-0802720. J.L. Morales was supported byAsociación Mexicana de CulturaAC and CONACyT-NSF grant J110.388/2006. J. Nocedal was supported by National Science Foundation grant DMS-0810213 and Department of Energy grant DE-FG02-87ER25047-A004.
Keywords
- American options pricing
- linear complementarity
- projected SOR method
ASJC Scopus subject areas
- Software
- Control and Optimization
- Applied Mathematics
