Numerical Methods and Optimization in Finance

Numerical Methods and Optimization in Finance......Page 1
Numerical Methods and Optimization in Finance......Page 2
Copyright......Page 3
List of Algorithms......Page 4
Acknowledgements......Page 6
1.1 About this book......Page 7
1.2 Principles......Page 9
1.3 On software......Page 11
1.4 On approximations and accuracy......Page 15
1.5 Summary: the theme of the book......Page 20
Representation of real numbers......Page 21
Example of limitations of floating point arithmetic......Page 24
2.2 Measuring errors......Page 25
Approximating first-order derivatives......Page 26
Partial derivatives......Page 27
Truncation error for forward difference......Page 28
Example of a numerically unstable algorithm......Page 30
Example of an ill-conditioned problem......Page 31
2.5 Condition number of a matrix......Page 32
Comments and examples......Page 33
2.6.1 Criteria for comparison......Page 35
Order of complexity and classification......Page 36
2.A Operation count for basic linear algebra operations......Page 37
3 Linear equations and Least Squares problems......Page 38
3.1.1 Triangular systems......Page 39
3.1.2 LU factorization......Page 40
LU factorization with Matlab......Page 41
3.1.3 Cholesky factorization......Page 43
The Cholesky algorithm......Page 44
3.1.4 QR decomposition......Page 46
3.2 Iterative methods......Page 47
3.2.1 Jacobi, Gauss–Seidel, and SOR......Page 48
Successive overrelaxation......Page 49
3.2.2 Convergence of iterative methods......Page 51
3.2.3 General structure of algorithms for iterative methods......Page 52
3.2.4 Block iterative methods......Page 55
3.3.1 Tridiagonal systems......Page 56
3.3.2 Irregular sparse matrices......Page 58
Sparse matrices in Matlab......Page 59
Structural rank......Page 60
Block triangular decomposition......Page 61
Structurally singular matrices......Page 62
3.4 The Least Squares problem......Page 63
3.4.1 Method of normal equations......Page 64
Computation of (A'A)-1......Page 65
3.4.2 Least Squares via QR factorization......Page 67
3.4.3 Least Squares via SVD decomposition......Page 68
The backslash operator in Matlab......Page 70
4.1 An example of a numerical solution......Page 72
A first numerical approximation......Page 73
A second numerical approximation......Page 74
4.2 Classification of differential equations......Page 76
4.3 The Black–Scholes equation......Page 77
4.3.2 Initial and boundary conditions and definition of the grid......Page 79
4.3.3 Implementation of the θ-method with Matlab......Page 85
4.3.4 Stability......Page 88
4.3.5 Coordinate transformation of space variables......Page 91
4.4 American options......Page 93
4.A A note on Matlab's function spdiags......Page 104
5.1 Motivation......Page 106
Matching moments......Page 107
5.2 Growing the tree......Page 108
Numerical implementation......Page 109
5.2.2 Vectorization......Page 110
5.2.3 Binomial expansion......Page 111
Numerical implementation......Page 112
5.3 Early exercise......Page 113
5.4 Dividends......Page 114
Delta Δ......Page 116
Theta Θ......Page 117
6.1.1 How it all began......Page 120
6.1.2 Financial applications......Page 121
6.2.1 Congruential generators......Page 122
6.2.2 Mersenne Twister......Page 125
6.3.1 The inversion method......Page 126
6.3.2 Acceptance–rejection method......Page 128
The Box–Muller method......Page 130
Marsaglia's polar method......Page 132
6.4.2 Higher order moments and the Cornish–Fisher expansion......Page 133
6.4.3 Further distributions......Page 135
6.5.1 Discrete uniform selection......Page 137
6.5.2 Roulette wheel selection......Page 138
6.5.3 Random permutations and shuffling......Page 139
6.6.1 The basic problem......Page 140
General considerations …......Page 141
…and caveats......Page 142
6.6.3 Stratified sampling......Page 143
Antithetic variables......Page 144
Importance sampling......Page 145
6.7.1 Data randomization......Page 146
Basic concepts......Page 147
Parametric and nonparametric bootstraps......Page 149
6.8.1 Replicability and ceteris paribus analysis......Page 153
6.8.2 Available random number generators in Matlab......Page 154
6.8.3 Uniform random numbers from Matlab's rand function......Page 155
6.8.4 Gaussian random numbers from Matlab's randn function......Page 156
6.8.5 Remedies......Page 157
7.1.1 Linear correlation......Page 160
7.1.2 Rank correlation......Page 166
7.2.1 Concepts......Page 174
7.2.2 The Metropolis algorithm......Page 176
7.3.1 Concepts......Page 179
Metropolis sampling......Page 182
Direct sampling......Page 184
8.1 Setting the stage......Page 186
8.2.1 Terminal asset prices......Page 187
8.2.2 1-over-N portfolios......Page 189
8.2.3 European options......Page 191
8.2.4 VaR of a covered put portfolio......Page 194
8.3 Simple price processes......Page 197
8.4.1 Efficient versus adaptive markets......Page 199
8.4.2 Moving averages......Page 200
8.4.3 Autoregressive models......Page 201
8.4.4 Autoregressive moving average (ARMA) models......Page 203
8.4.5 Simulating ARMA models......Page 204
8.4.6 Models with long-term memory......Page 206
8.5.1 The concepts......Page 207
8.5.2 Autocorrelated time-varying volatility......Page 209
8.5.3 Simulating GARCH processes......Page 212
8.5.4 Selected further autoregressive volatility models......Page 215
GARCH-M......Page 216
T-GARCH......Page 217
N-GARCH......Page 218
8.6.1 Price–earnings models......Page 219
8.6.2 Models with learning......Page 221
8.7.1 Backtesting......Page 223
8.7.2 Bootstrap......Page 224
8.8 Agent-based models and complexity......Page 229
9.1.1 Basic concepts......Page 234
9.1.2 Bootstrap......Page 236
9.2.1 Basic concepts......Page 238
The Hill estimator......Page 239
Threshold choice......Page 241
9.3 Option pricing......Page 243
9.3.1 Modeling prices......Page 244
9.3.2 Pricing models......Page 247
Black–Scholes......Page 248
The Heston model......Page 257
9.3.3 Greeks......Page 259
Discrepancy......Page 262
Van der Corput sequences......Page 263
Dimensionality......Page 268
10.1 What to optimize?......Page 270
10.2.1 Problems......Page 272
10.2.2 Classical methods and heuristics......Page 274
10.3 Evaluating solutions......Page 275
Portfolio optimization with alternative risk measures......Page 277
Robust/resistant regression......Page 279
Agent-based models......Page 280
Calibration of option-pricing models......Page 281
Calibration of yield structure models......Page 282
10.5 Summary......Page 283
11.1.1 A naïve approach......Page 285
Graphical solution......Page 286
11.1.2 Bracketing......Page 287
11.1.3 Bisection......Page 288
11.1.4 Fixed point method......Page 290
Convergence......Page 292
11.1.5 Newton's method......Page 296
Comments......Page 298
11.2 Classical unconstrained optimization......Page 299
Convergence......Page 300
11.3.1 Newton's method......Page 301
11.3.2 Golden section search......Page 303
11.4.1 Steepest descent method......Page 304
11.4.2 Newton's method......Page 306
11.4.3 Quasi-Newton method......Page 308
11.4.4 Direct search methods......Page 309
Solution for nonlinear systems of equations in Matlab......Page 315
11.5.1 Problem statement and notation......Page 316
11.5.3 Levenberg–Marquardt method......Page 318
11.6.1 General considerations......Page 321
Jacobi, Gauss–Seidel, and SOR method......Page 323
11.6.3 Newton's method......Page 326
Broyden's method......Page 330
Damped Newton......Page 332
Solution by minimization......Page 333
11.7 Synoptic view of solution methods......Page 334
12.1 Heuristics......Page 335
12.2.1 Stochastic local search......Page 339
12.2.2 Simulated Annealing......Page 340
12.2.4 Tabu Search......Page 342
12.3.1 Genetic Algorithms......Page 343
12.3.2 Differential Evolution......Page 344
12.3.3 Particle Swarm Optimization......Page 345
12.3.4 Ant Colony Optimization......Page 346
12.4 Hybrids......Page 347
12.5 Constraints......Page 350
12.6.1 Stochastic solutions and computational resources......Page 352
Asset allocation in practice......Page 354
Stochastic local search......Page 356
12.7.2 Efficient implementations......Page 357
12.7.3 Parameter settings......Page 360
12.8 Summary......Page 361
12.A Implementing heuristic methods with Matlab......Page 362
12.A.1 Threshold Accepting......Page 365
12.A.2 Genetic Algorithm......Page 369
12.A.3 Differential Evolution......Page 373
12.A.4 Particle Swarm Optimization......Page 375
13.1 The investment problem......Page 378
13.2.1 The model......Page 380
13.2.2 Solving the model......Page 382
Minimum-variance portfolios......Page 383
Mean–variance efficient portfolios......Page 386
The tangency portfolio......Page 387
Computing the whole frontier......Page 388
13.2.4 True, estimated, and realized frontiers......Page 390
A helpful identity......Page 393
Indefinite matrices......Page 394
13.3.1 Asset selection with local search......Page 400
13.3.2 Scenario optimization with Threshold Accepting......Page 406
Ingredient 1: handling scenarios......Page 407
Ingredient 2: building blocks for selection criteria......Page 408
Ingredient 3: Threshold Accepting......Page 414
Minimizing squared returns......Page 418
Minimizing a risk–reward ratio......Page 427
13.3.4 Diagnostics......Page 434
13.A.1 Scoping rules in R and objective functions......Page 437
13.A.2 Vectorized objective functions......Page 438
Bond prices and yields......Page 442
Constructing yield curves......Page 444
14.1.2 The Nelson–Siegel model......Page 448
Collinearity......Page 451
Case 1: Linear regression with bootstrapped zero rates......Page 453
Case 2: Fitting bootstrapped zero rates with Differential Evolution......Page 455
Case 3: Fitting prices with Differential Evolution......Page 464
Case 4: Fitting yields-to-maturity with Differential Evolution......Page 468
The objective function......Page 471
Constraints......Page 474
14.2 Robust and resistant regression......Page 477
14.2.1 The regression model......Page 481
Implementing Particle Swarm Optimization......Page 483
14.2.3 An example......Page 488
14.2.4 Numerical experiments......Page 491
Results......Page 492
14.2.5 Final remarks......Page 497
14.A Maximizing the Sharpe ratio......Page 499
15 Calibrating option pricing models......Page 501
15.1 Implied volatility with Black–Scholes......Page 502
The smile......Page 505
15.2.1 A pricing equation......Page 506
Merton's jump–diffusion model......Page 507
The Heston model......Page 510
The Bates model......Page 511
Pricing with Matlab's quad......Page 512
Merton......Page 513
Heston......Page 514
Bates......Page 517
A primer on numerical integration......Page 520
Interpolatory rules......Page 524
Finding the nodes for Gauss rules......Page 526
Speed......Page 532
Accuracy......Page 534
15.3.1 Techniques......Page 537
Constraints......Page 539
15.3.2 Organizing the problem and implementation......Page 540
Repairing solutions......Page 547
15.3.3 Two experiments......Page 548
Price errors......Page 549
Parameter errors......Page 550
Price errors......Page 551
15.4 Final remarks......Page 553
15.A Quadrature rules for infinity......Page 554
Bibliography......Page 558
B......Page 572
F......Page 573
L......Page 574
M......Page 575
P......Page 577
R......Page 578
Z......Page 579