### Transcription of Optimization Methods in Finance

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.

3 10. Quadratic Programming .. 11. Conic **Optimization** .. 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.

4 53. Modeling Languages .. 54. Features of Linear Programs .. 55. Dedication .. 56. Sensitivity Analysis for Linear Programming .. 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.

5 107. Sequential Quadratic Programming .. 112. Nonsmooth **Optimization** : Subgradient **Methods** .. 113. 6 NLP Models: Volatility Estimation 115. Volatility Estimation with GARCH Models .. 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.

6 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. 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.

7 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 .. 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.

8 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 .. 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.

9 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 .. 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.

10 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. 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.