A Newton method for American option pricing

ABSTRACT The variational inequality formulation provides a mechanism for determining both the option value and the early exercise curve implicitly (Jaillet, Lamberton and Lapeyre, 1990). Standard finite-difference approximation typically leads to linear complementarity problems with tridiagonal coefficient matrices. However, the second-order upwind finite-difference formulation gives rise to finite-dimensional linear complementarity problems with non-tridiagonal matrices, whereas the upstream weighting finite-difference approach, with the van Leer flux limiter for the convection term (Roache, 1972; Zvan, Vetzal and Forsyth, 1997), yields non-linear complementarity problems. We propose a Newton-type interior-point method to solve discretized complementarity/variational inequality problems arising in the American option valuation. We show that, on average, the proposed method solves a discretized problem in around two to five iterations to an appropriate accuracy. More importantly, the average number of iterations required does not seem to depend on the number of discretization points in the spatial dimension; the average number of iterations actually decreases as the time discretization becomes finer. The arbitrage condition for the fair value of an American option requires that its delta hedge factor be continuous. We investigate continuity of the delta factor approximation using the complementarity approach, the binomial method, and a simple method of taking the maximum of continuation value and the option payout (the explicit payout method). We show that, whereas the (implicit finite-difference) complementarity approach yields continuous delta hedge factors, both the binomial method and the explicit payout method (with the implicit finite difference) yield discontinuous delta approximations; the early exercise curve computed using the binomial method and the explicit payout method can be inaccurate. In addition, it is demonstrated that the delta factor computed using the Crank–Nicolson method with the complementarity approach can be oscillatory around the early exercise curve.