| Summary: | In this paper, we demonstrate that policy iteration, introduced in the context of HJB equations in [P. A. Forsyth and G. Labahn, J. Comput. Finance, 11 (2007), pp. 1-44], is an extremely simple generic algorithm for solving linear complementarity problems (LCPs) resulting from the finite difference and finite element approximation of American options. We show that, in general, O(N) is an upper and a lower bound on the number of iterations needed to solve a discrete LCP of size N. If embedded in a class of standard discretizations with M time steps, the overall complexity of American option pricing is indeed only O(N(M + N)), and, therefore, for M ~ N, it is identical to the pricing of European options, which is O(MN). We also discuss the numerical properties and robustness with respect to model parameters in relation to penalty and projected relaxation methods. Copyright © 2012 by SIAM.
|
|---|