constrained optimization

14 results back to index

pages: 320 words: 24,110

Elements of Mathematics for Economics and Finance by Vassilis C. Mavron, Timothy N. Phillips


constrained optimization, discrete time, the market place

Strictly, we should say a local (or relative) maximum or minimum: for they may not give the overall maximum or minimum of a function. Within the locality of a maximum point x = x0 , y = y0 (that is, for any x and y sufficiently close to these values), the value f (x, y) of f attains a maximum when x = x0 and y = y0 . Similarly for a minimum point. 9. Optimization 193 3. The problem stated in Example 9.5 above was initially a constrained optimization problem in three variables. But, upon substitution for z, it became an unconstrained optimization problem in the remaining two variables, x and y. 9.3 Constrained Optimization Optimization of a quantity in economic models, or indeed in many practical situations, is rarely unconstrained. Usually there are constraints involving some or all of the variables. For instance, in considering ways to maximize, say, output, there will be constraints due to costs or of the available labour.

Partial Differentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 8.2 Functions of Two or More Variables . . . . . . . . . . . . . . . . . . . . . . . . 160 8.3 Partial Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 8.4 Higher Order Partial Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 8.5 Partial Rate of Change . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 8.6 The Chain Rule and Total Derivatives . . . . . . . . . . . . . . . . . . . . . . 168 8.7 Some Applications of Partial Derivatives . . . . . . . . . . . . . . . . . . . . 171 8.7.1 Implicit Differentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 8.7.2 Elasticity of Demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 8.7.3 Utility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 8.7.4 Production . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 8.7.5 Graphical Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 9. Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 9.2 Unconstrained Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 9.3 Constrained Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 9.3.1 Substitution Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 9.3.2 Lagrange Multipliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 9.3.3 The Lagrange Multiplier λ: An Interpretation . . . . . . . . . . 201 9.4 Iso Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 10.

A government may try to minimize interest rates while trying to keep inflation at a certain level. A pilot may fly an aircraft so as to cover the maximum possible air miles when the total fuel cost is stipulated. Consumers try to maximize utility subject to a given budget. In this chapter, we will describe techniques of optimization when there are no constraints specified (unconstrained optimization) and subject to a constraint (constrained optimization). 185 186 Elements of Mathematics for Economics and Finance 9.2 Unconstrained Optimization The optimization of functions of one variable was discussed in Chapter 7. Optimization there meant finding the stationary (or critical or turning) points of the function and then testing to see whether they were maxima or minima. Maxima (or minima) are points where the function changes from being increasing to decreasing (or vice versa).


A Primer for the Mathematics of Financial Engineering by Dan Stefanica


asset allocation, Black-Scholes formula, capital asset pricing model, constrained optimization, delta neutral, discrete time, Emanuel Derman, implied volatility, law of one price, margin call, quantitative trading / quantitative finance, Sharpe ratio, short selling, time value of money, transaction costs, volatility smile, yield curve, zero-coupon bond

One method to solve such problems is by using Lagrange multipliers, as outlined below. Let U c ~n be an open set, and let j : U -----7 ~ be a smooth function, e.g., infinitely many times differentiable. We want to find the extrema of j (x) subject to m constrains given by g(x) = 0, where 9 : U -----7 ~m is a smooth function, i.e., Find Xo E U such that max g(x) = 0 xEU j(x) = j(xo) or min g(x) = 0 xEU j(x) j(xo). (8.1) Problem (8.1) is called a constrained optimization problem. For this problem to be well posed, a natural assumption is that the number of constraints is smaller than the number of degrees of freedom, i.e., m < n. Another way to formalize problem (8.1) is to introduce the set S of points satisfying the constraint g( x) = 0, and find extrema for the restriction of the function j (x) to the space S, i.e., for j Is. 235 236 CHAPTER 8. LAGRANGE MULTIPLIERS.

LAGRANGE MULTIPLIERS. NEWTON'S METHOD. 8.1. LAGRANGE MULTIPLIERS Definition 8.1. The point Xo E U c IRn is called a constrained extremum of the function f : U -----+ IR with respect to the constraint g( x) = 0 if and only if Xo is an extremum point of fls, where S = {x E U such that g(x) = o}. where Vf(x) and Vg(x), the gradients of f : U -----+ IR and 9 : U -----+ IRm are given by v f(x) To solve the constrained optimization problem (8.1), let A = (Ai)i=l:m be a vector of the same size, m, as the number of constraints; A is called a Lagrange multipliers vector. Let F : U x IRm -----+ IR given by F(x, A) = f(x) + be the Lagrangian function of f and g. If ::n (x, >.)) ; ~;~ (x) ~;~ (x) ... ~;~ (x) ) Vg(x) (8.2) At g(x) (:;, (x, >.) ... 237 Og2 (x) Og2 (x) '" OXl. OX2 . . .. .. .. ( ogm (x) ogm (x) OXl OX2 Og2 (x) OXn. .. ogm (x) OXn ; cf. (1.36) and (1.38), respectively.

The reason is that if a problem is known to have a unique constrained extremum, and if the Lagrangian has exactly one critical point, then that critical point must be the constrained extremum point. For this line of thinking to be sound we must know that the constrained extremum problem has a unique solution. In general, showing that a problem has a unique solution is not straightforward. The steps required to solve a constrained optimization problem using Lagrange multipliers can be summarized as follows: Step 1: Check that rank(\lg(x)) = m, for all xES. q( v) = (V2 - 2V3? + 2v~ + 3v~ - 2(V2 - 2V3)V2 + 4V2V3 = v~ + 4V2V3 + 7v~. Note that Vred = ( ~~ ). Step 2: Find (xo, Ao) E U X ffi.m such that \l(x,)..)F(xo, Ao) Step 3.1: Compute q(v) + 4V2V3 + 7v~. 0 (8.15) Whether the point Xo is a constrained extremum for f (x) will depend on the quadratic form qred being either positive definite2 , i.e., = v D2 Fo(xo) v, where Fo(x) = f(x) + Ab9(x).


pages: 320 words: 33,385

Market Risk Analysis, Quantitative Methods in Finance by Carol Alexander


asset allocation, backtesting, barriers to entry, Brownian motion, capital asset pricing model, constrained optimization, credit crunch, Credit Default Swap, discounted cash flows, discrete time, diversification, diversified portfolio,, implied volatility, interest rate swap, market friction, market microstructure, p-value, performance metric, quantitative trading / quantitative finance, random walk, risk tolerance, risk-adjusted returns, risk/return, Sharpe ratio, statistical arbitrage, statistical model, stochastic process, stochastic volatility, transaction costs, value at risk, volatility smile, Wiener process, yield curve

Then examining the Hessian matrix for positive definiteness, or evaluating the function at and around these points, will tell us whether a given stationary point is a local maximum, a local minimum or neither. Once we have found all possible local maxima and minima, the global maximum (if it exists) is the one of the local maxima where the function takes the highest value and the global minimum (if it exists) is the one of the local minima where the function takes the lowest value. More generally, a constrained optimization problem takes the form max fx such that x hx ≤ 0 (I.1.47) where hx ≤ 0 is a set of linear or non-linear equality or inequality constraints on x. Examples of constrained optimization in finance include the traditional portfolio allocation problem, i.e. how to allocate funds to different types of investments when the investor has constraints such as no short sales and/or at least 50% of his capital must be in UK bonds. To find a constrained optimum we must introduce new variables, which are called Lagrange multipliers and denoted = 1 k , where k is the number of constraints on the objective.

