Optimization Methods in Finance - ku

1 Optimization Methods in Finance Gerard Cornuejols tu Reha 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 sev- eral classes of Optimization problems (including linear , quadratic, integer, dynamic, stochastic, conic, and robust programming) encountered in finan- cial models. For each problem class, after introducing the relevant theory (optimality conditions, duality , etc.) and efficient solution Methods , we dis- cuss 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.

2 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 In- stitute of Technology, Japan, and the University of Coimbra, Portugal (Reha T ut . unc u). 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 s Vicente and Masakazu Kojima. Various drafts of this book were experimented with in class by Javier Pe na, Fran cois Margot, Miroslav Karamanov and Kathie Cameron, and we thank them for their comments. Contents 1 Introduction 9. Optimization Problems .. 9. linear and Nonlinear Programming .. 10. Quadratic Programming .. 11. Conic Optimization .

3 12. Integer Programming .. 12. Dynamic Programming .. 13. Optimization with Data Uncertainty .. 13. Stochastic Programming .. 13. Robust Optimization .. 14. Financial Mathematics .. 16. Portfolio Selection and Asset Allocation .. 16. Pricing and Hedging of Options .. 18. Risk Management .. 19. Asset/Liability Management .. 20. 2 linear Programming: Theory and Algorithms 23. The linear Programming Problem .. 23. duality .. 25. Optimality Conditions .. 28. The Simplex Method .. 31. Basic Solutions .. 32. Simplex Iterations .. 35. The Tableau Form of the Simplex Method .. 39. Graphical Interpretation .. 42. The Dual Simplex Method .. 43. Alternatives to the Simplex Method .. 45. 3 LP Models: Asset/Liability Cash Flow Matching 47. Short Term Financing .. 47. Modeling .. 48. Solving the Model with SOLVER .. 50. Interpreting the output of SOLVER .. 53. Modeling Languages .. 54. Features of linear Programs .. 55. Dedication .. 56. Sensitivity Analysis for linear Programming.

4 58. 3. 4 CONTENTS. Short Term Financing .. 58. Dedication .. 63. Case Study .. 66. 4 LP Models: Asset Pricing and Arbitrage 69. The Fundamental Theorem of Asset Pricing .. 69. Replication .. 71. Risk-Neutral Probabilities .. 72. The Fundamental Theorem of Asset Pricing .. 74. Arbitrage Detection Using linear Programming .. 75. Additional Exercises .. 78. Case Study: Tax Clientele Effects in Bond Portfolio Manage- ment .. 82. 5 Nonlinear Programming: Theory and Algorithms 85. Introduction .. 85. Software .. 87. Univariate Optimization .. 88. Binary search .. 88. Newton's Method .. 92. Approximate Line Search .. 95. Unconstrained Optimization .. 97. Steepest Descent .. 97. Newton's Method .. 101. Constrained Optimization .. 104. The generalized reduced gradient method .. 107. Sequential Quadratic Programming .. 112. Nonsmooth Optimization : Subgradient Methods .. 113. 6 NLP Models: Volatility Estimation 115. Volatility Estimation with GARCH Models.

5 115. Estimating a Volatility Surface .. 119. 7 Quadratic Programming: Theory and Algorithms 125. The Quadratic Programming Problem .. 125. Optimality Conditions .. 126. Interior-Point Methods .. 128. The Central Path .. 131. Interior-Point Methods .. 132. Path-Following Algorithms .. 132. Centered Newton directions .. 133. Neighborhoods of the Central Path .. 135. A Long-Step Path-Following Algorithm .. 138. Starting from an Infeasible Point .. 138. QP software .. 139. Additional Exercises .. 139. CONTENTS 5. 8 QP Models: Portfolio Optimization 141. Mean-Variance Optimization .. 141. Example .. 143. Large-Scale Portfolio Optimization .. 148. The Black-Litterman Model .. 151. Mean-Absolute Deviation to Estimate Risk .. 155. Maximizing the Sharpe Ratio .. 158. Returns-Based Style Analysis .. 160. Recovering Risk-Neural Probabilities from Options Prices .. 162. Additional Exercises .. 166. Case Study .. 168. 9 Conic Optimization Tools 171.

