How PSOR Algorithms Price American Options as Linear-Complementarity Problems: Early-Exercise Obstacles, Projected Gauss–Seidel Updates, Relaxation, Free Boundaries and Convergence Failure

Reader question: A finite-difference grid can price a European option by solving a linear system at each time step. How does the algorithm change when an American option may be exercised early and the value must never fall below intrinsic value?

Projected Successive Over-Relaxation (PSOR) solves that extra constraint directly. The American-option PDE becomes a variational inequality; after finite-difference discretisation, each time layer becomes a linear complementarity problem (LCP). PSOR combines a Gauss–Seidel/SOR linear-system update with a projection back onto the payoff obstacle after every node update.

This article owns one precise computational job: iterative solution of the American-option LCP produced by a finite-difference discretisation. It does not own the Black–Scholes PDE itself, generic finite-difference stability, Monte Carlo early-exercise regression, stochastic-mesh methods or all possible LCP solvers.

This is public mathematical and computational education. It is not financial advice, an exercise recommendation for a live option position or a claim that PSOR is the fastest American-option method in every model.

1. Why American options create an obstacle

Let Φ(S) be the immediate-exercise payoff. For an American put:

Φ(S)=max(K−S,0).

At every time before expiry, the option value must satisfy:

V(S,t) ≥ Φ(S).

In the continuation region, holding is better than exercising and the Black–Scholes operator satisfies the pricing PDE. In the exercise region, the option sits on the obstacle:

V = Φ.

The free boundary between those regions is not known in advance.

2. Complementarity form

One common continuous-time statement is:

min(V−Φ, −V_t−LV)=0,

where L denotes the spatial pricing operator under the chosen model.

This encodes three facts:

• V−Φ ≥ 0;
• −V_t−LV ≥ 0;
• their product/complementarity is zero.

At any point, either the obstacle binds or the continuation PDE binds.

3. Time discretisation creates an LCP

After a backward-Euler, Crank–Nicolson or related time step, the unknown vector Vⁿ at one time layer commonly satisfies a matrix inequality of the form:

A V ≥ b,

V ≥ Φ,

(A V−b)^T(V−Φ)=0.

Here A is usually sparse and tridiagonal in one spatial dimension. The exact A and b depend on the finite-difference scheme and boundary conditions.

4. Ordinary Gauss–Seidel is not enough

For the European problem, one could solve:

A V = b.

Gauss–Seidel updates each component sequentially using newly updated values on the left and old values on the right.

But an American value from that unconstrained solve can fall below intrinsic value. That violates the exercise right.

PSOR fixes this by projecting each updated node back onto:

V_i ≥ Φ_i.

5. The SOR update

For row i of A, write the Gauss–Seidel candidate:

Ṽ_i = [b_i − Σ_j<ia_ijV_j^new − Σ_j>ia_ijV_j^old]/a_ii.

SOR forms:

V̄_i = (1−ω)V_i^old + ωṼ_i.

The projected step is then:

V_i^new = max(Φ_i, V̄_i).

This one line is the distinctive PSOR mechanism: relax the linear solve, then enforce the early-exercise floor immediately.

6. What the relaxation parameter does

ω controls how aggressively the iteration moves.

• ω = 1 gives projected Gauss–Seidel.
• 1 < ω < 2 is over-relaxation.
• 0 < ω < 1 is under-relaxation.

For many classical SOR systems, an appropriate ω in (0,2) can accelerate convergence. But the best value depends on the matrix, grid and problem.

Falsifier: record iterations-to-tolerance over a grid of ω values. A fixed “magic” value copied between models is not evidence of optimal tuning.

7. Why projection solves the exercise constraint

Suppose the unconstrained iteration proposes V̄_i below intrinsic value.

The projection sets:

V_i=Φ_i.

That node is treated as an exercise-region candidate.

If the next iterations later produce a continuation value above Φ, the node can leave the obstacle. The active set therefore emerges endogenously from the iteration rather than being pre-specified.

8. Free-boundary extraction

After convergence at a time layer, compare:

V_i−Φ_i.

For a standard American put with conventional positive-rate geometry, exercise nodes lie below a critical stock level and continuation nodes above it.