To Walter Ledermann Contents List of Figures xiii List of Tables xvi List of Examples xvii Foreword xix Preface to Volume I I.1 Basic Calculus for Finance I.1.1 Introduction I.1.2 Functions and Graphs, Equations and Roots I.1.2.1 Linear and Quadratic Functions I.1.2.2 Continuous and Differentiable Real-Valued Functions I.1.2.3 Inverse Functions I.1.2.4 The Exponential Function I.1.2.5 The Natural Logarithm I.1.3 Differentiation and Integration I.1.3.1 Definitions I.1.3.2 Rules for Differentiation I.1.3.3 Monotonic, Concave and Convex Functions I.1.3.4 Stationary Points and Optimization I.1.3.5 Integration I.1.4 Analysis of Financial Returns I.1.4.1 Discrete and Continuous Time Notation I.1.4.2 Portfolio Holdings and Portfolio Weights I.1.4.3 Profit and Loss I.1.4.4 Percentage and Log Returns I.1.4.5 Geometric Brownian Motion I.1.4.6 Discrete and Continuous Compounding in Discrete Time I.1.4.7 Period Log Returns in Discrete Time I.1.4.8 Return on a Linear Portfolio I.1.4.9 Sources of Returns I.1.5 Functions of Several Variables I.1.5.1 Partial Derivatives: Function of Two Variables I.1.5.2 Partial Derivatives: Function of Several Variables xxiii 1 1 3 4 5 6 7 9 10 10 11 13 14 15 16 16 17 19 19 21 22 23 25 25 26 27 27 viii Contents I.1.5.3 Stationary Points I.1.5.4 Optimization I.1.5.5 Total Derivatives I.1.6 Taylor Expansion I.1.6.1 Definition and Examples I.1.6.2 Risk Factors and their Sensitivities I.1.6.3 Some Financial Applications of Taylor Expansion I.1.6.4 Multivariate Taylor Expansion I.1.7 Summary and Conclusions I.2 Essential Linear Algebra for Finance I.2.1 Introduction I.2.2 Matrix Algebra and its Mathematical Applications I.2.2.1 Basic Terminology I.2.2.2 Laws of Matrix Algebra I.2.2.3 Singular Matrices I.2.2.4 Determinants I.2.2.5 Matrix Inversion I.2.2.6 Solution of Simultaneous Linear Equations I.2.2.7 Quadratic Forms I.2.2.8 Definite Matrices I.2.3 Eigenvectors and Eigenvalues I.2.3.1 Matrices as Linear Transformations I.2.3.2 Formal Definitions I.2.3.3 The Characteristic Equation I.2.3.4 Eigenvalues and Eigenvectors of a 2 × 2 Correlation Matrix I.2.3.5 Properties of Eigenvalues and Eigenvectors I.2.3.6 Using Excel to Find Eigenvalues and Eigenvectors I.2.3.7 Eigenvalue Test for Definiteness I.2.4 Applications to Linear Portfolios I.2.4.1 Covariance and Correlation Matrices I.2.4.2 Portfolio Risk and Return in Matrix Notation I.2.4.3 Positive Definiteness of Covariance and Correlation Matrices I.2.4.4 Eigenvalues and Eigenvectors of Covariance and Correlation Matrices I.2.5 Matrix Decomposition I.2.5.1 Spectral Decomposition of a Symmetric Matrix I.2.5.2 Similarity Transforms I.2.5.3 Cholesky Decomposition I.2.5.4 LU Decomposition I.2.6 Principal Component Analysis I.2.6.1 Definition of Principal Components I.2.6.2 Principal Component Representation I.2.6.3 Case Study: PCA of European Equity Indices I.2.7 Summary and Conclusions 28 29 31 31 32 33 33 34 35 37 37 38 38 39 40 41 43 44 45 46 48 48 50 51 52 52 53 54 55 55 56 58 59 61 61 62 62 63 64 65 66 67 70 Contents I.3 Probability and Statistics I.3.1 Introduction I.3.2 Basic Concepts I.3.2.1 Classical versus Bayesian Approaches I.3.2.2 Laws of Probability I.3.2.3 Density and Distribution Functions I.3.2.4 Samples and Histograms I.3.2.5 Expected Value and Sample Mean I.3.2.6 Variance I.3.2.7 Skewness and Kurtosis I.3.2.8 Quantiles, Quartiles and Percentiles I.3.3 Univariate Distributions I.3.3.1 Binomial Distribution I.3.3.2 Poisson and Exponential Distributions I.3.3.3 Uniform Distribution I.3.3.4 Normal Distribution I.3.3.5 Lognormal Distribution I.3.3.6 Normal Mixture Distributions I.3.3.7 Student t Distributions I.3.3.8 Sampling Distributions I.3.3.9 Generalized Extreme Value Distributions I.3.3.10 Generalized Pareto Distribution I.3.3.11 Stable Distributions I.3.3.12 Kernels I.3.4 Multivariate Distributions I.3.4.1 Bivariate Distributions I.3.4.2 Independent Random Variables I.3.4.3 Covariance I.3.4.4 Correlation I.3.4.5 Multivariate Continuous Distributions I.3.4.6 Multivariate Normal Distributions I.3.4.7 Bivariate Normal Mixture Distributions I.3.4.8 Multivariate Student t Distributions I.3.5 Introduction to Statistical Inference I.3.5.1 Quantiles, Critical Values and Confidence Intervals I.3.5.2 Central Limit Theorem I.3.5.3 Confidence Intervals Based on Student t Distribution I.3.5.4 Confidence Intervals for Variance I.3.5.5 Hypothesis Tests I.3.5.6 Tests on Means I.3.5.7 Tests on Variances I.3.5.8 Non-Parametric Tests on Distributions I.3.6 Maximum Likelihood Estimation I.3.6.1 The Likelihood Function I.3.6.2 Finding the Maximum Likelihood Estimates I.3.6.3 Standard Errors on Mean and Variance Estimates ix 71 71 72 72 73 75 76 78 79 81 83 85 85 87 89 90 93 94 97 100 101 103 105 106 107 108 109 110 111 114 115 116 117 118 118 120 122 123 124 125 126 127 130 130 131 133 x Contents I.3.7 Stochastic Processes in Discrete and Continuous Time I.3.7.1 Stationary and Integrated Processes in Discrete Time I.3.7.2 Mean Reverting Processes and Random Walks in Continuous Time I.3.7.3 Stochastic Models for Asset Prices and Returns I.3.7.4 Jumps and the Poisson Process I.3.8 Summary and Conclusions I.4 Introduction to Linear Regression I.4.1 Introduction I.4.2 Simple Linear Regression I.4.2.1 Simple Linear Model I.4.2.2 Ordinary Least Squares I.4.2.3 Properties of the Error Process I.4.2.4 ANOVA and Goodness of Fit I.4.2.5 Hypothesis Tests on Coefficients I.4.2.6 Reporting the Estimated Regression Model I.4.2.7 Excel Estimation of the Simple Linear Model I.4.3 Properties of OLS Estimators I.4.3.1 Estimates and Estimators I.4.3.2 Unbiasedness and Efficiency I.4.3.3 Gauss–Markov Theorem I.4.3.4 Consistency and Normality of OLS Estimators I.4.3.5 Testing for Normality I.4.4 Multivariate Linear Regression I.4.4.1 Simple Linear Model and OLS in Matrix Notation I.4.4.2 General Linear Model I.4.4.3 Case Study: A Multiple Regression I.4.4.4 Multiple Regression in Excel I.4.4.5 Hypothesis Testing in Multiple Regression I.4.4.6 Testing Multiple Restrictions I.4.4.7 Confidence Intervals I.4.4.8 Multicollinearity I.4.4.9 Case Study: Determinants of Credit Spreads I.4.4.10 Orthogonal Regression I.4.5 Autocorrelation and Heteroscedasticity I.4.5.1 Causes of Autocorrelation and Heteroscedasticity I.4.5.2 Consequences of Autocorrelation and Heteroscedasticity I.4.5.3 Testing for Autocorrelation I.4.5.4 Testing for Heteroscedasticity I.4.5.5 Generalized Least Squares I.4.6 Applications of Linear Regression in Finance I.4.6.1 Testing a Theory I.4.6.2 Analysing Empirical Market Behaviour I.4.6.3 Optimal Portfolio Allocation 134 134 136 137 139 140 143 143 144 144 146 148 149 151 152 153 155 155 156 157 157 158 158 159 161 162 163 163 166 167 170 171 173 175 175 176 176 177 178 179 179 180 181 Contents I.4.6.4 Regression-Based Hedge Ratios I.4.6.5 Trading on Regression Models I.4.7 Summary and Conclusions xi 181 182 184 I.5 Numerical Methods in Finance I.5.1 Introduction I.5.2 Iteration I.5.2.1 Method of Bisection I.5.2.2 Newton–Raphson Iteration I.5.2.3 Gradient Methods I.5.3 Interpolation and Extrapolation I.5.3.1 Linear and Bilinear Interpolation I.5.3.2 Polynomial Interpolation: Application to Currency Options I.5.3.3 Cubic Splines: Application to Yield Curves I.5.4 Optimization I.5.4.1 Least Squares Problems I.5.4.2 Likelihood Methods I.5.4.3 The EM Algorithm I.5.4.4 Case Study: Applying the EM Algorithm to Normal Mixture Densities I.5.5 Finite Difference Approximations I.5.5.1 First and Second Order Finite Differences I.5.5.2 Finite Difference Approximations for the Greeks I.5.5.3 Finite Difference Solutions to Partial Differential Equations I.5.6 Binomial Lattices I.5.6.1 Constructing the Lattice I.5.6.2 Arbitrage Free Pricing and Risk Neutral Valuation I.5.6.3 Pricing European Options I.5.6.4 Lognormal Asset Price Distributions I.5.6.5 Pricing American Options I.5.7 Monte Carlo Simulation I.5.7.1 Random Numbers I.5.7.2 Simulations from an Empirical or a Given Distribution I.5.7.3 Case Study: Generating Time Series of Lognormal Asset Prices I.5.7.4 Simulations on a System of Two Correlated Normal Returns I.5.7.5 Multivariate Normal and Student t Distributed Simulations I.5.8 Summary and Conclusions 185 185 187 187 188 191 193 193 195 197 200 201 202 203 I.6 Introduction to Portfolio Theory I.6.1 Introduction I.6.2 Utility Theory I.6.2.1 Properties of Utility Functions I.6.2.2 Risk Preference I.6.2.3 How to Determine the Risk Tolerance of an Investor I.6.2.4 Coefficients of Risk Aversion 225 225 226 226 229 230 231 203 206 206 207 208 210 211 211 212 213 215 217 217 217 218 220 220 223 xii Contents I.6.2.5 I.6.2.6 I.6.2.7 I.6.3 I.6.4 I.6.5 I.6.6 Some Standard Utility Functions Mean–Variance Criterion Extension of the Mean–Variance Criterion to Higher Moments Portfolio Allocation I.6.3.1 Portfolio Diversification I.6.3.2 Minimum Variance Portfolios I.6.3.3 The Markowitz Problem I.6.3.4 Minimum Variance Portfolios with Many Constraints I.6.3.5 Efficient Frontier I.6.3.6 Optimal Allocations Theory of Asset Pricing I.6.4.1 Capital Market Line I.6.4.2 Capital Asset Pricing Model I.6.4.3 Security Market Line I.6.4.4 Testing the CAPM I.6.4.5 Extensions to CAPM Risk Adjusted Performance Measures I.6.5.1 CAPM RAPMs I.6.5.2 Making Decisions Using the Sharpe Ratio I.6.5.3 Adjusting the Sharpe Ratio for Autocorrelation I.6.5.4 Adjusting the Sharpe Ratio for Higher Moments I.6.5.5 Generalized Sharpe Ratio I.6.5.6 Kappa Indices, Omega and Sortino Ratio Summary and Conclusions 232 234 235 237 238 240 244 245 246 247 250 250 252 253 254 255 256 257 258 259 260 262 263 266 References 269 Statistical Tables 273 Index 279 List of Figures A linear function The quadratic function fx = 4x2 + 3x + 2 I.1.3 The reciprocal function I.1.4 The inverse of a function I.1.5 The exponential function I.1.6 The natural logarithmic function I.1.7 Definition of the first derivative I.1.8 Two functions I.1.9 The definite integral I.1.10 The h-period log return is the sum of h consecutive one-period log returns I.1.11 Graph of the function in Example I.1.8 I.2.1 A matrix is a linear transformation I.2.2 A vector that is not an eigenvector I.2.3 An eigenvector I.2.4 Six European equity indices I.2.5 The first principal component I.3.1 Venn diagram I.3.2 Density and distribution functions: (a) discrete random variable; (b) continuous variable I.3.3 Building a histogram in Excel I.3.4 The effect of cell width on the histogram shape I.3.5 Two densities with the same expectation I.1.1 I.1.2 4 5 6 7 8 I.3.6 9 I.3.8 10 12 15 I.3.9 24 27 I.3.7 I.3.10 I.3.11 I.3.12 I.3.13 48 I.3.14 49 50 67 I.3.15 I.3.16 69 75 I.3.17 77 78 I.3.18 78 I.3.19 I.3.20 but different standard deviations (a) A normal density and a leptokurtic density; (b) a positively skewed density The 0.1 quantile of a continuous random variable Some binomial density functions A binomial tree for a stock price evolution The standard uniform distribution Two normal densities Lognormal density associated with the standard normal distribution A variance mixture of two normal densities A skewed, leptokurtic normal mixture density Comparison of Student t densities and standard normal Comparison of Student t density and normal with same variance Comparison of standardized empirical density with standardized Student t density and standard normal density The Excel t distribution function Filtering data to derive the GEV distribution A Fréchet density 80 83 84 86 87 89 90 93 95 97 98 99 99 100 102 103 xiv List of Figures I.3.21 Filtering data in the peaks-over-threshold model I.3.22 Kernel estimates of S&P 500 returns I.3.23 Scatter plots from a paired sample of returns: (a) correlation +075; (b) correlation 0; (c) correlation −075 I.3.24 Critical regions for hypothesis tests I.3.25 The dependence of the likelihood on parameters I.3.26 The likelihood and the log likelihood functions I.3.27 FTSE 100 index I.3.28 Daily prices and log prices of DJIA index I.3.29 Daily log returns on DJIA index I.4.1 Scatter plot of Amex and S&P 500 daily log returns I.4.2 Dialog box for Excel regression I.4.3 Unbiasedness and efficiency I.4.4 Distribution of a consistent estimator I.4.5 Billiton share price, Amex Oil index and CBOE Gold index I.4.6 Dialog box for multiple regression in Excel I.4.7 The iTraxx Europe index and its determinants I.4.8 Residuals from the Billiton regression I.5.1 Method of bisection I.5.2 Setting Excel’s Goal Seek I.5.3 Newton–Raphson iteration I.5.4 104 107 I.5.5 I.5.6 I.5.7 I.5.8 I.5.9 113 I.5.10 125 I.5.11 130 I.5.12 131 133 I.5.13 I.5.14 137 138 I.5.15 I.5.16 145 I.5.17 153 I.5.18 156 I.5.19 157 I.5.20 162 I.6.1 164 I.6.2 172 I.6.3 178 187 189 189 I.6.4 I.6.5 Convergence of Newton–Raphson scheme Solver options Extrapolation of a yield curve Linear interpolation on percentiles Fitting a currency smile A cubic spline interpolated yield curve FTSE 100 and S&P 500 index prices, 1996–2007 Sterling–US dollar exchange rate, 1996–2007 Slope of chord about a point Discretization of space for the finite difference scheme A simple finite difference scheme A binomial lattice Computing the price of European and American puts Simulating from a standard normal distribution Possible paths for an asset price following geometric Brownian motion A set of three independent standard normal simulations A set of three correlated normal simulations Convex, concave and linear utility functions The effect of correlation on portfolio volatility Portfolio volatility as a function of portfolio weight Portfolio risk and return as a function of portfolio weight Minimum variance portfolio 190 191 193 195 197 200 204 204 206 209 210 210 216 218 220 221 222 229 239 241 242 243 I.6.6 I.6.7 I.6.8 Solver settings for Example I.6.9 The opportunity set and the efficient frontier Indifference curves of risk averse investor List of Figures xv Indifference curves of risk loving investor I.6.10 Market portfolio I.6.11 Capital market line I.6.12 Security market line 249 251 251 253 I.6.9 246 247 248 List of Tables I.1.1 Asset prices I.1.2 Portfolio weights and portfolio value I.1.3 Portfolio returns I.2.1 Volatilities and correlations I.2.2 The correlation matrix of weekly returns I.2.3 Eigenvectors and eigenvalues of the correlation matrix I.3.1 Example of the density of a discrete random variable I.3.2 Distribution function for Table I.3.1 I.3.3 Biased and unbiased sample moments I.3.4 The B(3, 1/6) distribution I.3.5 A Poisson density function I.3.6 A simple bivariate density I.3.7 Distribution of the product I.3.8 Calculating a covariance I.3.9 Sample statistics I.4.1 Calculation of OLS estimates I.4.2 Estimating the residual sum of sqaures and the standard error of the regression I.4.3 Estimating the total sum of squares I.4.4 Critical values of t3 I.4.5 Some of the Excel output for the Amex and S&P 500 model 18 18 26 56 68 68 75 75 82 86 88 110 110 111 127 147 149 150 152 154 I.4.6 ANOVA for the Amex and S&P 500 model I.4.7 Coefficient estimates for the Amex and S&P 500 model I.4.8 ANOVA for Billiton regression I.4.9 Wald, LM and LR statistics I.5.1 Mean and volatility of the FTSE 100 and S&P 500 indices and the £/$ FX rate I.5.2 Estimated parameters of normal mixture distributions I.5.3 Analytic vs finite difference Greeks I.5.4 Characteristics of asset returns I.6.1 Two investments (outcomes as returns) I.6.2 Two investments (utility of outcomes) I.6.3 Returns characteristics for two portfolios I.6.4 Two investments I.6.5 Sharpe ratio and weak stochastic dominance I.6.6 Returns on an actively managed fund and its benchmark I.6.7 Statistics on excess returns I.6.8 Sharpe ratios and adjusted Sharpe ratios I.6.9 Kappa indices 154 154 164 167 205 205 208 221 227 228 237 258 259 261 262 262 264 List of Examples I.1.1 I.1.2 I.1.3 I.1.4 I.1.5 I.1.6 I.1.7 I.1.8 I.1.9 I.1.10 I.1.11 I.2.1 I.2.2 I.2.3 I.2.4 I.2.5 I.2.6 I.2.7 I.2.8 I.2.9 I.2.10 I.2.11 Roots of a quadratic equation Calculating derivatives Identifying stationary points A definite integral Portfolio weights Returns on a long-short portfolio Portfolio returns Stationary points of a function of two variables Constrained optimization Total derivative of a function of three variables Taylor approximation Finding a matrix product using Excel Calculating a 4 × 4 determinant Finding the determinant and the inverse matrix using Excel Solving a system of simultaneous linear equations in Excel A quadratic form in Excel Positive definiteness Determinant test for positive definiteness Finding eigenvalues and eigenvectors Finding eigenvectors Using an Excel add-in to find eigenvectors and eigenvalues Covariance and correlation matrices 5 12 14 16 18 20 25 28 30 31 32 40 42 43 45 45 46 47 51 53 54 56 I.2.12 Volatility of returns and volatility of P&L I.2.13 A non-positive definite 3 × 3 matrix I.2.14 Eigenvectors and eigenvalues of a 2 × 2 covariance matrix I.2.15 Spectral decomposition of a correlation matrix I.2.16 The Cholesky matrix of a 2 × 2 matrix I.2.17 The Cholesky matrix of a 3 × 3 matrix I.2.18 Finding the Cholesky matrix in Excel I.2.19 Finding the LU decomposition in Excel I.3.1 Building a histogram I.3.2 Calculating moments of a distribution I.3.3 Calculating moments of a sample I.3.4 Evolution of an asset price I.3.5 Normal probabilities I.3.6 Normal probabilities for portfolio returns I.3.7 Normal probabilities for active returns I.3.8 Variance and kurtosis of a zero-expectation normal mixture I.3.9 Probabilities of normal mixture variables I.3.10 Calculating a covariance I.3.11 Calculating a correlation I.3.12 Normal confidence intervals 57 59 60 61 62 63 63 64 77 81 82 87 90 91 92 95 96 110 112 119 xviii List of Examples I.3.13 One- and two-sided confidence intervals I.3.14 Confidence interval for a population mean I.3.15 Testing for equality of means and variances I.3.16 Log likelihood of the normal density I.3.17 Fitting a Student t distribution by maximum likelihood I.4.1 Using the OLS formula I.4.2 Relationship between beta and correlation I.4.3 Estimating the OLS standard error of the regression I.4.4 ANOVA I.4.5 Hypothesis tests in a simple linear model I.4.6 Simple regression in matrix form I.4.7 Goodness-of-fit test in multiple regression I.4.8 Testing a simple hypothesis in multiple regression I.4.9 Testing a linear restriction I.4.10 Confidence interval for regression coefficient I.4.11 Prediction in multivariate regression I.4.12 Durbin–Watson test I.4.13 White’s heteroscedasticity test I.5.1 Excel’s Goal Seek I.5.2 Using Solver to find a bond yield I.5.3 Interpolating implied volatility I.5.4 Bilinear interpolation I.5.5 120 I.5.6 123 I.5.7 127 131 I.5.8 I.5.9 132 147 147 148 150 151 160 I.5.10 I.6.1 I.6.2 I.6.3 I.6.4 I.6.5 I.6.6 164 165 165 168 I.6.7 I.6.8 I.6.9 169 177 I.6.10 I.6.11 177 188 I.6.12 191 I.6.13 I.6.14 194 194 I.6.15 Fitting a 25-delta currency option smile Interpolation with cubic splines Finite difference approximation to delta, gamma and vega Pricing European call and put options Pricing an American option with a binomial lattice Simulations from correlated Student t distributed variables Expected utility Certain equivalents Portfolio allocations for an exponential investor Higher moment criterion for an exponential investor Minimum variance portfolio: two assets Minimum variance portfolio on S&P 100 and FTSE 100 General formula for minimum variance portfolio The Markowitz problem Minimum variance portfolio with many constraints The CML equation Stochastic dominance and the Sharpe ratio Adjusting a Sharpe ratio for autocorrelation Adjusted Sharpe ratio Computing a generalized Sharpe ratio Omega, Sortino and kappa indices 196 198 208 212 215 222 227 228 235 236 241 242 244 245 246 252 258 260 261 263 264 Foreword How many children dream of one day becoming risk managers?

