PSOR for American Options

Setup

The American Option Problem

A European option can only be exercised at maturity $T$. An American option can be exercised at any time $\tau \in [0, T]$. Its value at time $t$ is:

$V(t, S) = \sup_{\tau \in \mathcal{T}_{t,T}} \mathbb{E}^{\mathbb{Q}}\!\left[e^{-r(\tau - t)} g(S_\tau) \,\Big|\, S_t = S\right],$

where $\mathcal{T}_{t,T}$ is the set of stopping times taking values in $[t, T]$, and $g(S)$ is the payoff (e.g., $(K - S)^+$ for an American put). This is an optimal stopping problem.

The Free Boundary

The American option value satisfies $V(t, S) \geq g(S)$ always (one can always exercise immediately). There exists a time-dependent critical asset price $S^*(t)$ — the early exercise boundary — such that:

• For $S \leq S^*(t)$ (American put): it is optimal to exercise immediately; $V(t, S) = g(S)$.
• For $S > S^*(t)$: holding is optimal; $V(t, S) > g(S)$ and $V$ satisfies the Black-Scholes PDE.

The boundary $S^*(t)$ is not known in advance — it must be determined as part of the solution. This is a free boundary problem (Stefan problem type).

Assumptions

Same as Black-Scholes: GBM for $S_t$, constant $r$ and $\sigma$, no dividends (unless stated). Continuous dividends at rate $q$ make early exercise of calls optimal; without dividends, early exercise of American calls is never optimal (they equal European calls). The interesting case is the American put.

Linear Complementarity Formulation

The free boundary problem can be reformulated as a linear complementarity problem (LCP), which is more amenable to numerical methods.

In terms of time to expiry $\tau = T - t$ and log-spot $x = \ln S$, with $\mathcal{L}$ the Black-Scholes operator:

$\mathcal{L}V = \frac{\partial V}{\partial \tau} - \frac{\sigma^2}{2}\frac{\partial^2 V}{\partial x^2} - \left(r - \frac{\sigma^2}{2}\right)\frac{\partial V}{\partial x} + rV,$

the LCP is:

$\mathcal{L}V \geq 0, \qquad V \geq g, \qquad \mathcal{L}V \cdot (V - g) = 0,$

almost everywhere on $(0, T] \times \mathbb{R}$.

Interpretation of each condition:

• $\mathcal{L}V \geq 0$: the option value satisfies the BS PDE inequality (in the holding region, $\mathcal{L}V = 0$ exactly; in the exercise region, $\mathcal{L}V > 0$ would imply arbitrage — so equality holds everywhere but the free boundary is where the transition occurs).
• $V \geq g$: value is at least intrinsic.
• $\mathcal{L}V \cdot (V - g) = 0$: at each point, either $\mathcal{L}V = 0$ (holding optimal, PDE satisfied) or $V = g$ (early exercise optimal), but not neither.

The LCP is equivalent to the free boundary formulation: it encodes all conditions without explicitly tracking $S^*(t)$.

Variational Inequality

The LCP is the Euler-Lagrange condition for a variational inequality (Bensoussan-Lions formulation): find $V$ in a suitable Sobolev space such that for all test functions $\phi \geq g$:

$a(V, \phi - V) \geq l(\phi - V),$

where $a(\cdot, \cdot)$ is the bilinear form associated with $\mathcal{L}$ and $l(\cdot)$ is the linear functional. This gives rigorous existence and uniqueness of the solution, with regularity $V \in H^1$ but generically $V \notin H^2$ (the second derivative is discontinuous at the free boundary).

Discretisation and the Discrete LCP

Apply Crank-Nicolson to the LCP, treating the spatial operator implicitly. At each time step $j \to j+1$:

Without early exercise constraint (pure CN): $A \mathbf{C}^{j+1} = \mathbf{b}^j,$

where $A$ is the CN tridiagonal matrix and $\mathbf{b}^j$ includes the explicit contribution from level $j$.

With early exercise constraint: replace the linear system with the discrete LCP:

$A \mathbf{V}^{j+1} - \mathbf{b}^j \geq \mathbf{0}, \qquad \mathbf{V}^{j+1} \geq \mathbf{g}, \qquad (A\mathbf{V}^{j+1} - \mathbf{b}^j)^\top (\mathbf{V}^{j+1} - \mathbf{g}) = 0.$

This must be solved for $\mathbf{V}^{j+1}$ at each time step. The constraint is applied component-wise: for each spatial grid point $i$, either the PDE residual is zero (holding) or $V_i = g_i$ (exercise).

PSOR Algorithm

Successive Over-Relaxation (SOR)

SOR solves $A\mathbf{x} = \mathbf{b}$ iteratively. Writing $A = D + L + U$ (diagonal + strict lower + strict upper triangular), one iteration of SOR: