The Design and Analysis of Lattice Algorithms for Multivariate Option Pricing Models

衍生性金融商品是一種財務工具，其投資收益取決於一些基本的金融資產。它們是推測與風險管理的根本工具。對於衍生性金融商品的評價的方法，大多數的商品並不存在分析方程式解。當此狀況發生時，衍生性金融商品就必須使用數值方法來評價，例如：樹狀方法。本論文著重於多變數評價模型的樹狀方法，包含 GARCH (generalized autoregressive conditional heteroskedastic) 種類的模型、Hilliard-Schwartz 模型 (簡稱為 HS 模型)、 Hull-White 模型 (簡稱為 HW 模型)、 SABR 模型、 Chambers-Lu 模型 (簡稱為 CL 模型) 與多資產選擇權。令 n 表示樹狀方法評價的期數與 Δt 表示每一期的時間長度。對於 GARCH 種類的模型評價，本論文證明當 n 超過某一個門檻值時， Ritchken-Trevor 樹狀方法的樹狀模型大小呈指數成長，而當 n 不超過某一個門檻值，平均追蹤 (mean-tracking) 樹狀方法的樹狀模型大小呈二次方成長。Hilliard 與 Schwartz 對於他們的模型提出一個其樹狀模型大小呈三次方成長的樹狀方法 (簡稱為 HS 樹狀方法)。但本論文將証明 HS 樹狀方法本質上會有負的轉移機率以及任何對於 HW、 SABR 及 HS 模型所建構的合法樹狀模型其大小都至少會有次指數的成長率。對於評價多資產選擇權的樹狀方法，本論文定義一樹狀方法為最佳必須滿足對於所有資產間介於-1+O(Δt^0.5) 與 1-O(Δt^0.5) 之間的相關係數都能保證所有轉移機率都合法。本論文對於文獻上的許多樹狀方法其最佳化與評價障礙選擇權的能力做分析。本論文提出一個全新多資產選擇權樹狀方法名為六元 (hexanomial) 樹狀方法，本方法能使得某一層的節點與其中一個資產對應的障礙吻合以得到優越的收斂，同時證明在評價雙資產選擇權的狀況此樹狀方法為最佳。最後，為了瞭解 GPU (graphics processing unit) 的大量運算能力，本論文以 CL 樹狀方法為例子，將其實做可於 GPU 與 CPU (central processing unit) 上運算。實驗結果顯示 GPU 的運算可以較 CPU 運算減少至少一百倍以上的運算時間。Financial derivatives are financial instruments whose payoff depends on some fundamental financial assets. They are essential tools for speculation and risk-management. For pricing derivatives, analytical formulas are rare for most ones. When this happens, derivatives must be priced by numerical methods such as lattices. This thesis focuses on the lattices for the multivariate pricing models including GARCH (generalized autoregressive conditional heteroskedastic)-type models, the Hilliard-Schwartz (HS) model, which nests the Hull-White (HW) and SABR models, the Chambers-Lu (CL) model, and the multi-asset options. Let n denote the number of time steps and Δt denote the duration of a time step. This thesis proves that the Ritchken-Trevor lattice for GARCH-type models explodes if n exceeds some threshold and the mean-tracking lattice for GARCH-type models grows only quadratically if n does not exceed some threshold. Hilliard and Schwartz give a cubic-time lattice for their model. But this thesis proves that the HS lattice inherently has negative transition probabilities and any valid lattices for the HW, SABR, and HS models must have at least a subexponential complexity. A lattice for multi-asset options is said to be (correlation) optimal if it guarantees validity as long as the correlations between all pairs of assets fall within −1+O(Δt^0.5) and 1−O(Δt^0.5). Many lattices in the literature are analyzed in the thesis according as their optimality and ability to handle barrier options. This thesis proposes a new multi-asset lattice called the hexanomial lattice that can align a layer of lattice nodes with a barrier for each asset for excellent convergence and is provably optimal for the bivariate case. Finally, to exploit the massive computing power of GPUs (graphics processing units), this thesis takes the CL lattice as an example and implements it on the GPU and CPU (central processing unit). The numerical results show that up to a hundred-fold speedup can be achieved by the GPU over the CPU.Contents Page Chinese Abstract i Abstract iii Contents iv List of Figures viii List of Tables x 1 Introduction 1 1.1 Derivatives and Their Pricing . . . . . . . . . . . . 1 1.2 A Quick Review of Background Knowledge . . . . . . . 3 1.2.1 Options . . . . . . . . . . . . . . . . . . . . . . 4 1.2.2 Bivariate Lattices . . . . . . . . . . . . . . . . 5 1.2.3 Pricing Methods for Multi-Asset Options . . . . . . 6 1.3 Motivations and Problem Statements . . . . . . . . . 7 1.4 Summary of Results . . . . . . . . . . . . . . . . . 8 2 Preliminaries 10 2.1 Ito Process and Ito’s Lemma . . . . . . . . . . . . 10 2.2 Stock Price Dynamics . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.1 The Stock Price and Geometric Brownian Motion .. . 11 2.2.2 The SV Models . . . . . . . . . . . . . . . . . . 11 2.2.2.1 GARCH-Type Models . . . . . . . . .. . . . . . . 11 2.2.2.2 The HS Model . . . . . . . . . . . . . . . . . 12 2.3 A Quick Review of Financial Knowledge . . . . . . .. 13 2.4 Lattice and Pricing . . . . .. . . . . . . . . . . . 14 2.4.1 A Lattice for Geometric Brownian Motion . . . .. . 14 2.4.2 Pricing with Backward Induction on a Lattice . . . 15 2.4.3 Axioms for Lattices . . . . . . . . . . . .. . . . 16 2.4.4 Justifications for the Axioms . . . . . . . . .. . 17 2.5 Lattice Size and Its Growth Rate . . . . . . . . . . 19 3 Complexities of the RT and MT Lattices for GARCH-Type Models 21 3.1 The RT Lattice . . . . . . . . . . . . . . . . . . . 21 3.2 The MT Lattice . . . . . . . . . . . . . . . . . . . 24 3.3 Complexity Analysis . . . . . . . . . . . . . . . . 26 3.3.1 NGARCH . . . . . . . . . . . . . . . . . . . . . . 26 3.3.1.1 The Explosion Threshold . . . . . . . . . . . . 26 3.3.1.2 The Non-Explosion Threshold . . . . . . . . . . 27 3.3.1.3 Numerical Results under the Explosion Condition 27 3.3.1.4 Numerical Results under the Non-Explosion Condition 27 3.3.2 LGARCH . . . . . . . . . . . . . . . . . . . . . . 29 3.3.2.1 The Explosion Threshold . . . . . . . . . . . . 29 3.3.2.2 The Non-Explosion Threshold . . . . . . . .. . . 31 3.3.2.3 Numerical Results under the Explosion Condition 31 3.3.2.4 Numerical Results under the Non-Explosion Condition 31 3.3.3 AGARCH . . . . . . . . . . . . . . . . . . . . . 33 3.3.3.1 The Explosion Threshold . . . . . . . . . . . . 33 3.3.3.2 The Non-Explosion Threshold . . . . . . . . . . 33 3.3.3.3 Numerical Results under the Explosion Condition 35 3.3.3.4 Numerical Results under the Non-Explosion Condition 35 3.3.4 GJR-GARCH . . . . . . .. . . . . . . . . . . . . . 37 3.3.4.1 The Explosion Threshold . . . . . . . . .. . . . 37 3.3.4.2 The Non-Explosion Threshold . . . . . . . . . . 37 3.3.4.3 Numerical Results under the Explosion Condition 38 3.3.4.4 Numerical Results under the Non-Explosion Condition 38 3.3.5 TS-GARCH . . . . . . . . . . . . . . . . . . . . . 40 3.3.5.1 The Explosion Threshold . . . . . . . . . . .. . 41 3.3.5.2 The Non-Explosion Threshold . . . . . . . . . . 42 3.3.5.3 Numerical Results under the Explosion Condition 44 3.3.5.4 Numerical Results under the Non-Explosion Condition 45 3.3.6 TGARCH . . . . . . . . . . . . . . . . . . . . . . 46 3.3.6.1 The Explosion Threshold . . . . . . . . . . . . 46 3.3.6.2 The Non-Explosion Threshold . . . . . . . . . . 46 3.3.6.3 Numerical Results under the Explosion Condition 47 3.3.6.4 Numerical Results under the Non-Explosion Condition 47 3.3.7 Summary of Thresholds of GARCH-Type Models . . . . 49 4 Complexity Analysis of the HS Model 51 4.1 Preliminaries . .. . . . . . . . . . . . . . . . . . 51 4.1.1 The NR Transformation and Its Uniqueness . . . . . 51 4.1.2 Basic Results for Lattices . . . . . . . . . . . . 54 4.2 The NR Transformations for the HS Model . . . . . . .57 4.3 The Fundamental Problems with the HS Lattice . . . . 59 4.3.1 A Brief Review of the HS Lattice . . . . . . . . . 59 4.3.2 Negative Probabilities of the HS Lattice . . . . . 61 4.4 The Complexity of the HS Model . . . . . . . . . . . 62 4.4.1 The Proof . . . . . . . . . . . . . . . . . . . . 62 5 Lattices for Multi-Asset Options 70 5.1 Analysis of Multi-Asset Lattices . . . . . . . . . . 70 5.1.1 The 4-Jump Bivariate Lattice of Boyle et al. . . . 71 5.1.2 The Pyramid of Rubinstein . . . . . . . . . . . . .71 5.1.3 The 5-Jump Bivariate Lattice of Boyle . . . . . . .72 5.1.4 The 9-Jump Bivariate Lattice of Lin . . . . . . . .72 5.1.5 The 4-Jump Bivariate Lattice of Hahn and Dyer . . .74 5.2 The Hexanomial Lattice . . . . . . . . . . . . . . . 75 5.2.1 The First Phase . . . . . . . . . . . . . . . . .. 77 5.2.2 The Second Phase . . . . . . . . . . . . . . . . . 77 5.2.3 The First Moments of ζi(t, Δt) over One Time Step . . . . . . 79 5.2.4 The Second Moments of ζi(t, Δt) over One Time Step . . . . 79 5.2.5 The Correlation of ζ1(t, Δt) and ζ2(t, Δt) over One Time Step 80 5.2.6 The Complexity of the Hexanomial Lattice for the Bivariaten Option . . . 82 5.2.7 The Higher-Dimensional Hexanomial Lattice . . .. . 87 5.3 Numerical Results . . . . . . . . . . . . . . . . . 88 5.3.1 The Maximum Option . . . . . . . . . . . . . . . . 88 5.3.2 The Spread Option . . . . . . . . . . . . . . . .. 88 5.3.3 The Dual-Strike Option . . . . . . . . . . . . . . 90 5.3.4 The Dual-Strike Option with a Knock-Out Barrier on Each Asset . . . . . . . . . . . . . . . . . . . . . . 90 5.3.5 The Cases with Near ±1 Correlations . . . . . . . 91 6 Speedup of Computation on a Bivariate Lattice by the GPU 93 6.1 Computation on the CPU and the GPU . . . . . . . . . 93 6.2 Compute Unified Device Architecture (CUDA) . . . . . 93 6.3 Experimental Results . . . . . . . . . . . . . . . . 94 6.3.1 Performance of the GPU Implementation with Multiple Threads but without Memory Optimization .. . . . . . . . 95 6.3.2 Performance of the GPU Implementation with Multiple Threads and Memory Optimization . . . . . . . . . . . . 96 7 Conclusion 98 Bibliography 10