This result forms the basis of portfolio theory, and will be used extensively in Chapter I.6. Another application of differentiation is to the optimal allocation problem for an investor who faces certain constraints, such as no short sales and/or at least 30% of his funds must be invested in US equities. The investor’s problem is to choose his portfolio weights to optimize his objective whilst respecting his constraints. This falls into the class of constrained optimization problems, problems that are solved using differentiation. Risk is the uncertainty about an expected value, and a risk-averse investor wants to achieve the maximum possible return with the minimum possible risk. Standard measures of portfolio risk are the variance of a portfolio and its square root which is called the portfolio volatility.6 The portfolio variance is a quadratic function of the portfolio weights.


pages: 396 words: 117,149

The Master Algorithm: How the Quest for the Ultimate Learning Machine Will Remake Our World by Pedro Domingos


3D printing, Albert Einstein, Amazon Mechanical Turk, Arthur Eddington, Benoit Mandelbrot, bioinformatics, Black Swan, Brownian motion, cellular automata, Claude Shannon: information theory, combinatorial explosion, computer vision, constrained optimization, correlation does not imply causation, crowdsourcing, Danny Hillis, data is the new oil, double helix, Douglas Hofstadter, Erik Brynjolfsson, experimental subject, Filter Bubble, future of work, global village, Google Glasses, Gödel, Escher, Bach, information retrieval, job automation, John Snow's cholera map, John von Neumann, Joseph Schumpeter, Kevin Kelly, lone genius, mandelbrot fractal, Mark Zuckerberg, Moneyball by Michael Lewis explains big data, Narrative Science, Nate Silver, natural language processing, Netflix Prize, Network effects, NP-complete, P = NP, PageRank, pattern recognition, phenotype, planetary scale, pre–internet, random walk, Ray Kurzweil, recommendation engine, Richard Feynman, Richard Feynman, Second Machine Age, self-driving car, Silicon Valley, speech recognition, statistical model, Stephen Hawking, Steven Levy, Steven Pinker, superintelligent machines, the scientific method, The Signal and the Noise by Nate Silver, theory of mind, transaction costs, Turing machine, Turing test, Vernor Vinge, Watson beat the top human players on Jeopardy!, white flight

