Bermudan option pricing based on piecewise harmonic interpolation and the reduite, , November 27, 2006

1 Introduction

We intend to approximate the function that assigns the value of a Bermudan option with payoff function

g

and no dividends to the logarithmic start prices of the underlying assets by piecewise harmonic functions. In the first step, we will compute a piecewise harmonic approximation to the function that assigns the European option price associated with

g

and the Bermudan’s maturity

T > 0

to the logarithmic asset prices at the penultimate time

T - t

where exercise is possible. Then we iteratively compute the expectation of this function after time

t

, discount, take the maximum with the payoff function

g

, and perform a reduite-based interpolation (in the one-dimensional setting: a piecewise harmonic interpolation).

Now we would like to answer the following questions: Given the stationarity of perpetual Bermudan option prices, can we prove that there exists a minimal fixed point of the iteration step described above (which would then be an approximation to the perpetual Bermudan price)? If so, can we characterise it explicitly? Is the iteration step monotone?

First, we will discuss these questions in the one-dimensional setting – very little knowledge of potential theory has to be assumed for the proofs in that section.

Second, we shall generalise that approach to higher dimensions; this will entail a few technical subtleties.

2 Piecewise Bermudan option pricing for options on one asset

Consider

{a_{0}, . . ., a_{m}} \subset R

, the set of (mutually distinct) support abscissas, and let

L : C^{\infty} (R, R) \to C^{\infty} (R, R)

be the infinitesimal generator of a Markov semigroup of operators on Lebesgue measurable functions from

R

R

. We call a function

f \in C^{\infty} (R, R)

P

-harmonic (or shorter: harmonic, if no ambiguity can arise) if and only if

L f = 0

. Let

(P_{t})_{t \geq 0}

denote the semigroup generated by

L

For the following, assume

L

to be a second-order differential operator, that is, there are constants

β_{1}, β_{2} \in R

such that