6 Introduction .. 171. Second-order cone programming: .. 171. Ellipsoidal Uncertainty for linear Constraints .. 173. Conversion of quadratic constraints into second-order cone constraints .. 175. Semidefinite programming: .. 176. Ellipsoidal Uncertainty for Quadratic Constraints .. 178. Algorithms and Software .. 179. 10 Conic Optimization Models in Finance 181. Tracking Error and Volatility Constraints .. 181. Approximating Covariance Matrices .. 184. Recovering Risk-Neural Probabilities from Options Prices .. 187. Arbitrage Bounds for Forward Start Options .. 189. A Semi-Static Hedge .. 190. 11 Integer Programming: Theory and Algorithms 195. Introduction .. 195. Modeling Logical Conditions .. 196. Solving Mixed Integer linear Programs .. 199. linear Programming Relaxation .. 199. Branch and Bound .. 200. Cutting Planes .. 208. Branch and Cut .. 212. 12 IP Models: Constructing an Index Fund 215. Combinatorial Auctions .. 215. The Lockbox Problem.

7 216. Constructing an Index Fund .. 219. A Large-Scale Deterministic Model .. 220. A linear Programming Model .. 223. Portfolio Optimization with Minimum Transaction Levels .. 224. Exercises .. 225. Case Study .. 226. 6 CONTENTS. 13 Dynamic Programming Methods 227. Introduction .. 227. Backward Recursion .. 230. Forward Recursion .. 233. Abstraction of the Dynamic Programming Approach .. 234. The Knapsack Problem.. 237. Dynamic Programming Formulation .. 237. An Alternative Formulation .. 238. Stochastic Dynamic Programming .. 239. 14 DP Models: Option Pricing 241. A Model for American Options .. 241. Binomial Lattice .. 243. Specifying the parameters .. 244. Option Pricing .. 245. 15 DP Models: Structuring Asset Backed Securities 249. Data .. 251. Enumerating possible tranches .. 253. A Dynamic Programming Approach .. 254. Case Study .. 255. 16 Stochastic Programming: Theory and Algorithms 257. Introduction .. 257. Two Stage Problems with Recourse.

8 258. Multi Stage Problems .. 260. Decomposition .. 262. Scenario Generation .. 265. Autoregressive model .. 265. Constructing scenario trees .. 267. 17 SP Models: Value-at-Risk 273. Risk Measures .. 273. Minimizing CVaR .. 276. Example: Bond Portfolio Optimization .. 278. 18 SP Models: Asset/Liability Management 281. Asset/Liability Management .. 281. Corporate Debt Management .. 284. Synthetic Options .. 287. Case Study: Option Pricing with Transaction Costs .. 290. The Standard Problem .. 291. Transaction Costs .. 292. 19 Robust Optimization : Theory and Tools 295. Introduction to Robust Optimization .. 295. Uncertainty Sets .. 296. Different Flavors of Robustness .. 298. CONTENTS 7. Constraint Robustness .. 298. Objective Robustness .. 299. Relative Robustness .. 301. Adjustable Robust Optimization .. 303. Tools and Strategies for Robust Optimization .. 304. Sampling .. 305. Conic Optimization .. 305. Saddle-Point Characterizations.

9 307. 20 Robust Optimization Models in Finance 309. Robust Multi-Period Portfolio Selection .. 309. Robust Profit Opportunities in Risky Portfolios .. 313. Robust Portfolio Selection .. 315. Relative Robustness in Portfolio Selection .. 317. Moment Bounds for Option Prices .. 319. Additional Exercises .. 320. A Convexity 323. B Cones 325. C A Probability Primer 327. D The Revised Simplex Method 331. 8 CONTENTS. Chapter 1. Introduction Optimization is a branch of applied mathematics that derives its importance both from the wide variety of its applications and from the availability of efficient algorithms. Mathematically, it refers to the minimization (or max- imization) of a given objective function of several decision variables that satisfy functional constraints. A typical Optimization model addresses the allocation of scarce resources among possible alternative uses in order to maximize an objective function such as total profit.

10 Decision variables, the objective function, and constraints are three es- sential elements of any Optimization problem. Problems that lack constraints are called unconstrained Optimization problems, while others are often re- ferred to as constrained Optimization problems. Problems with no objective functions are called feasibility problems. Some problems may have multiple objective functions. These problems are often addressed by reducing them to a single-objective Optimization problem or a sequence of such problems. If the decision variables in an Optimization problem are restricted to integers, or to a discrete set of possibilities, we have an integer or discrete Optimization problem. If there are no such restrictions on the variables, the problem is a continuous Optimization problem. Of course, some problems may have a mixture of discrete and continuous variables. We continue with a list of problem classes that we will encounter in this book.