Or, equivalently, we can minimize the weights under the constraint that all examples have a given margin, which could be one—the precise value is arbitrary. This is what SVMs usually do. Constrained optimization is the problem of maximizing or minimizing a function subject to constraints. The universe maximizes entropy subject to keeping energy constant. Problems of this type are widespread in business and technology. For example, we may want to maximize the number of widgets a factory produces, subject to the number of machine tools available, the widgets’ specs, and so on. With SVMs, constrained optimization became crucial for machine learning as well. Unconstrained optimization is getting to the top of the mountain, and that’s what gradient descent (or, in this case, ascent) does. Constrained optimization is going as high as you can while staying on the road. If the road goes up to the very top, the constrained and unconstrained problems have the same solution.

You know you’ve reached the highest point on the road when you can’t go any higher without driving off the road; in other words, when the path to the top is at right angles to the road. If the road and the path to the top form an oblique angle, you can always get higher by driving farther along the road, even if that doesn’t get you higher as quickly as aiming straight for the top of the mountain. So the way to solve a constrained optimization problem is to follow not the gradient but the part of it that’s parallel to the constraint surface—in this case the road—and stop when that part is zero. In general, we have to deal with many constraints at once (one per example, in the case of SVMs). Suppose you wanted to get as close as possible to the North Pole but couldn’t leave your room. Each of the room’s four walls is a constraint, and the solution is to follow the compass until you bump into the corner where the northeast and northwest walls meet.

The connectionists’ is gradient descent. The evolutionaries’ is genetic search, including crossover and mutation. The Bayesians are unusual in this regard: they don’t just look for the best model, but average over all models, weighted by how probable they are. To do the weighting efficiently, they use probabilistic inference algorithms like MCMC. The analogizers (or more precisely, the SVM mavens) use constrained optimization to find the best model. After a long day’s journey, the sun is rapidly nearing the horizon, and you need to hurry before it gets dark. The city’s outer wall has five massive gates, each controlled by one of the tribes and leading to its district in Optimization Town. Let us enter through the Gradient Descent Gate, after whispering the watchword—“deep learning”—to the guard, and spiral in toward the Towers of Representation.


pages: 130 words: 11,880

Optimization Methods in Finance by Gerard Cornuejols, Reha Tutuncu


asset allocation, call centre, constrained optimization, correlation coefficient, diversification, finite state, fixed income, frictionless, frictionless market, index fund, linear programming, Long Term Capital Management, passive investing, Sharpe ratio, transaction costs, value at risk, Y2K

