Contents
1 Introduction 9
1.1 Optimization Problems . . . . . . . . . . . . . . . . . . . . . . 9
1.1.1 Linear and Nonlinear Programming . . . . . . . . . . 10
1.1.2 Quadratic Programming . . . . . . . . . . . . . . . . . 11
1.1.3 Conic Optimization . . . . . . . . . . . . . . . . . . . 12
1.1.4 Integer Programming . . . . . . . . . . . . . . . . . . 12
1.1.5 Dynamic Programming . . . . . . . . . . . . . . . . . 13
1.2 Optimization with Data Uncertainty . . . . . . . . . . . . . . 13
1.2.1 Stochastic Programming . . . . . . . . . . . . . . . . . 13
1.2.2 Robust Optimization . . . . . . . . . . . . . . . . . . . 14
1.3 Financial Mathematics . . . . . . . . . . . . . . . . . . . . . . 16
1.3.1 Portfolio Selection and Asset Allocation . . . . . . . . 16
1.3.2 Pricing and Hedging of Options . . . . . . . . . . . . . 18
1.3.3 Risk Management . . . . . . . . . . . . . . . . . . . . 19
1.3.4 Asset/Liability Management . . . . . . . . . . . . . . 20
2 Linear Programming: Theory and Algorithms 23
2.1 The Linear Programming Problem . . . . . . . . . . . . . . . 23
2.2 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . 28
2.4 The Simplex Method . . . . . . . . . . . . . . . . . . . . . . . 31
2.4.1 Basic Solutions . . . . . . . . . . . . . . . . . . . . . . 32
2.4.2 Simplex Iterations . . . . . . . . . . . . . . . . . . . . 35
2.4.3 The Tableau Form of the Simplex Method . . . . . . . 39
2.4.4 Graphical Interpretation . . . . . . . . . . . . . . . . . 42
2.4.5 The Dual Simplex Method . . . . . . . . . . . . . . . 43
2.4.6 Alternatives to the Simplex Method . . . . . . . . . . 45
3 LP Models: Asset/Liability Cash Flow Matching 47
3.1 Short Term Financing . . . . . . . . . . . . . . . . . . . . . . 47
3.1.1 Modeling . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.1.2 Solving the Model with SOLVER . . . . . . . . . . . . 50
3.1.3 Interpreting the output of SOLVER . . . . . . . . . . 53
3.1.4 Modeling Languages . . . . . . . . . . . . . . . . . . . 54
3.1.5 Features of Linear Programs . . . . . . . . . . . . . . 55
3.2 Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.3 Sensitivity Analysis for Linear Programming . . . . . . . . . 58
3
4 CONTENTS
3.3.1 Short Term Financing . . . . . . . . . . . . . . . . . . 58
3.3.2 Dedication . . . . . . . . . . . . . . . . . . . . . . . . 63
3.4 Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4 LP Models: Asset Pricing and Arbitrage 69
4.1 The Fundamental Theorem of Asset Pricing . . . . . . . . . . 69
4.1.1 Replication . . . . . . . . . . . . . . . . . . . . . . . . 71
4.1.2 Risk-Neutral Probabilities . . . . . . . . . . . . . . . . 72
4.1.3 The Fundamental Theorem of Asset Pricing . . . . . . 74
4.2 Arbitrage Detection Using Linear Programming . . . . . . . . 75
4.3 Additional Exercises . . . . . . . . . . . . . . . . . . . . . . . 78
4.4 Case Study: Tax Clientele Eects in Bond Portfolio Management
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5 Nonlinear Programming: Theory and Algorithms 85
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.3 Univariate Optimization . . . . . . . . . . . . . . . . . . . . . 88
5.3.1 Binary search . . . . . . . . . . . . . . . . . . . . . . . 88
5.3.2 Newton's Method . . . . . . . . . . . . . . . . . . . . . 92
5.3.3 Approximate Line Search . . . . . . . . . . . . . . . . 95
5.4 Unconstrained Optimization . . . . . . . . . . . . . . . . . . . 97
5.4.1 Steepest Descent . . . . . . . . . . . . . . . . . . . . . 97
5.4.2 Newton's Method . . . . . . . . . . . . . . . . . . . . . 101
5.5 Constrained Optimization . . . . . . . . . . . . . . . . . . . . 104
5.5.1 The generalized reduced gradient method . . . . . . . 107
5.5.2 Sequential Quadratic Programming . . . . . . . . . . . 112
5.6 Nonsmooth Optimization: Subgradient Methods . . . . . . . 113
6 NLP Models: Volatility Estimation 115
6.1 Volatility Estimation with GARCH Models . . . . . . . . . . 115
6.2 Estimating a Volatility Surface . . . . . . . . . . . . . . . . . 119
7 Quadratic Programming: Theory and Algorithms 125
7.1 The Quadratic Programming Problem . . . . . . . . . . . . . 125
7.2 Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . 126
7.3 Interior-Point Methods . . . . . . . . . . . . . . . . . . . . . . 128
7.4 The Central Path . . . . . . . . . . . . . . . . . . . . . . . . . 131
7.5 Interior-Point Methods . . . . . . . . . . . . . . . . . . . . . . 132
7.5.1 Path-Following Algorithms . . . . . . . . . . . . . . . 132
7.5.2 Centered Newton directions . . . . . . . . . . . . . . . 133
7.5.3 Neighborhoods of the Central Path . . . . . . . . . . . 135
7.5.4 A Long-Step Path-Following Algorithm . . . . . . . . 138
7.5.5 Starting from an Infeasible Point . . . . . . . . . . . . 138
7.6 QP software . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
7.7 Additional Exercises . . . . . . . . . . . . . . . . . . . . . . . 139
CONTENTS 5
8 QP Models: Portfolio Optimization 141
8.1 Mean-Variance Optimization . . . . . . . . . . . . . . . . . . 141
8.1.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . 143
8.1.2 Large-Scale Portfolio Optimization . . . . . . . . . . . 148
8.1.3 The Black-Litterman Model . . . . . . . . . . . . . . . 151
8.1.4 Mean-Absolute Deviation to Estimate Risk . . . . . . 155
8.2 Maximizing the Sharpe Ratio . . . . . . . . . . . . . . . . . . 158
8.3 Returns-Based Style Analysis . . . . . . . . . . . . . . . . . . 160
8.4 Recovering Risk-Neural Probabilities from Options Prices . . 162
8.5 Additional Exercises . . . . . . . . . . . . . . . . . . . . . . . 166
8.6 Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
9 Conic Optimization Tools 171
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
9.2 Second-order cone programming: . . . . . . . . . . . . . . . . 171
9.2.1 Ellipsoidal Uncertainty for Linear Constraints . . . . . 173
9.2.2 Conversion of quadratic constraints into second-order
cone constraints . . . . . . . . . . . . . . . . . . . . . 175
9.3 Semidenite programming: . . . . . . . . . . . . . . . . . . . 176
9.3.1 Ellipsoidal Uncertainty for Quadratic Constraints . . . 178
9.4 Algorithms and Software . . . . . . . . . . . . . . . . . . . . . 179
10 Conic Optimization Models in Finance 181
10.1 Tracking Error and Volatility Constraints . . . . . . . . . . . 181
10.2 Approximating Covariance Matrices . . . . . . . . . . . . . . 184
10.3 Recovering Risk-Neural Probabilities from Options Prices . . 187
10.4 Arbitrage Bounds for Forward Start Options . . . . . . . . . 189
10.4.1 A Semi-Static Hedge . . . . . . . . . . . . . . . . . . . 190
11 Integer Programming: Theory and Algorithms 195
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
11.2 Modeling Logical Conditions . . . . . . . . . . . . . . . . . . 196
11.3 Solving Mixed Integer Linear Programs . . . . . . . . . . . . 199
11.3.1 Linear Programming Relaxation . . . . . . . . . . . . 199
11.3.2 Branch and Bound . . . . . . . . . . . . . . . . . . . . 200
11.3.3 Cutting Planes . . . . . . . . . . . . . . . . . . . . . . 208
11.3.4 Branch and Cut . . . . . . . . . . . . . . . . . . . . . 212
12 IP Models: Constructing an Index Fund 215
12.1 Combinatorial Auctions . . . . . . . . . . . . . . . . . . . . . 215
12.2 The Lockbox Problem . . . . . . . . . . . . . . . . . . . . . . 216
12.3 Constructing an Index Fund . . . . . . . . . . . . . . . . . . . 219
12.3.1 A Large-Scale Deterministic Model . . . . . . . . . . . 220
12.3.2 A Linear Programming Model . . . . . . . . . . . . . 223
12.4 Portfolio Optimization with Minimum Transaction Levels . . 224
12.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
12.6 Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
6 CONTENTS
13 Dynamic Programming Methods 227
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
13.1.1 Backward Recursion . . . . . . . . . . . . . . . . . . . 230
13.1.2 Forward Recursion . . . . . . . . . . . . . . . . . . . . 233
13.2 Abstraction of the Dynamic Programming Approach . . . . . 234
13.3 The Knapsack Problem. . . . . . . . . . . . . . . . . . . . . . 237
13.3.1 Dynamic Programming Formulation . . . . . . . . . . 237
13.3.2 An Alternative Formulation . . . . . . . . . . . . . . . 238
13.4 Stochastic Dynamic Programming . . . . . . . . . . . . . . . 239
14 DP Models: Option Pricing 241
14.1 A Model for American Options . . . . . . . . . . . . . . . . . 241
14.2 Binomial Lattice . . . . . . . . . . . . . . . . . . . . . . . . . 243
14.2.1 Specifying the parameters . . . . . . . . . . . . . . . . 244
14.2.2 Option Pricing . . . . . . . . . . . . . . . . . . . . . . 245
15 DP Models: Structuring Asset Backed Securities 249
15.1 Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
15.2 Enumerating possible tranches . . . . . . . . . . . . . . . . . 253
15.3 A Dynamic Programming Approach . . . . . . . . . . . . . . 254
15.4 Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
16 Stochastic Programming: Theory and Algorithms 257
16.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
16.2 Two Stage Problems with Recourse . . . . . . . . . . . . . . . 258
16.3 Multi Stage Problems . . . . . . . . . . . . . . . . . . . . . . 260
16.4 Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . 262
16.5 Scenario Generation . . . . . . . . . . . . . . . . . . . . . . . 265
16.5.1 Autoregressive model . . . . . . . . . . . . . . . . . . 265
16.5.2 Constructing scenario trees . . . . . . . . . . . . . . . 267
17 SP Models: Value-at-Risk 273
17.1 Risk Measures . . . . . . . . . . . . . . . . . . . . . . . . . . 273
17.2 Minimizing CVaR . . . . . . . . . . . . . . . . . . . . . . . . 276
17.3 Example: Bond Portfolio Optimization . . . . . . . . . . . . . 278
18 SP Models: Asset/Liability Management 281
18.1 Asset/Liability Management . . . . . . . . . . . . . . . . . . . 281
18.1.1 Corporate Debt Management . . . . . . . . . . . . . . 284
18.2 Synthetic Options . . . . . . . . . . . . . . . . . . . . . . . . 287
18.3 Case Study: Option Pricing with Transaction Costs . . . . . 290
18.3.1 The Standard Problem . . . . . . . . . . . . . . . . . . 291
18.3.2 Transaction Costs . . . . . . . . . . . . . . . . . . . . 292
19 Robust Optimization: Theory and Tools 295
19.1 Introduction to Robust Optimization . . . . . . . . . . . . . . 295
19.2 Uncertainty Sets . . . . . . . . . . . . . . . . . . . . . . . . . 296
19.3 Dierent Flavors of Robustness . . . . . . . . . . . . . . . . . 298
CONTENTS 7
19.3.1 Constraint Robustness . . . . . . . . . . . . . . . . . . 298
19.3.2 Objective Robustness . . . . . . . . . . . . . . . . . . 299
19.3.3 Relative Robustness . . . . . . . . . . . . . . . . . . . 301
19.3.4 Adjustable Robust Optimization . . . . . . . . . . . . 303
19.4 Tools and Strategies for Robust Optimization . . . . . . . . . 304
19.4.1 Sampling . . . . . . . . . . . . . . . . . . . . . . . . . 305
19.4.2 Conic Optimization . . . . . . . . . . . . . . . . . . . 305
19.4.3 Saddle-Point Characterizations . . . . . . . . . . . . . 307
20 Robust Optimization Models in Finance 309
20.1 Robust Multi-Period Portfolio Selection . . . . . . . . . . . . 309
20.2 Robust Prot Opportunities in Risky Portfolios . . . . . . . . 313
20.3 Robust Portfolio Selection . . . . . . . . . . . . . . . . . . . . 315
20.4 Relative Robustness in Portfolio Selection . . . . . . . . . . . 317
20.5 Moment Bounds for Option Prices . . . . . . . . . . . . . . . 319
20.6 Additional Exercises . . . . . . . . . . . . . . . . . . . . . . . 320
A Convexity 323
B Cones 325
C A Probability Primer 327
D The Revised Simplex Method 331