A discrete free-boundary estimate can be taken near the largest S node where the obstacle binds, with interpolation if needed.

But unusual models—such as negative or stochastic rates—can generate more complex exercise geometry. Boundary extraction rules should not assume connectedness unless the model guarantees it.

9. Stopping criteria need more than one number

A simple iteration test is:

||V^k+1−V^k||∞ < ε.

That detects small iterate changes but does not directly prove the LCP conditions.

A stronger audit also checks:

• obstacle violation: min(V−Φ);
• PDE/LCP residual: min(A V−b);
• complementarity residual;
• boundary-condition residuals.

An iterate can change very little because ω is badly chosen while still being far from an accurate solution.

10. Inputs and outputs

Inputs can include:

• spot grid and domain S_max;
• time grid;
• strike and payoff;
• interest/dividend inputs;
• volatility/local-volatility inputs;
• finite-difference scheme;
• boundary conditions;
• relaxation parameter ω;
• iteration tolerance;
• maximum iterations.

Outputs can include:

• American option value;
• full value surface;
• exercise/continuation mask;
• free-boundary estimate;
• PSOR iteration count per time step;
• LCP residuals;
• grid-refinement convergence table;
• comparison with European value and alternative solvers.

11. Evidence polarity

Evidence for confidence includes:

• V ≥ Φ at every node;
• LCP residuals converge to tolerance;
• price changes shrink under space/time-grid refinement;
• European special cases agree with the corresponding European PDE solver;
• American put values agree with high-resolution binomial/tree benchmarks;
• exercise boundaries move smoothly with time when theory predicts that geometry;
• different ω values converge to the same price.

Evidence against confidence includes:

• nodes below intrinsic value;
• large complementarity residuals despite a small iterate-change norm;
• iteration counts exploding under refinement;
• price depends materially on ω after apparent convergence;
• free boundary oscillates grid point by grid point;
• Crank–Nicolson produces near-expiry oscillatory Greeks;
• boundary expansion materially changes today’s price.

12. Counterexample: project only after solving

A tempting shortcut is:

1. solve A V = b;
2. replace V with max(V,Φ) once.

That does not generally solve the LCP because the projection changes neighbouring equations. The linear-system residual is no longer consistent with the projected values.

PSOR interleaves solving and projection so the active set and linear equations converge together.

13. Counterexample: ω too close to 2

Over-relaxation can accelerate a stable iteration, but excessive ω can create oscillation or divergence.

Falsifier: plot the residual norm versus iteration. Alternating or growing residuals indicate that the relaxation choice is destabilising the solver.

14. Counterexample: ω too small

Under-relaxation can be safe but painfully slow.

A solver may hit its maximum iteration count and return a partially converged surface.

Falsifier: never treat “max iterations reached” as success. Persist convergence status in the output.

15. Grid refinement can make PSOR relatively slow

Projected SOR is simple and robust, but it is a stationary iterative method. Research comparing American-option LCP solvers finds that projected multigrid, policy iteration, splitting or two-phase methods can be much faster on fine grids.

Boundary: PSOR is an excellent teaching baseline and often a practical one-dimensional solver, but simplicity is not the same as asymptotic optimality.

16. Crank–Nicolson near a kink

The payoff at maturity has a kink at the strike. Crank–Nicolson is second-order in smooth settings but can show oscillations in values or Greeks near non-smooth terminal data.

Rannacher-style initial backward-Euler steps are one common damping technique.

PSOR enforces exercise; it does not by itself cure time-discretisation oscillations.

See Finite-Difference Option-Pricing Algorithms for the parent discretisation problem.

17. Nonuniform grids

Option curvature is usually highest near economically important regions such as the strike and exercise boundary.

A nonuniform grid can concentrate nodes there while keeping distant boundaries sparse.

But the finite-difference coefficients and M-matrix properties must be recomputed correctly.

Falsifier: compare uniform and nonuniform grids at similar node counts and verify monotonicity, positivity and refinement convergence.

18. Boundary conditions can dominate the result

At S=0 and S=S_max, the PDE is replaced by asymptotic/boundary conditions.

