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:

$x_i^{(\text{new})} = (1 - \omega) x_i^{(\text{old})} + \frac{\omega}{a_{ii}}\left(b_i - \sum_{k < i} a_{ik} x_k^{(\text{new})} - \sum_{k > i} a_{ik} x_k^{(\text{old})}\right),$

for $i = 1, \ldots, M-1$. The parameter $\omega \in (1, 2)$ is the relaxation factor ($\omega = 1$ = Gauss-Seidel; $\omega > 1$ = over-relaxation). Optimal $\omega$ for a tridiagonal system with spectral radius $\rho_J$ of the Jacobi iteration matrix:

$\omega^* = \frac{2}{1 + \sqrt{1 - \rho_J^2}}.$

Projected SOR (PSOR)

PSOR modifies each SOR iteration by projecting onto the feasible set $V_i \geq g_i$:

$\tilde{V}_i = (1 - \omega) V_i^{(\text{old})} + \frac{\omega}{a_{ii}}\left(b_i - \sum_{k < i} a_{ik} V_k^{(\text{new})} - \sum_{k > i} a_{ik} V_k^{(\text{old})}\right),$

$V_i^{(\text{new})} = \max\!\left(g_i,\; \tilde{V}_i\right).$

The max projection enforces the early exercise constraint at each grid point during each iteration. No knowledge of the free boundary location is needed — it is implicitly determined by which nodes are projected.

Per time step cost: $O(M \cdot K_{\mathrm{iter}})$, where $K_{\mathrm{iter}}$ is the number of PSOR iterations to convergence (typically $5$–$20$).

Convergence of PSOR

Theorem (Cryer, 1971; Mangasarian, 1977). For PSOR applied to a discrete LCP $A\mathbf{x} \geq \mathbf{b}$, $\mathbf{x} \geq \mathbf{g}$, $(A\mathbf{x} - \mathbf{b})^\top(\mathbf{x} - \mathbf{g}) = 0$, where $A$ is symmetric positive definite (or an M-matrix), PSOR converges to the unique solution for any $\omega \in (0, 2)$.

For the CN discretisation of the American put, $A$ is an M-matrix (diagonally dominant, non-positive off-diagonal). Convergence is guaranteed for $\omega \in (0, 2)$.

Rate. The convergence rate of PSOR is $\rho(\omega)$, the spectral radius of the iteration matrix. For $\omega < \omega^*$, convergence is sub-optimal; for $\omega > \omega^*$, it can oscillate. In practice, $\omega = 1.2$–$1.5$ is effective for the BS tridiagonal.

Convergence Criterion

Iterate until the residual $r_k = \max_i |(A\mathbf{V}^{(k)})_i - b_i|$ falls below a tolerance $\varepsilon$ (typically $10^{-8}$–$10^{-6}$) and all constraint violations are resolved: $\max_i (g_i - V_i^{(k)})^+ < \varepsilon$.

Comparison: PSOR vs. Binomial Tree

Both methods solve the American option problem. Their comparison illuminates the trade-off between implementation simplicity and numerical efficiency.

Convergence order note. The binomial tree converges at $O(1/N)$ for smooth payoffs but $O(1/\sqrt{N})$ for American puts due to the staircase approximation of the free boundary. Richardson extrapolation or the Broadie-Detemple smoothing technique recovers $O(1/N)$. The PSOR grid achieves $O(\Delta\tau^2)$ with CN and smooth payoffs.

At matched grid resolution. Setting $M = N$ (equal number of grid points and time steps) and computing at matched total computation cost, PSOR gives significantly more accurate prices. The free boundary is resolved with order $O(\Delta x)$ accuracy in both methods at matched grid; PSOR's advantage comes from its higher-order time discretisation.

Limitations

Payoff smoothness. Near expiry for deep in-the-money American puts, the free boundary moves rapidly (it converges to $K$ as $\tau \to 0$ at rate $O(\sqrt{\tau \ln \tau})$). This rapid movement can cause local inaccuracy in the free boundary location. Finer grids near $\tau = 0$ or local grid refinement is needed.