A typical optimization model addresses the allocation of scarce resources among a set of alternative activities in order to maximize an objective function–a measure of the modeler’s satisfaction with the solution, for example, the total profit. Decision variables, the objective function, and constraints are three essential elements of any optimization problem. Some problems may lack constraints so that any set of decision variables (of appropriate dimension) are acceptable as alternative solutions. Such problems are called unconstrained optimization problems, while others are often referred to as constrained optimization problems. There are problem instances with no objective functions–the so-called feasibility problems, and others with multiple objective functions. Such problems are often addressed by reduction to a single or a sequence of single-objective optimization 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.

(5.6) Thus, we proved the following result: Proposition 5.1 Given a set X of feasible portfolios with the property that eT x = 1, ∀x ∈ X , the portfolio x∗ with the maximum Sharpe ratio in this set can be found by solving the following problem with a convex quadratic objective function min xT Qx s.t. (x, κ) ∈ X + , (µ − rf e)T x = 1, (5.7) with X + as in (5.4). If (x̂, κ̂) is the solution to (5.7), then x∗ = κ̂x̂ . This last problem can be solved using the techniques we discussed for convex quadratic programming problems. 5.3. RETURNS-BASED STYLE ANALYSIS 5.3 63 Returns-Based Style Analysis In two ground-breaking articles, Sharpe described how constrained optimization techniques can be used to determine the effective asset mix of a fund using only the return time series for the fund and a number of carefully chosen asset classes [13, 14]. Often, passive indices or index funds are used to represent the chosen asset classes and one tries to determine a portfolio of these funds/indices whose returns provide the best match for the returns of the fund being analyzed.


pages: 252 words: 73,131

The Inner Lives of Markets: How People Shape Them—And They Shape Us by Tim Sullivan


Airbnb, airport security, Al Roth, Andrei Shleifer, attribution theory, autonomous vehicles, barriers to entry, Brownian motion, centralized clearinghouse, clean water, conceptual framework, constrained optimization, continuous double auction, deferred acceptance, Donald Trump, Edward Glaeser, experimental subject, first-price auction, framing effect, frictionless, fundamental attribution error, George Akerlof, Goldman Sachs: Vampire Squid, helicopter parent, Internet of things, invisible hand, Isaac Newton, iterative process, Jean Tirole, Jeff Bezos, Johann Wolfgang von Goethe, John Nash: game theory, John von Neumann, Joseph Schumpeter, late fees, linear programming, Lyft, market clearing, market design, market friction, medical residency, multi-sided market, mutually assured destruction, Nash equilibrium, Occupy movement, Peter Thiel,, pez dispenser, pre–internet, price mechanism, price stability, prisoner's dilemma, profit motive, proxy bid, RAND corporation, ride hailing / ride sharing, Robert Shiller, Robert Shiller, Ronald Coase, school choice, school vouchers, sealed-bid auction, second-price auction, second-price sealed-bid, sharing economy, Silicon Valley, spectrum auction, Steve Jobs, Tacoma Narrows Bridge, technoutopianism, telemarketer, The Market for Lemons, The Wisdom of Crowds, Thomas Malthus, Thorstein Veblen, trade route, transaction costs, two-sided market, uranium enrichment, Vickrey auction, winner-take-all economy

Suppose you want to help people commute safely and efficiently across the East River, from Brooklyn to Manhattan. Traditional economics is the equivalent of assuming that the only two ways of doing so are bridge or ferry. Mechanism design imagines the broad set of possibilities—zip line, catapult, people mover—then figures out which will work best. It’s what, in technical terms, is called constrained optimization (the same technique Vickrey deployed to determine that the best way to get to work at Columbia was on roller skates). Mechanism designers consider the restrictions imposed by laws, human nature, our sense of right and wrong, and the strategizing that kidney patients, school applicants, and others may engage in to get a better organ or education. And they design a mechanism to best to fulfill society’s needs and wants within those constraints.

., 169–170, 172 Camp, Garrett, 170 candle auctions, 82 capitalism, free-market, 172–173 car service platform, 169–171 cash-back bonus, 116 cash-for-sludge transactions, 167–169 See also Summers, Larry centralized clearinghouses, 140–141 Champagne fairs, 105–106, 126–128 Changi POW camp, 175–177 Le Chatelier, Henry Louis, 29 Le Chatelier’s principle, 29 cheap talk, 62–66, 69 chess, difference between Cold War and, 26 See also poker, bluffing in child labor, 180 cigarettes, as currency in German POW camp, 8–9 Clarke, Edward, 93 Clavell, James, 175 clerkship offers, with federal judges, 140 coat hook, 151–152, 174 Codes of the Underworld (Gambetta), 68 Cold War, difference between chess and, 26 See also poker, bluffing in Collectible Supplies, 128–129 “College Admissions and the Stability of Marriage” (Gale and Shapley), 137 commitment, signs of, 62–63, 69–71, 72–75 community game, 178–179 competition models of, 35, 166, 172–173 platform, 124–126 unethical conduct with, 180–181 “Competition is for Losers” (Thiel), 173 competitive equilibrium, existence of, 29, 31–34, 36–37, 40, 45, 76 competitive markets, 35, 124–126, 172–174, 180–181 See also platforms competitive signaling, 70–71 congestion pricing model, 86, 94 constrained optimization, 85–86, 133, 120 copycat competitors, 172–173 corporate philanthropy, 72–75 Cowles, Alfred, 25, 27 Cowles Commission for Research in Economics, 25, 27, 31, 134 “creative destruction,” 50 credit card platforms, 113–116, 123–124 criminal organizations, informational challenges of, 68 currency, at Stalag VII-A POW camp, 8–9 customer feedback, 52, 74–75 Davis, Harry, 154, 157 Debreu, Gérard, 20, 24, 25, 32–33, 36–37 decentralized match, 139–140 deferred acceptance algorithm, 137–141, 145–149 Delmonico, Frank, 164 descending price auctions, 81–82 design, auction, 14, 101–102 Digital Dealing (Hall), 94 Discover card, 115–116 distribution of income, 22 Domar, Evsey, 36–37 Dorosin, Neil, 142–144 Douglas Aircraft Company, 25 Dow, Bob, 1–2 Dow, Edna, 1–2 Drèze, Jacques, 85–86 dumping toxic waste, transactions for, 167–169 Dutch auctions, 81–82 dysfunction, market, 36, 75–77, 143 eBay adverse selection on, 51–55, 57 auction listings, 94–97 concerns on model for, 43, 46, 48 on seller motivation for giving to charities, 73–75 start of, 39–41 as two-sided market, 109, 119 e-commerce, 41–43, 52–55 “The Economic Organization of a P.O.W.


pages: 500 words: 145,005

Misbehaving: The Making of Behavioral Economics by Richard H. Thaler


Albert Einstein, Amazon Mechanical Turk, Andrei Shleifer, Apple's 1984 Super Bowl advert, Atul Gawande, Berlin Wall, Bernie Madoff, Black-Scholes formula, capital asset pricing model, Cass Sunstein, Checklist Manifesto, choice architecture, clean water, cognitive dissonance, conceptual framework, constrained optimization, Daniel Kahneman / Amos Tversky, delayed gratification, diversification, diversified portfolio, Edward Glaeser, endowment effect, equity premium, Eugene Fama: efficient market hypothesis, experimental economics, Fall of the Berlin Wall, George Akerlof, hindsight bias, Home mortgage interest deduction, impulse control, index fund, invisible hand, Jean Tirole, John Nash: game theory, John von Neumann, late fees, law of one price, libertarian paternalism, Long Term Capital Management, loss aversion, market clearing, Mason jar, mental accounting, meta analysis, meta-analysis, More Guns, Less Crime, mortgage debt, Nash equilibrium, Nate Silver, New Journalism, nudge unit, payday loans, Ponzi scheme, presumed consent, pre–internet, principal–agent problem, prisoner's dilemma, profit maximization, random walk, randomized controlled trial, Richard Thaler, Robert Shiller, Robert Shiller, Ronald Coase, Silicon Valley, South Sea Bubble, statistical model, Steve Jobs, technology bubble, The Chicago School, The Myth of the Rational Market, The Signal and the Noise by Nate Silver, The Wealth of Nations by Adam Smith, Thomas Kuhn: the structure of scientific revolutions, transaction costs, ultimatum game, Walter Mischel

Of all the goods and services a family could buy, the family chooses the best one that it can afford. Furthermore, the beliefs upon which Econs make choices are assumed to be unbiased. That is, we choose on the basis of what economists call “rational expectations.” If people starting new businesses on average believe that their chance of succeeding is 75%, then that should be a good estimate of the actual number that do succeed. Econs are not overconfident. This premise of constrained optimization, that is, choosing the best from a limited budget, is combined with the other major workhorse of economic theory, that of equilibrium. In competitive markets where prices are free to move up and down, those prices fluctuate in such a way that supply equals demand. To simplify somewhat, we can say that Optimization + Equilibrium = Economics. This is a powerful combination, nothing that other social sciences can match.