L : f \mapsto β_{1} f^{'} + β_{2} f^{''} .

A function

g : R \to R

is said to be subharmonic (superharmonic) if and only if

g

is rightand left-differentiable (thus, letting

L g

become well-defined as a function from

R

R \cup {\pm \infty}

) and

L g \geq 0

(

L g \leq 0

, respectively).

In particular, the supremum (infimum) of countably many harmonic functions is subharmonic (superharmonic).

Lemma 1. Given two support abscissas and ordinates, there is a unique harmonic interpolation, provided

L

is a second-order differential operator with a non-trivial second-order part (i e

β_{2} \neq 0

) or a non-zero first-order part (i e

β_{2} \neq 0

Proof sketch. The uniqueness is a consequence of the maximum principle for harmonic functions. The existence follows (in our one-dimensional setting) by distinguishing the cases delineated in the statement of the Lemma. If $L$ is a second-order operator and it has only a non-zero term of second order, then the space of solutions are all affine-linear functions from $R$ to $R$ . This space is two-dimensional. If there are terms of different order, the space of solutions will have basis elements of the form $exp (α \cdot)$ and we have to solve a linear or quadratic equation to find the $α$ (or $α$ ’s) satisfying this linear or quadratic equation. Since $L$ is sub-Markovian, there will be at least one real solution to this equation for $α$ .

The Lemma implies

Corollary 1. There cannot be more than two linearly independent harmonic functions: There is a canonical monomorphism from the space of functions to the – two-dimensional – space of pairs of subordinates.

Lemma 2. A subharmonic function from

R

R

is constantly zero if it has three zeros.

Proof. The leftand right-differentiablility of subharmonic functions entail that for all subharmonic $g$ , $L g$ will be defined as a function from $R$ to $R \cup {\pm \infty}$ .

If there is only a first order non-zero term, the space of harmonic functions will just coincide with the space of constant functions.

Lemma 3.

1. Piecewise harmonic interpolation with respect to the support abscissas ${a_{0}, . . ., a_{m}}$ preserves subharmonicity on $[a_{0}, a_{m}]$ : The interpolating function dominates the interpolated function on $A : = [a_{0}, a_{m}]$ , and if the interpolating function $f$ equals the harmonic function $f_{i}$ on $[a_{i}, a_{i + 1}]$ for all $i < m$ , then we have $f = sup {f_{0}, . . ., f_{m - 1}}$ .
2. The interpolating function $f$ is strictly dominated by the interpolated function $ℐ (f)$ on the intervals $(- \infty, a_{0})$ and $(a_{m}, + \infty)$ .

Proof sketch.
- 1. The domination part follows from the maximum principle for harmonic functions. From the maximum principle, we also get for all $i < m - 1$ that if $f_{i} \neq f_{i + 1}$ , then ${f_{i} = f_{i + 1}} = {a_{i + 1}} .$ Now there are two possibilities: either $f_{i} < f_{i + 1}$ on $(- \infty, a_{i + 1})$ and $f_{i} > f_{i + 1}$ on $(a_{i + 1}, + \infty)$ or the other way round $f_{i} > f_{i + 1}$ on $(- \infty, a_{i + 1})$ and $f_{i} < f_{i + 1}$ on $(a_{i + 1}, + \infty)$ . However, in the former case, the interpolating function would equal $f_{i} \land f_{i + 1}$ on $[a_{i}, a_{i + 2}]$ , which is superharmonic, and it would also dominate the subharmonic interpolated function $η$ on $[a_{i}, a_{i + 2}]$ .
  Then, $η - (f_{i} \land f_{i + 1})$ would be nonpositive and subharmonic on $[a_{i}, a_{i + 2}]$ and it would have three zeroes, in $a_{i}$ , $a_{i + 1}$ and $a_{i + 2}$ . By Lemma 2 , this can only be true if $η - (f_{i} \land f_{i + 1}) = 0$ on $[a_{i}, a_{i + 2}]$ . Thus, $η = f_{i} \land f_{i + 1}$ on $[a_{i}, a_{i + 2}]$ . Since $η$ is subharmonic on $[a_{i}, a_{i + 2}]$ , so must be $f_{i} \land f_{i + 1}$ then, and therefore, $f_{i} \land f_{i + 1}$ is harmonic on $[a_{i}, a_{i + 2}]$ . This means $f_{i} = f_{i + 1}$ (as both $f_{i}$ and $f_{i + 1}$ are harmonic) which contradicts our assumption that $f_{i} \neq f_{i + 1}$ . Therefore, $f_{i} > f_{i + 1}$ on $(- \infty, a_{i + 1})$ and $f_{i} < f_{i + 1}$ on $(a_{i + 1}, + \infty)$ for all $i < m$ .
  Inductively, this yields $f \geq f_{i}$ on $[a_{0}, a_{m}]$ for all $i < m$ , hence $f = sup {f_{0}, . . ., f_{m - 1}}$ on $[a_{0}, a_{m}]$ .
- 2. The function $f - ℐ (f)$ is subharmonic on $(- \infty, a_{1}]$ and it has two zeroes in $a_{0}$ and $a_{1}$ . Moreover, it is nonpositive on $(a_{0}, a_{1})$ . Because of Lemma 2 , then $f - ℐ (f)$ has to be positive or negative on $(- \infty, a_{0})$ .
  In the former case, we are done. In the latter case, due to the maximum principle, $f - ℐ (f)$ must be decreasing and therefore in $a_{0}$ we would have $L (f - ℐ (f)) (a_{0}) < 0$ , which is absurd. A symmetric argument works for the proof of the domination of $ℐ (f)$ by $f$ on the interval $(a_{m}, + \infty)$ .

Lemma 4. Piecewise harmonic interpolation to a set of support absicssas

{a_{0}, . . ., a_{m}}

is monotone on

[a_{0}, a_{m}]

in the sense that if

f \leq g

[a_{0}, a_{m}]

, then the piecewise harmonic interpolation of

f

will be dominated by the piecewise harmonic interpolation of

g

[a_{0}, a_{m}]

Proof. Use the maximum principle on each of the intervals $[a_{i}, a_{i + 1}]$ for $i < m$ .

Lemma 5. Let

ℐ : R^{[a_{0}, a_{m}]} \to R^{R}

denote the operator of piecewise harmonic interpolation with respect to the set of support abscissas

{a_{0}, . . ., a_{m}}

. Let

f : R \to R

be subharmonic on

R

. Consider a harmonic function

h : R \to R

, assumed to dominate

f

f \leq h

R

. Then

ℐ (f) \leq h

R

Proof. From the previous Lemma 4 , we already know that $ℐ (f) (x) \leq ℐ (h) (x)$ holds for all $x \in [a_{0}, a_{m}]$ . However, $ℐ (h) = h$ , hence $ℐ (f) \leq h$ on $[a_{0}, a_{m}]$ and from Lemma 3 , we conclude that $h \geq f \geq ℐ (f)$ on the intervals $(- \infty, a_{0})$ and $(a_{m}, + \infty)$ .

Theorem 1. Let

ℐ : R^{[a_{0}, a_{m}]} \to R^{R}

again denote the operator of piecewise harmonic interpolation with respect to the set of support abscissas

{a_{0}, . . ., a_{m}}

. Let

g

be a subharmonic function, let

c

be nonnegative and subharmonic, and let

h

be harmonic. Let

c

be, moreover, harmonic on each of the intervals

[a_{i}, a_{i + 1}]

for

i < m

Suppose

c \leq g

[a_{0}, a_{m}]

and

c, g \leq h

R

r > 0

and let

t > 0

Now define

K : f \mapsto ℐ (e^{- r t} P_{t} (ℐ (f) \lor c) \lor g) ↾ [a_{0}, a_{m}]

as well as

Q : = {f ↾ [a_{0}, a_{m}] : \begin{matrix} f : R \to R subharmonic, f \geq c on [a_{0}, a_{m}], \\ \forall i \in {1, . . ., m - 2} f harmonic on [a_{i}, a_{i + 1}], \\ f harmonic on (- \infty, a_{1}), (a_{m - 1}, + \infty), f \leq h \end{matrix}} .

Then

K

maps the convex and bounded subset

Q

C^{0} [a_{0}, a_{m}]

continuously to itself. Moreover, due to Lemma 1 ,

Q

is a subset of a finite-dimensional subspace of

C^{0} [a_{0}, a_{m}]

(this subspace being the space of all functions from

[a_{0}, a_{m}]

that are harmonic on each of the intervals

[a_{i}, a_{i + 1}]

for

i < m

. By Brouwer’s Fixed Point Theorem,

K

has got a fixed point in

Q

. Finally,

K

is a composition of monotone functions on

[a_{0}, a_{m}]

and therefore monotone as well.

Proof sketch. We can divide the proof for K ( Q ) ⊆ Q into three parts:
- 1. The cone of subharmonic functions is closed under $\lor$ , under $P_{t}$ , under multiplication by constants and under piecewise harmonic interpolation $ℐ$ (cf Lemma 3 ), therefore the image of $Q$ under $K$ can only consist of subharmonic functions.
- 2. The upper bound on the elements of the image $K (Q)$ follows from the monotonicity of $P_{t}$ and $ℐ$ (Lemma 4 ), combined with the equations $P_{t} h = h$ and $ℐ (h) = h$ as well as the Lemma 5 : First, we may state $e^{- r t} P_{t} (ℐ (f) \lor c) \lor g \leq h$ for all $f \leq h$ , which by Lemma 5 allows us to deduce $ℐ (e^{- r t} P_{t} (ℐ (f) \lor c) \lor g) \leq h$ for all $f \in Q$ .
- 3. The lower bound follows again from the monotonicity of $ℐ$ , but this time only by exploiting $c \leq g$ on $[a_{0}, a_{m}]$ and employing the fact that the space of those functions that are harmonic on each of the intervals $[a_{i}, a_{i + 1}]$ for $i < m$ is invariant under the composition of $ℐ$ with the restriction to $[a_{0}, a_{m}]$ (yielding $ℐ (c) = c$ on $[a_{0}, a_{m}]$ ).
Since c is nonnegative, we get that Q is bounded by sup [ a 0 , a m ] h ≥ 0 as a subset of C 0 [ a 0 , a m ] , and because Q is finite-dimensional, we may apply Schauder’s Theorem, provided we are given the continuity of K . However, this last assertion follows from the maximum principle.

The existence of a minimal fixed point for

K

can be proven constructively as well:

Corollary 2. Let us adopt the notation of the previous Theorem. Then the sequence

{(K^{n} (g \lor 0))}_{n \in N_{0}}

is monotone on

[a_{0}, a_{m}]

, bounded and dominated by

h

. Therefore we have the existence of a limit on

[a_{0}, a_{m}]

given by

\forall x \in [a_{0}, a_{m}] q (x) : = {lim}_{n \to \infty} K^{n} (g \lor 0) (x) = {sup}_{n \in N_{0}} K^{n} (g \lor 0) (x) .

This limit is an element of

Q

and therefore can be canonically extended to the whole of

R

. By the continuity of

K

q

is a fixed point of

K

. On

[a_{0}, a_{m}]

, the convergence in the last equation will be uniform.

Proof. The only part of the Corollary that does not follow directly from the preceding Theorem 1 is the uniformity of the convergence and that $q$ will be harmonic on each of the intervals $[a_{i}, a_{i + 1}]$ for $i < m$ . However, monotone convergence on compact sets preserves harmonicity and is always uniform (cf e g Meyer [3] – or, more directly, Port and Stone [4,Theorem3.9] if $P$ is the Brownian semigroup).

Lemma 6. In the preceding Corollary’s notation,

q

is the minimal nonnegative fixed point of

K

Proof. Any nonnegative fixed point $p$ of $K$ must be greater or equal $g$ on $[a_{0}, a_{m}]$ .
Therefore the monotonicity of $K$ on $[a_{0}, a_{m}]$ , implies $\forall n \in N_{0} p = K^{n} p \geq K^{n} (g \lor 0) on [a_{0}, a_{m}],$ yielding $p \geq {sup}_{n \in N_{0}} K^{n} (g \lor 0) = q on [a_{0}, a_{m}] .$

Example 1 (Bermudan vanilla put in a special Black-Scholes model). Assume

P : = (P_{t})_{t \geq 0} : = {(ν_{- μ t, σ^{2} t} * \cdot)}_{t \geq 0},

where

σ > 0, μ : = r - \frac{σ^{2}}{2},

thus

P

can be perceived as the semigroup associated to the logarithmic price process under the risk-neutral measure in the one-dimensional Black-Scholes model). We will assume that (possibly after a linear change of the time scale)

σ = 1

. Define

g : = K - exp .

(the payoff on exercise of a one-dimensional put option with strike price

K

). The infinitesimal generator of the Markov semigroup

P

L = \frac{1}{2} Δ - μ \nabla .

Thus, if we assume

\begin{matrix} 1 - 2 μ = 1 - 2 r + σ^{2} \leq 0, \end{matrix}

(1)

that is,

μ \geq \frac{1}{2}

, we obtain

L g = - (\frac{1}{2} - μ) exp \geq 0,

hence

g

is, given the condition ( 1 ),

P

-subharmonic. We can find the

P

-harmonic functions for

μ \neq 0

(otherwise they are simply the affine linear functions) by observing that for all

α \in R

\begin{matrix} 0 = L exp (α \cdot) = \frac{1}{2} (α^{2} - 2 μ α) exp (α) \end{matrix}

\begin{matrix} \Leftrightarrow & α \in {0, 2 μ} . \end{matrix}

μ \neq 0

, the functions

1 : x \mapsto 1

and

exp (2 μ \cdot) : x \mapsto e^{2 μ x}

are two linearly independent harmonic functions, thus by Corollary 1 , we have already found a basis for the space of harmonic functions. If

μ = 0

, the harmonic functions are exactly the affine linear functions. In order to obtain the setting of Theorem 1 , we will assume

μ = \frac{1}{2}

, thereby making

g = K - exp

(the payoff on exercise of a put option with strike price

K

) as well as

h = K

harmonic. Then clearly

g \leq h

. In order to satisfy the conditions on

c

if we set

c = 0

, we could assume in addition

a_{m} \leq ln K

(where

a_{m}

is the maximal support abscissa) for instance.

3 Reduite-based approximation of Bermudan option prices

Suppose

P

is a Markov semigroup on

R^{d}

(

d \in N

) and

L

is the infinitesimal generator of

P

. We will call a function

f : R^{d} \to R

subharmonic if and only if

\forall t > 0 P_{t} f \geq f

holds pointwise. A function

f : R^{d} \to R

will be called superharmonic if and only if

- f

is subharmonic, and

f : R^{d} \to R

will be called harmomic if it is both superand subharmonic.

Let

U

denote the operator of upper-semicontinuous regularisation, that is, for all functions

f : R^{d} \to R

U f = inf {ℓ \geq f : ℓ : R^{d} \to R subharmonic}

(of course, this is a priori only defined as a function taking values in

R \cup {- - \infty}

Consider a harmonic function

h : R^{d} \to R

and a closed

F_{σ}

set

B

and define the reduite operator

ℛ = ℛ_{h, B}

on the set of all subharmonic functions

f : R^{d} \to R

dominated by

h

via

ℛ f : = U (sup {ℓ \leq h : ℓ : R^{d} \to R subharmonic, ℓ \leq f on B}) .

It is a well-known result from potential theory (cf e g the work of Paul-Andre Meyer [3,TheoremeT22] ) that there will be a greatest subharmonic function dominated by

f

B

and that this function will be equal to

ℛ f

. Moreover, we have that

f = ℛ f

B

except on a set of potential zero, in probabilistic/potential-theoretic jargon

f = ℛ f q.e. on B,

where “q.e.” is, as usual, short-hand for “quasi-everywhere”. Now define

Q : = {f \leq h : f : R^{d} \to R subharmonic} .

Then our definition of the reduite operator

ℛ

implies

ℛ f \leq h

(as

h

is dominating the function whose upper-semicntinuous regularisation is, according to our definition, the reduite

ℛ f

f

) and our potential-theoretic characterisation of the reduite – as the greatest subharmonic function dominated by

f

B

– ensures the subharmonicity of

ℛ f

. Therefore,

ℛ : Q \to Q .

We also have that

U

is monotone (in the sense that for all

f_{0} \leq f_{1}

U f_{0} \leq U f_{1}

) so that

ℛ

must be monotone as well (from the

\subseteq

-monotonicity of

sup

and the definition of

ℛ

Hence

Lemma 7. Adopting the notation of the preceding paragaph,

ℛ : Q \to Q

and whenever

f_{0} \leq f_{1}

ℛ f_{0} \leq ℛ f_{1}

Let

g : R^{d} \to R

be a subharmonic function such that

g \leq h

and let

r > 0

. The next step is going to be the consideration of the following family of operators:

φ_{t} : f \mapsto e^{- r t} P_{t} f \lor g

for

t \geq 0

. If

f \leq h

P_{t} f \leq P_{t} h = h

for all

t \geq 0

, since the operators

P_{t}

are positive and linear, and

h

was assumed to be harmonic. Thus, since

g \leq h

and

r > 0

, one must have

φ_{t} f \leq h

for all

f \leq h

and

t \geq 0

. Moreover, the operators

P_{t}

preserve subharmonicity and the maximum of two subharmonic functions is subharmonic again, therefore

φ_{t} f

must be subharmonic for all subharmonic

f

. Finally, since

P_{t}

is monotone,

φ_{t}

has to be monotone for all

t \geq 0

Summarising this, we obtain

Lemma 8. Using the notation introduced previously,

φ_{t} : Q \to Q

and whenever

f_{0} \leq f_{1}

φ_{t} f_{0} \leq φ_{t} f_{1}

for all

t \geq 0

As a consequence, we derive from the two Lemmas 7 and 8 the following:

Corollary 3. If we define

K_{t} : = ℛ \circ φ_{t}

(adopting the notation of the previous paragraph), we have

K_{t} : Q \to Q

and whenever

f_{0} \leq f_{1}

K_{t} f_{0} \leq K_{t} f_{1}

This already suffices to prove the following

Theorem 2. Let

t \geq 0

. Then for all

n \in N_{0}

\begin{matrix} {K_{t}}^{n + 1} (g \lor 0) \geq {K_{t}}^{n} (g \lor 0) . \end{matrix}

(2)

Furthermore,

q : = {sup}_{n \in N_{0}} {K_{t}}^{n} (g \lor 0)

(which a priori is only defined as a function with range in

R \cup {+ \infty}

) is an element of

Q

and indeed is the least nonnegative fixed point of

K_{t}

Proof.

1. The proof of equation ( 2 ) is a straightforward induction on $n$ where we have to use the monotonicity of $K_{t}$ in the induction step.

2. Since

K_{t}

maps

Q

to itself, the whole sequence

{({K_{t}}^{n} (g \lor 0))}_{n \in N_{0}}

is bounded by

h

. This entails

q \leq h

as well. Applying Beppo Levi’s Theorem on swapping

sup

and

\int \cdot d μ

– for bounded monotonely increasing sequences of measurable nonnegative functions and an arbitrary measure

μ

– to the measures

P_{t} (\cdot, x)

x \in R^{d}

and the sequence

{({K_{t}}^{n} (g \lor 0))}_{n \in N_{0}}

, we can exploit the subharmonicity of the functions

{K_{t}}^{n} (g \lor 0)

n \in N_{0}

, to deduce

\begin{matrix} \forall x \in R^{d} P_{t} q (x) & = & {sup}_{n \in N_{0}} P_{t} ({K_{t}}^{n} (g \lor 0)) (x) \end{matrix}

\begin{matrix} \geq & {sup}_{n \in N_{0}} {K_{t}}^{n} (g \lor 0) (x) = q (x), \end{matrix}

which is the subharmonocity of

q

. As we have already seen,

q \leq h

, so

q \in Q

3. If we employ Beppo Levi’s Theorem again, we can show that $K_{t}$ and ${sup}_{n \in N_{0}}$ commute for bounded monotonely increasing sequences of functions.
Thereby $K_{t} q = {sup}_{n \in N_{0}} K_{t} {K_{t}}^{n} (g \lor 0) = {sup}_{n \in N} {K_{t}}^{n} (g \lor 0) = q .$
4. Any nonnegative fixed point $p$ of $K_{t}$ must be greater or equal $g \lor 0$ .
Therefore by the monotonicity of $sup$ and $K_{t}$ , ${sup}_{n \in N_{0}} {K_{t}}^{n} p \geq {sup}_{n \in N_{0}} {K_{t}}^{n} (g \lor 0) = q .$

Example 2 (Bermudan put option with equidistant exercise times in

t \cdot N_{0}

on the weighted arithmetic average of a basket in a special Black-Scholes model). Let

β_{1}, . . ., β_{d} \in [0, 1]

be a convex combination and

{(P_{t})}_{t \geq 0} = {(ν_{- t / 2, t})}_{t \geq 0}

. Then one has

L = \frac{1}{2} Δ - (\frac{1}{2}, \dots, \frac{1}{2}) \cdot \nabla

(cf e g Revuz and Yor’s exposition [5] ), and both

g : x \mapsto K - \sum_{i = 1}^{d} β_{i} exp (x_{i})

and

h : = K

(where

K \geq 0

is the option’s strike price) are harmonic.

Moreover, obviously

g \leq h

. This allows us to deduce that whatever closed

F_{σ}

-set

B \subset R^{d}

we choose (for the sake of computational efficiency one could think of a triangulisation for instance), the (perpetual) Bermudan option pricing algorithm that iteratively applies

K_{t}

(where

t > 0

is the exercise mesh size of the option) to the payoff function

g \lor 0

on the

log

-price space, will monotonely increase and will have a limit which is the smallest nonnegative fixed point of

K_{t}

Acknowledgements. This work originates from research conducted by the author for his doctoral thesis at the University of Oxford. The author is highly indebted to Professor Terry Lyons for numerous helpful discussions. Furthermore, he gratefully acknowledges funding from the German Academic Exchange Service (Doktorandenstipendium des Deutschen Akademischen Austauschdienstes).

References

K Ito, H P McKean Jr, Diffusion processes and their sample paths, Grundlehren der mathematischen Wissenschaften 125, Springer, Berlin 1974.
T J Lyons, personal communication.
P-A Meyer, Probabilites et potentiel, Actualites scientifiqes et industrielles 1318, Hermann, Paris 1966.
S C Port, C J Stone, Brownian motion and classical potential theory, Academic Press, New York 1978.
D Revuz, M Yor, Continuous martingales and Brownian motion, 3rd ed, Grundlehren der mathematischen Wissenschaften 293, Springer, Berlin 1999.
D Stroock, Probability theory – an analytic view, Cambridge University Press, Cambridge 1993.

Bermudan option pricing based on piecewise harmonic interpolation and the reduite

F S Herzberg, Merton College, University of Oxford, Oxford OX1 4JD

November 27, 2006