American Options - Computational Methods for Quantitative Finance - page 72

Ta b l e 5 . 2 Description of the primal-dual active set algorithm
Choose an initial guess x 0 ≥ c , λ 0

≥

0.

Choose ε> 0.
For k = 0 , 1 , 2 ,... ,

Set I k λ i k 1 (c i x i ) ={ i : + − ≤ 0 } ,

A k ={ i : λ i + k 1 (c i − x i )> 0 }

Solve A x k + 1 λ k + 1 b , x k + 1 c on A k , λ k + 1

+ = = = 0 on I k .

x k + 1 − x k

If

2 <ε stop else

Next k

Note that assumption (i) of Proposition 5.4.1 ensures the existence of a unique
solution of ( 5.11 ).

5.4.2 Primal-Dual Active Set Algorithm

N

Problem ( 5.11 ) can be formulated as follows: find x , λ ∈ R such that

A x + λ = b ,

x ≥ c,

(5.12)

≥

λ 0 ,

( x − c ) λ = 0 .

Problem ( 5.12 ) was solved by Ito and Kunisch [84] using the primal-dual active
set algorithm that can also be formulated as a semi-smooth Newton method for P-
matrices A . A matrix is called a P-matrix if all its principal minors are positive.
This can be shown to hold in our setup for the FEM discretization as well as for the
FDM discretization for sufficiently small time-step k . The complementarity system
in ( 5.12 ) can equivalently be expressed as

C ( x,λ ) = 0 , where C ( x,λ ) := λ − max ( 0 , λ + k 1 ( c − x) ),

for each k 1 > 0. Therefore, ( 5.12 ) is equivalent to

A x + λ = b ,

(5.13)

C ( x , λ ) = 0 .

The primal-dual active set algorithm is based on using ( 5.13 ) for a prediction strat-
egy, i.e. given a pair ( x , λ ) , the active and inactive sets are given as

I ={ i : λ i + k 1 (c i − x i ) ≤ 0 } , A ={ i : λ i + k 1 (c i − x i )> 0 } .

This leads to the algorithm given in Table 5.2 .