(Lamont and Thaler), 250 capital asset pricing model (CAPM), 226–29, 348 “CAPM is Wanted, Dead or Alive, The” (Fama and French), 228 Car Talk, 32 Case, Chip, 235 Case-Shiller Home Price Index, 235 cashews, 21, 24, 42, 85–86, 92, 100, 102–3, 107n casinos, 49n cautious paternalism, 323 Census Bureau, 47 Center for Research in Security Prices (CRSP), 208, 221 charity, 66, 129 cheap stocks, 219–21 Checklist Manifesto, The (Gawande), 356 Chen, Nai-fu, 243 Chetty, Raj, 320, 357–58 Chicago, University of, 255–56 behavioral economics conference at, 159–64, 167–68, 169, 170, 205 conference on 1987 crash at, 237 debate on behavioral economics at, 159–63, 167–68, 169, 170, 205 finance studied at, 208 offices at, 270–76, 278 Chicago Bulls, 19 Chicago police department, 260 chicken (game of), 183 choice: number of, 21, 85, 99–103 preferences revealed by, 86 choice architecture, 276, 326–27, 357 Choices, Values, and Frames, xiv Chrysler, 121, 123, 363 Cialdini, Robert, 180, 335, 336 Clegg, Nick, 333 Clinton, Hillary, 22 closed-end funds, 238–39, 239, 240 puzzles of, 240–43, 244, 250 coaches, 292–93 Coase, Ronald, 261 Coase theorem, 261–62, 264–65, 264, 267–68 Cobb, David, 115 Cobb, Michael, 115, 116, 117, 118n, 119, 120, 123 Coca-Cola, 134–35 cognitive dissonance, 178 commitment strategies, 100, 102–3, 106–7 compliance (medical), 189–90 COMPUSTAT, 221 computing power, 208 concert tickets, 18–19, 66 conditional cooperators, 146, 182, 335n “Conference Handbook, The” (Stigler), 162–63 confirmation bias, 171–72 Conservative Party, U.K., 330–33 constrained optimization, 5–6, 8, 27, 43, 161, 207, 365 “Consumer Choice: A Theory of Economists’ Behavior” (Thaler), 35 consumers, optimization problem faced by, 5–6, 8, 27, 43, 161, 207, 365 consumer sovereignty, 268–69 consumer surplus, 59 consumption function, 94–98, 106, 309 “Contrarian Investment, Extrapolation, and Risk” (Lakonishok, Shleifer and Vishny), 228 cooperation, 143–47 conditional, 146, 182, 335n Prisoner’s Dilemma and, 143–44, 145, 301–5, 302 Copernican revolution, 169 Cornell University, 42, 43, 115, 140–43, 153–55, 157 Costco, 63, 71–72 Council of Economic Advisors, 352 coupons, 62, 63, 67–68, 120 credit cards, 18, 74, 76–77 late fees for, 360 crime, 265 Daily Mail, 135 Daily Show, The, 352 Dallas Cowboys, 281 data: financial, 208 collection and recording of, 355–56 Dawes, Robyn, 146 Deal or No Deal, 296–301, 297, 303 path dependence on, 298–300 deals, 61–62 De Bondt, Werner, 216–18, 221, 222–24, 226n, 233, 278 debt, 78 default investment portfolio, 316 default option, 313–16, 327 default saving rate, 312, 316, 319, 357 delayed gratification, 100–102 De Long, Brad, 240 Demos, 330 Denmark, 320, 357–58 descriptive, 25, 30, 45, 89 Design of Everyday Things, The (Norman), 326 Diamond, Doug, 273, 276 Diamond, Peter, 323 Dictator Game, 140–41, 142, 160, 182, 301 diets, 342 diminishing marginal utility, 106 of wealth, 28, 30 diminishing sensitivity, 30–34 discount, surcharge vs., 18 discounts, returns and, 242–43 discounted utility model, 89–94, 99, 110, 362 discretion, 106 Ditka, Mike, 279, 280 dividends, 164–67, 365 present value of, 231–33, 231, 237 Dodd, David, 219 doers, planners vs., 104–9 Donoghue, John, 265n “Do Stock Prices Move Too Much to be Justified by Subsequent Changes in Dividends?”


pages: 523 words: 143,139

Algorithms to Live By: The Computer Science of Human Decisions by Brian Christian, Tom Griffiths


4chan, Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, algorithmic trading, anthropic principle, asset allocation, autonomous vehicles, Berlin Wall, Bill Duvall, bitcoin, Community Supported Agriculture, complexity theory, constrained optimization, cosmological principle, cryptocurrency, Danny Hillis, delayed gratification, dematerialisation, diversification, double helix, Elon Musk, fault tolerance, Fellow of the Royal Society, Firefox, first-price auction, Flash crash, Frederick Winslow Taylor, George Akerlof, global supply chain, Google Chrome, Henri Poincaré, information retrieval, Internet Archive, Jeff Bezos, John Nash: game theory, John von Neumann, knapsack problem, Lao Tzu, linear programming, martingale, Nash equilibrium, natural language processing, NP-complete, P = NP, packet switching, prediction markets, race to the bottom, RAND corporation, RFC: Request For Comment, Robert X Cringely, sealed-bid auction, second-price auction, self-driving car, Silicon Valley, Skype, sorting algorithm, spectrum auction, Steve Jobs, stochastic process, Thomas Malthus, traveling salesman, Turing machine, urban planning, Vickrey auction, Walter Mischel, Y Combinator

Being a circuit lawyer meant literally making a circuit—moving through towns in fourteen different counties to try cases, riding hundreds of miles over many weeks. Planning these circuits raised a natural challenge: how to visit all the necessary towns while covering as few miles as possible and without going to any town twice. This is an instance of what’s known to mathematicians and computer scientists as a “constrained optimization” problem: how to find the single best arrangement of a set of variables, given particular rules and a scorekeeping measure. In fact, it’s the most famous optimization problem of them all. If it had been studied in the nineteenth century it might have become forever known as “the prairie lawyer problem,” and if it had first come up in the twenty-first century it might have been nicknamed “the delivery drone problem.”

See also uncertainty charity Cheshire, Stuart chess childhood Chomsky, Noam Churchill, Winston circuit switching clairvoyance clinical trials closet, organizing Cobham, Alan Cobham-Edmonds thesis Cockcroft, George (Luke Rhinehart) coconut water cognitive decline coincidences coins denominations two-headed tosses collators commitment problem communications. See also language; networking; storytelling confirmation priors and community-supported agriculture (CSA) Comparison Counting Sort comparison-shopping websites complexity penalizing computation, defined by Turing computational kindness confidence interval confirmation congestion avoidance of price of anarchy and Connection Machine constant-time (O(1)) constrained optimization problems constrained problem, preferences for Constraint Relaxation construction projects content distribution networks (CDNs) context switching continuous optimization problems Continuous Relaxation control without hierarchy Cooper, Martin cooperation Copernican Principle Copernicus, Nicolaus corporate marketing cost-benefit analysis Cramer, Jim Cravath system creativity crêpe stand queue Cross-Validation cryptography customer service hold times Darwin, Charles data.


pages: 257 words: 13,443

Statistical Arbitrage: Algorithmic Trading Insights and Techniques by Andrew Pole


algorithmic trading, Benoit Mandelbrot, Chance favours the prepared mind, constrained optimization, Dava Sobel, Long Term Capital Management, Louis Pasteur, mandelbrot fractal, market clearing, market fundamentalism, merger arbitrage, pattern recognition, price discrimination, profit maximization, quantitative trading / quantitative finance, risk tolerance, Sharpe ratio, statistical arbitrage, statistical model, stochastic volatility, systematic trading, transaction costs

A single pair spread expected to ‘‘revert to its local mean’’ may continue to increase beyond the point at which stop loss limits force exit from the position. This new element, risk, complicates the goal, which now becomes twofold: Maximize expected return and maintain the risk of achieving that return below a certain tolerance. So far so good. Going from foresight to forecast we exchange certainty for uncertainty; we move from guaranteed optimization to constrained optimization of a best guess. However, in practice matters are not quite as straightforward as that sentence seems to imply. The first obstacle is precisely specifying the notion of risk—or, at least, its practical implementation. Risk arises because there is no guarantee that a particular forecast will be borne out in reality. Indeed, the truth is that it would be an extraordinary event if a forecast turned out to be 100 percent accurate.


pages: 408 words: 85,118

Python for Finance by Yuxing Yan


asset-backed security, business intelligence, capital asset pricing model, constrained optimization, correlation coefficient, distributed generation, diversified portfolio, implied volatility, market microstructure, P = NP, p-value, quantitative trading / quantitative finance, Sharpe ratio, time value of money, value at risk, volatility smile

