On the Solution of Complementarity Problems Arising in American Options Pricing

L. Feng(fenglmuiuc.edu)
V. Linetsky(linetskyiems.northwestern.edu)
J.L Morales(jmoralesitam.mx)
J. Nocedal(nocedaleecs.northwestern.edu)

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 system of partial differential variational inequalities. When these inequalities are discretized, one obtains a linear complementarity problem that must be solved at each time step. This paper presents an algorithm for the solution of these types of linear complementarity problems 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 Gauss-Seidel (or SOR) iteration with the second-order acceleration of a (recursive) reduced-space phase. Weshow how to design the algorithm so that it exploits the structure of the linear complementarity problems arising in these financial models and present numerical results that show the effectiveness of our approach.

Keywords: options pricing, linear complementarity, active-set method

Category 1: Applications -- OR and Management Sciences

Category 2: Applications -- OR and Management Sciences (Finance and Economics )

Category 3: Complementarity and Variational Inequalities

Citation: Technical Report 09/2, Optimization Center, Northwestern University, July 2009

Download: [PDF]

Entry Submitted: 07/30/2009
Entry Accepted: 07/31/2009
Entry Last Modified: 07/30/2009

Modify/Update this entry