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.

Google Online Preview   Download