Our major function would start from Step 3 as shown in the following code: # Step 3: generate a return matrix (annul return) n=len(ticker) # number of stocks x2=ret_annual(ticker[0],begdate,enddate) for i in range(1,n): x_=ret_annual(ticker[i],begdate,enddate) x2=pd.merge(x2,x_,left_index=True,right_index=True) # using scipy array format R = sp.array(x2) print('Efficient porfolio (mean-variance) :ticker used') print(ticker) [ 216 ] Chapter 8 print('Sharpe ratio for an equal-weighted portfolio') equal_w=sp.ones(n, dtype=float) * 1.0 /n print(equal_w) print(sharpe(R,equal_w)) # for n stocks, we could only choose n-1 weights w0= sp.ones(n-1, dtype=float) * 1.0 /n w1 = fmin(negative_sharpe_n_minus_1_stock,w0) final_w = sp.append(w1, 1 - sum(w1)) final_sharpe = sharpe(R,final_w) print ('Optimal weights are ') print (final_w) print ('final Sharpe ratio is ') print(final_sharpe) From the following output, we know that if we use a naïve equal-weighted strategy, the Sharpe ratio is 0.63. However, the Sharpe ratio for our optimal portfolio is 0.67: Constructing an efficient frontier with n stocks Constructing an efficient frontier is always one of the most difficult tasks for finance instructors since the task involves matrix manipulation and a constrained optimization procedure. One efficient frontier could vividly explain the Markowitz Portfolio theory. The following Python program uses five stocks to construct an efficient frontier: from import quotes_historical_yahoo import numpy as np import pandas as pd [ 217 ] Statistical Analysis of Time Series from numpy.linalg import inv, pinv # Step 1: input area begYear,endYear = 2001,2013 stocks=['IBM','WMT','AAPL','C','MSFT'] # Step 2: define a few functions # function 1 def ret_monthly(ticker): x = quotes_historical_yahoo(ticker,(begYear,1,1),(endYear,12,31),asob ject=True,adjusted=True) logret=log(x.aclose[1:]/x.aclose[:-1]) date=[] for i in range(0,size(logret)): date.append(''.join([d0[i].strftime("%Y"),d0[i].strftime("%m")])) y=pd.DataFrame(logret,date,columns=[ticker]) return y.groupby(y.index).sum() # function 2: objective function def objFunction(W, R, target_ret): stock_mean=np.mean(R,axis=0),stock_mean) # portfolio mean cov=np.cov(R.T) # var-cov matrix,cov),W.T) # portfolio variance penalty = 2000*abs(port_mean-target_ret)# penalty 4 deviation return np.sqrt(port_var) + penalty # objective function # Step 3: Generate a return matrix R R0=ret_monthly(stocks[0]) # starting from 1st stock n_stock=len(stocks) # number of stocks for i in xrange(1,n_stock): # then merge with other stocks x=ret_monthly(stocks[i]) R0=pd.merge(R0,x,left_index=True,right_index=True) R=np.array(R0) # Step 4: estimate optimal portfolio for a given return out_mean,out_std,out_weight=[],[],[] stockMean=np.mean(R,axis=0) for r in np.linspace(np.min(stockMean), np.max(stockMean), num=100): [ 218 ] Chapter 8 W = ones([n_stock])/n_stock # starting from equal weights b_ = [(0,1) for i in range(n_stock)] # bounds, here no short c_ = ({'type':'eq', 'fun': lambda W: sum(W)-1. })#constraint result=sp.optimize.minimize(objFunction,W,(R,r),method='SLSQP',constr aints=c_, bounds=b_) if not result.success: # handle error raise BaseException(result.message) out_mean.append(round(r,4)) # 4 decimal places std_=round(np.std(np.sum(R*result.x,axis=1)),6) out_std.append(std_) out_weight.append(result.x) # Step 4: plot the efficient frontier title('Efficient Frontier') xlabel('Standard Deviation of the porfolio (Risk))') ylabel('Return of the portfolio') figtext(0.5,0.75,str(n_stock)+' stock are used: ') figtext(0.5,0.7,' '+str(stocks)) figtext(0.5,0.65,'Time period: '+str(begYear)+' ------ '+str(endYear)) plot(out_std,out_mean,'--') The output graph is presented as follows: [ 219 ] Statistical Analysis of Time Series Understanding the interpolation technique Interpolation is a technique used quite frequently in finance.


pages: 481 words: 125,946

What to Think About Machines That Think: Today's Leading Thinkers on the Age of Machine Intelligence by John Brockman


3D printing, agricultural Revolution, AI winter, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, algorithmic trading, artificial general intelligence, augmented reality, autonomous vehicles, bitcoin, blockchain, clean water, cognitive dissonance, Colonization of Mars, complexity theory, computer age, computer vision, constrained optimization, corporate personhood, cosmological principle, cryptocurrency, cuban missile crisis, Danny Hillis, dark matter, discrete time, Elon Musk, Emanuel Derman, endowment effect, epigenetics, Ernest Rutherford, experimental economics, Flash crash, friendly AI, Google Glasses, hive mind, income inequality, information trail, Internet of things, invention of writing, iterative process, Jaron Lanier, job automation, John von Neumann, Kevin Kelly, knowledge worker, loose coupling, microbiome, Moneyball by Michael Lewis explains big data, natural language processing, Network effects, Norbert Wiener, pattern recognition, Peter Singer: altruism, phenotype, planetary scale, Ray Kurzweil, recommendation engine, Republic of Letters, RFID, Richard Thaler, Rory Sutherland, Search for Extraterrestrial Intelligence, self-driving car, sharing economy, Silicon Valley, Skype, smart contracts, speech recognition, statistical model, stem cell, Stephen Hawking, Steve Jobs, Steven Pinker, Stewart Brand, strong AI, Stuxnet, superintelligent machines, supervolcano, the scientific method, The Wisdom of Crowds, theory of mind, Thorstein Veblen, too big to fail, Turing machine, Turing test, Von Neumann architecture, Watson beat the top human players on Jeopardy!, Y2K

He even predicted the tendency to see computer-intensive hill climbing as something cognitively special: “Perhaps what amounts to straightforward hill-climbing on one level may sometimes appear (on a lower level) as the sudden jumps of ‘insight.’” There are other AI algorithms, but most fall into categories Minsky wrote about. One example is running Bayesian probability algorithms on search trees or graphs. They have to grapple with exponential branching or some related form of the curse of dimensionality. Another example is convex or other nonlinear constrained optimization for pattern classification. Italian mathematician Joseph-Louis Lagrange found the general solution algorithm we still use today. He came up with it in 1811. Clever tricks and tweaks will always help. But progress here depends crucially on running these algorithms on ever faster computers. The algorithms themselves consist mainly of vast numbers of additions and multiplications, so they’re not likely to suddenly wake up one day and take over the world.


Commodity Trading Advisors: Risk, Performance Analysis, and Selection by Greg N. Gregoriou, Vassilios Karavas, François-Serge Lhabitant, Fabrice Douglas Rouah


Asian financial crisis, asset allocation, backtesting, capital asset pricing model, collateralized debt obligation, commodity trading advisor, compound rate of return, constrained optimization, corporate governance, correlation coefficient, Credit Default Swap, credit default swaps / collateralized debt obligations, discrete time, distributed generation, diversification, diversified portfolio, dividend-yielding stocks, fixed income, high net worth, implied volatility, index arbitrage, index fund, interest rate swap, iterative process, linear programming, London Interbank Offered Rate, Long Term Capital Management, market fundamentalism, merger arbitrage, Mexican peso crisis / tequila crisis, p-value, Ponzi scheme, quantitative trading / quantitative finance, random walk, risk-adjusted returns, risk/return, Sharpe ratio, short selling, stochastic process, systematic trading, technology bubble, transaction costs, value at risk