If S_max is too small, the far boundary can contaminate the interior solution.

Falsifier: expand S_max materially. Today’s price and boundary near spot should remain stable.

19. Dividends and early exercise

For a non-dividend-paying stock under standard positive rates, early exercise of an American call is not optimal; its value equals the European call under the standard assumptions.

This provides a valuable special-case test.

With dividends, calls can have early-exercise regions. A discrete dividend requires jump conditions at ex-dividend dates rather than a simple continuous-yield PDE.

Falsifier: a PSOR code that prices a no-dividend American call materially above its European counterpart under standard assumptions needs investigation.

20. PSOR under stochastic volatility

Under Heston, the American problem becomes a two-dimensional partial differential inequality.

PSOR can still be applied to the resulting LCP, but the matrix is larger and mixed derivatives complicate discretisation.

Comparative research shows projected SOR can become much slower than multigrid or splitting methods on fine two-dimensional grids.

See ADI Algorithms for the Heston PDE for the neighbouring multidimensional time-stepping problem.

21. Alternatives

Brennan–Schwartz: exploits one-dimensional tridiagonal/M-matrix structure and can solve certain American put LCPs directly.

Penalty methods: replace the obstacle with a large nonlinear penalty and solve a sequence of nonlinear/linear systems.

Policy iteration / active-set methods: switch nodes between exercise and continuation regimes and solve reduced linear systems.

Ikonen–Toivanen splitting: separates the linear evolution and early-exercise constraint into fractional steps.

Longstaff–Schwartz: uses simulated paths and continuation regressions rather than a PDE/LCP.

22. Relation to the early-exercise Monte Carlo estate

Longstaff–Schwartz LSMC approximates conditional continuation values by regression.

Andersen–Broadie produces primal/dual bounds around an exercise policy.

PSOR instead owns the deterministic grid-based complementarity solve.

23. Relation to sparse grids

Smolyak sparse grids reduce high-dimensional node growth. They can be combined with PDE or continuation-value machinery, but they do not replace the American obstacle logic.

24. Weak links

• wrong LCP sign convention;
• projection against the wrong payoff;
• ω chosen without diagnostics;
• iterate-change tolerance used without complementarity residuals;
• far boundary too close;
• grid too coarse near strike/exercise boundary;
• terminal kink not damped where needed;
• dividend treatment incorrect;
• maximum-iteration failure silently accepted;
• American geometry assumed instead of verified.

25. What would falsify confidence?

Confidence should be withdrawn if the obstacle or LCP residuals fail; if prices do not converge under grid refinement; if different relaxation parameters converge to materially different values; if special cases disagree with European/tree benchmarks; if exercise boundaries are unstable; or if a more suitable LCP solver reproduces a materially different price on the same discrete system.

26. Verification and update triggers

Preserve the PDE coefficients, grid, boundary conditions, time scheme, exact A/b construction, payoff, ω, tolerance, iteration cap, residual definitions and benchmark outputs.

Revalidate when:

• model coefficients change;
• dividend treatment changes;
• negative/stochastic rates are introduced;
• grid construction changes;
• time stepping changes;
• dimension increases;
• a new LCP solver replaces PSOR.

27. Primary and high-quality references

• Liming Feng, Vadim Linetsky, José Luis Morales and Jorge Nocedal, On the Solution of Complementarity Problems Arising in American Options Pricing, Optimization Methods and Software, 2011.
• Christoph Reisinger and Jan Hendrik Witte, On the Use of Policy Iteration as an Easy Way of Pricing American Options, SIAM Journal on Financial Mathematics, 2012.
• Samuli Ikonen and Jari Toivanen, Efficient Numerical Methods for Pricing American Options under Stochastic Volatility, Numerical Methods for Partial Differential Equations.
• Xian-Jun Shi, Lei Yang and Zheng-Hai Huang, A Fixed Point Method for the Linear Complementarity Problem Arising from American Option Pricing, 2016.

Educational boundary: PSOR is a numerical method for solving a discretised early-exercise complementarity problem. A converged PSOR iteration is only as accurate as the PDE model, grid, boundary conditions and time discretisation that produced the LCP.