Optimization Methods in Finance - ku
Optimization Methods in Finance
Gerard Cornuejols Reha Tu?tu?ncu?
Carnegie Mellon University, Pittsburgh, PA 15213 USA
January 2006
2
Foreword Optimization models play an increasingly important role in financial de-
cisions. Many computational finance problems ranging from asset allocation to risk management, from option pricing to model calibration can be solved efficiently using modern optimization techniques. This course discusses several classes of optimization problems (including linear, quadratic, integer, dynamic, stochastic, conic, and robust programming) encountered in financial models. For each problem class, after introducing the relevant theory (optimality conditions, duality, etc.) and efficient solution methods, we discuss several problems of mathematical finance that can be modeled within this problem class. In addition to classical and well-known models such as Markowitz' mean-variance optimization model we present some newer optimization models for a variety of financial problems.
Acknowledgements This book has its origins in courses taught at Carnegie Mellon University
in the Masters program in Computational Finance and in the MBA program at the Tepper School of Business (G?erard Cornu?ejols), and at the Tokyo Institute of Technology, Japan, and the University of Coimbra, Portugal (Reha Tu?tu?ncu?). We thank the attendants of these courses for their feedback and for many stimulating discussions. We would also like to thank the colleagues who provided the initial impetus for this project, especially Michael Trick, John Hooker, Sanjay Srivastava, Rick Green, Yanjun Li, Lu?is Vicente and Masakazu Kojima. Various drafts of this book were experimented with in class by Javier Pen~a, Franc?ois Margot, Miroslav Karamanov and Kathie Cameron, and we thank them for their comments.
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 Effects in Bond Portfolio Manage-
ment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Semidefinite 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
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- data analysis methods in research
- learning methods in education
- methods in teaching
- promotional methods in marketing
- teaching methods in education
- statistical methods in nursing research
- methods in cell biology journal
- data collection methods in research
- array methods in java
- approaches and methods in language
- methods in string class java
- statistical methods in medical research