MSCI Global −0.52 −1.25 17.23 12.56 0.21 1.57% 4.32% 0.63 0.82 0.87 3.24 1.51% 0.30% 28 MSCI Global 1.18% 4.15% 28 Futures Fund Index 50–60% 0.64 2.07 0.19 1.05 3.90% 0.41% 3.88% 28 Futures Fund Index −0.30 −1.32 28.80 13.37 −0.01 2.49% 2.42% 0.32% 28 MSCI Global 60–70% −0.48 0.18 −0.49 −1.23 3.33% 0.12 −1.45 34.47 14.29 0.31 3.66% 28 3.57% 0.43% 28 MSCI Global −0.29% 3.31% Futures Fund Index 70–80% 1.61 4.08 1.98 6.28 5.88% 2.77% 5.15% 28 Futures Fund Index 0.47 −1.16 50.82 15.51 0.38 5.04% 4.94% 0.44% 28 MSCI Global 80–90% 0.93 0.44 0.65 2.47 5.71% 1.25% 5.56% 28 Futures Fund Index 0.82 −0.34 24.41 17.87 0.26 8.02% 7.71% 1.68% 28 MSCI Global 90–100% 356 0/100 10/90 20/80 30/70 40/60 50/50 60/40 70/30 80/20 90/10 100/0 Combination Returns −3.36% −2.86% −2.36% −1.85% −1.35% −0.85% −1.02% 0.16% 0.66% 1.16% 1.67% −7.57% −6.57% −5.57% −4.57% −3.57% −2.57% −3.08% −0.57% 0.43% 1.44% 2.44% 10– 20% Returns 0– 10% −1.86% −1.71% −1.56% −1.42% −1.27% −1.12% −1.34% −0.83% −0.68% −0.53% −0.38% Returns 20– 30% −0.58% −0.49% −0.40% −0.31% −0.22% −0.14% −0.16% 0.04% 0.13% 0.22% 0.31% Returns 30– 40% 0.43% 0.43% 0.44% 0.45% 0.45% 0.46% 0.55% 0.47% 0.48% 0.49% 0.50% Returns 40– 50% 1.51% 1.48% 1.44% 1.41% 1.38% 1.34% 1.61% 1.28% 1.25% 1.21% 1.18% Returns 50– 60% TABLE 19.5 Combining Futures and Equity Indices in Different Proportions 2.42% 2.22% 2.02% 1.82% 1.62% 1.42% 1.70% 1.01% 0.81% 0.61% 0.41% Returns 60– 70% 3.57% 3.18% 2.79% 2.41% 2.02% 1.64% 1.96% 0.87% 0.48% 0.09% −0.29% Returns 70– 80% 90– 100% 4.94% 4.72% 4.50% 4.29% 4.07% 3.85% 4.62% 3.42% 3.20% 2.99% 2.77% 7.71% 7.06% 6.41% 5.77% 5.12% 4.48% 5.37% 3.18% 2.54% 1.89% 1.25% Returns Returns 80– 90% 7.19% 7.45% 7.72% 7.98% 8.25% 8.51% 10.22% 9.04% 9.31% 9.58% 9.84% Portfolio Returns CTA Strategies for Returns-Enhancing Diversification 357 were to look for the least number of negative periods, then the combination of 90/10 would almost ensure that there would only be a 1 in 10 chance of negative returns. The results illustrate a useful idea: If we are concerned about event risk, we may wish to define our objective function as one that has the least number of negative returns during the investment horizon, with the constraint that the correlation at first decile should be the lowest. This could be a useful framework to carry out constrained optimization of portfolio returns. CONCLUSION Our results indicate that the risk-adjusted returns as measured by Sharpe and Sortino ratios are always higher in CTA strategies than in most traditional asset classes for the entire sample period under study. Unlike hedge funds, the correlation coefficients of the CTAs with the equity markets are negative during bad times (worst performance period of the equity markets).


Culture and Prosperity: The Truth About Markets - Why Some Nations Are Rich but Most Remain Poor by John Kay


Albert Einstein, Asian financial crisis, Barry Marshall: ulcers, Berlin Wall, Big bang: deregulation of the City of London, California gold rush, complexity theory, computer age, constrained optimization, corporate governance, corporate social responsibility, correlation does not imply causation, Daniel Kahneman / Amos Tversky, David Ricardo: comparative advantage, Donald Trump, double entry bookkeeping, double helix, Edward Lloyd's coffeehouse, equity premium, Ernest Rutherford, European colonialism, experimental economics, Exxon Valdez, failed state, financial innovation, Francis Fukuyama: the end of history, George Akerlof, George Gilder, greed is good, haute couture, illegal immigration, income inequality, invention of the telephone, invention of the wheel, invisible hand, John Nash: game theory, John von Neumann, Kevin Kelly, knowledge economy, labour market flexibility, late capitalism, Long Term Capital Management, loss aversion, Mahatma Gandhi, market bubble, market clearing, market fundamentalism, means of production, Menlo Park, Mikhail Gorbachev, money: store of value / unit of account / medium of exchange, moral hazard, Naomi Klein, Nash equilibrium, new economy, oil shale / tar sands, oil shock,, popular electronics, price discrimination, price mechanism, prisoner's dilemma, profit maximization, purchasing power parity, QWERTY keyboard, Ralph Nader, RAND corporation, random walk, rent-seeking, risk tolerance, road to serfdom, Ronald Coase, Ronald Reagan, second-price auction, shareholder value, Silicon Valley, Simon Kuznets, South Sea Bubble, Steve Jobs, telemarketer, The Chicago School, The Death and Life of Great American Cities, The Market for Lemons, The Nature of the Firm, The Predators' Ball, The Wealth of Nations by Adam Smith, Thorstein Veblen, total factor productivity, transaction costs, tulip mania, urban decay, Washington Consensus, women in the workforce, yield curve, yield management

He should do just the amount of calculation needed to find the best strategy in the light of his knowledge that every second devoted to calculation increases the chances ofbeing caught by the bear. 18 Borrowing Herbert Simon's term (but for a very different concept), Oliver Williamson calls this optimization under constraints-bounded rationality. 19 In this vein, transactions costs economics often degenerates into a Panglossian view of the world: institutions that exist must be the solution to some constrained-optimization problem. Economists even have a word-recoverability-for deducing the maximization problem to which observed behavior is the answer. But this version of bounded rationality confronts a fundamental problem. How could the economist know when to stop calculating { 220} John Kay when he cannot know the benefits of further calculation? If we knew enough to be boundedly rational, we would know enough to be completely rational.


pages: 662 words: 180,546

Never Let a Serious Crisis Go to Waste: How Neoliberalism Survived the Financial Meltdown by Philip Mirowski


Andrei Shleifer, asset-backed security, bank run, barriers to entry, Basel III, Berlin Wall, Bernie Madoff, Bernie Sanders, Black Swan, blue-collar work, Bretton Woods, Brownian motion, capital controls, Carmen Reinhart, Cass Sunstein, central bank independence, cognitive dissonance, collapse of Lehman Brothers, collateralized debt obligation, complexity theory, constrained optimization, credit crunch, Credit Default Swap, credit default swaps / collateralized debt obligations, crony capitalism, dark matter, David Brooks, David Graeber, debt deflation, deindustrialization, Edward Glaeser, Eugene Fama: efficient market hypothesis, experimental economics, facts on the ground, Fall of the Berlin Wall, financial deregulation, financial innovation, Flash crash, full employment, George Akerlof, Goldman Sachs: Vampire Squid, Hernando de Soto, housing crisis, Hyman Minsky, illegal immigration, income inequality, incomplete markets, invisible hand, Jean Tirole, joint-stock company, Kenneth Rogoff, knowledge economy, l'esprit de l'escalier, labor-force participation, liquidity trap, loose coupling, manufacturing employment, market clearing, market design, market fundamentalism, Martin Wolf, Mont Pelerin Society, moral hazard, mortgage debt, Naomi Klein, Nash equilibrium, night-watchman state, Northern Rock, Occupy movement, offshore financial centre, oil shock, payday loans, Ponzi scheme, precariat, prediction markets, price mechanism, profit motive, quantitative easing, race to the bottom, random walk, rent-seeking, Richard Thaler, road to serfdom, Robert Shiller, Robert Shiller, Ronald Coase, Ronald Reagan, savings glut, school choice, sealed-bid auction, Silicon Valley, South Sea Bubble, Steven Levy, technoutopianism, The Chicago School, The Great Moderation, the map is not the territory, The Myth of the Rational Market, the scientific method, The Wisdom of Crowds, theory of mind, Thomas Kuhn: the structure of scientific revolutions, Thorstein Veblen, Tobin tax, too big to fail, transaction costs, War on Poverty, Washington Consensus, We are the 99%, working poor

While the focus on procyclical movement of leverage and asset prices is an important departure from much of orthodox models, the commitment to Walrasian general equilibrium so hampers the formalism that good intentions ended up in Bedlam. Geanakoplos likes to phrase his commentary in terms of “cycles,” but in fact, general equilibrium forces him to posit separate and unconnected sequential states of equilibrium, driven in a Rube Goldberg fashion by the arbitrarily sequenced arrival of asset issuance→“news”→valuation. Each state along the way is in “equilibrium,” as defined by constrained optimization and market clearing. Because everything is always already in equilibrium, the only reason anything changes is the deus ex machina imposed from outside by the model builder. Worse, the sequence itself is completely arbitrary, dictated more by the math than by anything that happens in the world: for instance, each player has only one chance to issue assets, is proscribed from trading them on secondary markets, and consumption can happen only at the initial issuance and at the end of time.108 It seems that, however proud he may be of hewing to Walrasian heuristics, the suite of models he has constructed rarely do much to actually illuminate the actual crisis and aftermath.