Multi-factor extensions. For basket American options or Heston model American options, the LCP is two-dimensional. PSOR extends to 2D: sweep over the 2D grid in a lexicographic order, applying the projection at each node. The outer iteration now solves a 2D implicit system, which is typically handled by ADI splitting — with each ADI substep having an LCP structure solved by 1D PSOR.

Bermudan options. Bermudan options allow exercise at a finite set of dates $\{T_1, \ldots, T_n\}$. The free boundary is not continuous in time — it is a finite set of early exercise dates. The LCP at each exercise date reduces to a simple node-by-node projection: $V_i = \max(g_i, V_i^{\mathrm{hold}})$, which is trivial. PSOR is not needed between exercise dates; the CN solver suffices.

American call without dividends. The American call with no dividends equals the European call: early exercise is never optimal because the call's time value exceeds the dividends foregone (none). Including a continuous dividend yield $q > 0$ restores the early exercise premium for calls, requiring PSOR.

Interview Angle

L1. Why is an American put worth more than a European put? Under what condition is early exercise of an American call optimal?

American put premium: The American put can be exercised early to earn the interest on the strike $K$: if the stock is very low, immediately exercising yields $K - S \approx K$ which can be invested at rate $r$. Waiting risks the stock rising and the put expiring worthless. The premium over the European put equals the present value of the optimal early exercise strategy.

American call: Early exercise of a call sacrifices time value (option's convexity premium) in exchange for the dividend received. Without dividends, it is always suboptimal to exercise a call early — the European and American call have the same price. With a continuous dividend $q > r(1 - K/S)$ (approximately), early exercise becomes optimal above some critical spot.

L2. State the linear complementarity problem for the American put. Show that the LCP at each grid point encodes either the PDE holding condition or the early exercise condition. Describe the PSOR update rule.

LCP at node $i$: Two conditions hold simultaneously: (a) $(AV^{j+1})_i - b_i^j \geq 0$ (PDE residual non-negative), (b) $V_i^{j+1} \geq g_i$ (intrinsic floor), (c) $[(AV^{j+1})_i - b_i^j] \cdot [V_i^{j+1} - g_i] = 0$ (complementarity).

At each node: if $V_i > g_i$ (holding region), then $(AV)_i = b_i$ (PDE = 0 residual). If $(AV)_i > b_i$ (PDE positive), then $V_i = g_i$ (exercise region).

PSOR update: Compute the Gauss-Seidel trial value $\tilde{V}_i$, then set $V_i^{\text{new}} = \max(g_i, \tilde{V}_i)$. The projection ensures $V_i \geq g_i$; if the SOR value is below intrinsic, we force early exercise at that node.

L3. Prove that PSOR converges for the American put LCP. Compare the convergence rate of PSOR to Gauss-Seidel for a symmetric positive definite tridiagonal system, and explain the optimal over-relaxation factor.

Convergence proof (sketch). The CN tridiagonal matrix $A$ is an M-matrix: non-negative diagonal, non-positive off-diagonals, strictly diagonally dominant. An M-matrix is positive definite and has a regular splitting $A = D - B$ with $D > 0$, $B \geq 0$. By Mangasarian's theorem, PSOR converges for any $\omega \in (0,2)$ when $A$ is an M-matrix. The proof uses the fact that the LCP solution is unique (by positive definiteness of $A$) and that the PSOR iterates form a monotone sequence bounded below by the solution.

Optimal $\omega$: For a consistently ordered matrix, the spectral radius of the SOR iteration matrix is minimised at $\omega^* = 2/(1+\sqrt{1-\rho_J^2})$ where $\rho_J$ is the spectral radius of the Jacobi matrix. For the BS tridiagonal with $\rho_J \approx \cos(\pi/M)$, $\omega^* \approx 2/(1 + \pi/M) \approx 2 - 2\pi/M$ for large $M$. The convergence rate (spectral radius of SOR iteration matrix at $\omega^*$) is $\rho(\omega^*) = \omega^* - 1 \approx 1 - 2\pi/M$, requiring $O(M)$ iterations for a fixed tolerance — expensive for large $M$. For this reason, direct LCP solvers (Policy iteration, or a direct tridiagonal approach to the LCP) are sometimes preferred over PSOR for large grids.