WorksMathematics
SPIKE-Accelerated Split-Bregman/ADMM Methods for Obstacle Problems and American Option Pricing under Jump-Diffusion Models
Abstract
This paper presents a parallel split Bregman/alternating direction method of multipliers (ADMM) \cite{goldstein,tran} for obstacle problems and for the linear complementarity problems (LCPs) that arise in the pricing of American options under the Black–Scholes and Merton jump-diffusion \cite{merton} models. The auxiliary variable of ADMM decouples the inequality constraint from the differential operator, so that every iteration consists of a linear solve with a fixed banded matrix and a pointwise projection. The matrix is factorized once by the SPIKE algorithm \cite{spike}, as in the parallel direct approach of \cite{singh}, and reused in all iterations and time steps in a Fortran~90 MPI implementation. Convergence is proved by a Lyapunov functional for every positive augmentation parameter, for the symmetric obstacle problem and the non-symmetric option LCP alike, and the iterates do not depend on the number of processes. The method therefore needs a single factorization, no tuned relaxation parameter and only pointwise, perfectly parallel updates. One- and two-dimensional obstacle problems, the Black–Scholes call and American put, and European and American options under Merton's model are computed and compared with exact, closed-form, binomial and published values. In two dimension a speed-up of on four processes is obtained. It is also shown that the augmentation parameter has to be scaled to the diagonal of the time-stepping matrix when only a few inner iterations are used.