overview

IEOR E4007: Optimization Models and Methods Overview of Optimization Garud Iyengar Columbia University Industrial Engineering and Operations Research Asset Allocation Problem: Allocate wealth W (= $10M) over d (= 6) assets. Iteration 1 Decision: x i = $ invested in asset i = 1 , . . . , d Constraints: x i ≥ 0 (long only), ∑ d i =1 x i = W Objective function: maximize expected return E [˜ r x ] = ∑ d i =1 x i E [˜ r i ] How does one estimate the expected return of the investment? Historical prices p ( t ) i ... historical rate of return r ( t ) i = p ( t +1) i - p ( t ) i p ( t ) i Estimate of expected rate of return of asset i : ˆ μ i = 1 T ∑ T t =1 r ( t ) i Estimate of expected return of investment: ∑ d i =1 ˆ μ i x i Note that statistics and estimated quantities enter the model. 2

Iteration 1 (contd.) Optimization model maximize ∑ d i =1 ˆ μ i x i subject to ∑ d i =1 x i = W, x i ≥ 0 , i = 1 , . . . , d. A function f ( x ) : R d → R is called linear if for all α, β ∈ R and x , y ∈ R d f ( α x + β y ) = αf ( x ) + βf ( y ) Can show that f ( x ) = c x = ∑ d i =1 c i x i for some c = [ c 1 , . . . , c d ] ∈ R d Above optimization model has linear objective function constraints of the form f ( x ) ≥ or ≤ or = b for some linear function f Such an optimization problem is called a linear program . 3 Optimization models Optimization = selecting best allocation of limited resources subject to constraints imposed by the problem. Model = Mathematical approximation/abstraction of the “real” problem Models can be used for optimization, simulation or scenario analysis. Components of an optimization model Decision variables: mathematical representation of the decisions Constraints: limits on the choices for the decisions Objective function(s): goals to optimize 4

Iteration 2: Penalize variability! Variance of the investment return var (˜ r x ) = var d i =1 x i ˜ r i = d i =1 d j =1 x i x j cov (˜ r i , ˜ r j ) How does one estimate the covariance? Historical estimate cov (˜ r i , ˜ r j ) ≈ ˆ Q ij = 1 T - 1 T t =1 ( r ( t ) i - ˆ μ i )( r ( t ) j - ˆ μ j ) Problems? Can one do better? Use Capital Asset Pricing Model and other forward looking methods 7 Iteration 2 (contd) Optimization model maximize ∑ d i =1 ˆ μ i x i - λ ∑ d i =1 ∑ d j =1 x i x j ˆ Q ij = ˆ μ x - λ x ˆ Q x subject to 1 x = W, x ≥ 0 . quadratic objective function: λ = risk aversion parameter linear constraints Such a model is called a quadratic program . Really a two objective problem: maximize E [˜ r x ] and minimize var (˜ r x ) Characterize the Pareto frontier or the Efficient frontier for the two quantities Can be done in three different ways 8

Iteration 2 (contd) variance var ( r x ) Expected return E [ r x ] min var ( r x ) s.t. E [ r x ] ≥ ¯ r ¯ r max E [ r x ] s.t. var ( r x ) ≤ σ 2 σ 2 max E [ r x ] - λ var ( r x ) 9 Iteration 2: Stress testing the model Statistical issues Variance is a good measure only for elliptical distributions. Particularly bad for heavy tailed distributions. Number of correlations grow as O ( d 2 ) . Never have enough data! Errors in correlations have serious impact on portfolio holdings. Operational issues How does one estimate the risk aversion? Many assets have very small holdings. Either x i = 0 or | x i | ≥ L How does one handle trading costs? May be add a penalty term maximize ˆ μ x - λx ˆ Q x - η x - x old subject to 1 x = W, x ≥ 0 . What does this miss? 10

Iteration 4: Neural network (NN) approach Inputs Past returns on the assets Past factor values: interest rates, economic indicators, etc. Output Portfolio: x ≥ 0 , ∑ d i =1 x i ≤ W What NN output structure to use? Soft-max. But how does one get inequality in the budget? Training: Use historical data with an appropriate loss function Pro: Very flexible! Cons: Local optimum solution Constraints are hard to impose Not interpretable ... well not quite Not robust ... well not quite 13 Iteration 5: Dynamics Asset allocation problems are never 1-period problems! Long term goals: Financing retirement, purchasing the first home, education Multiple re-balancing Model Position at time n : y ( n ) = ( y ( n ) 1 , . . . , y ( n ) d ) New position after trade at time n : x Trading cost: c ( x, y ) Market returns realized ... positions at time n + 1 : y ( n +1) = (1 + ˜ r ( n ) 1 ) x 1 , . . . , (1 + ˜ r ( n ) d ) x d = R ( n ) ◦ x 14

Iteration 4 (contd.) V n ( y ) = “value” of holding position y at time n . Then V n ( y ) = max x c ( x, y ) + 1 1 + ι n E V n +1 ( R ( n ) ◦ x ) Bellman equation ... Dynamic programming Is the expectation with respect to “ Real world ” or risk neutral probability? Computational issues: Have to recursively compute the value function V n . Computationally intractable! New idea: approximate V n ( x ) = ∑ k β k f k ( x ) for some basis functions f k . Computation β using regression. Method called Approximate Dynamic Progamming . 15 Course structure This course is about modeling and solving optimization models approximate problems by a standard model solve a set of standard models using standard solvers Other issues Robustness of the model Sensitivity of the solution Large scale models and iterative solutions Theory supports the last set of questions Theory supports applications If you do not see a connection, interrupt me! 16