1 Lecture Outline History of Nonlinear Optimization Where do NLPs Arise? Portfolio Optimization Trac Assignment The general problem The role of convexity Convex optimization Examples of convex optimization problems 2 History of Optimization Fermat, 1638 Newton, 1670 Euler, 1755 Lagrange, 1797 Slide 1 Slide 2 min f (x) x: scalar df (x) = 0 dx min f (x1 : : : xn) rf (x) = 0 min f (x1 : : : xn) s.t. gk (x1 : : : xn) = 0 k = 1 : : : m Euler, Lagrange Problems in in nite dimensions, calculus of variations. Kuhn and Tucker, 1950s Optimality conditions. 1950s Applications. 1960s Large Scale Optimization. Karmakar, 1984 Interior point algorithms. 1 Slide 3 3 Where do NLPs Arise? 3.1 Wide Applicability Transportation Trac management, Trac equilibrium . . . Revenue management and Pricing Finance - Portfolio Management Equilibrium Problems Slide 4 Slide 5 Engineering Data Networks and Routing Pattern Classi cation Manufacturing Resource Allocation Production Planning 4 A Simple Portfolio Selection Problem 4.1 Data xi : decision variable on amount to invest in stock i = 1 2 ri : reward from stock i = 1 2 (random variable) Data: i = E(ri ): expected reward from stock i = 1 2 V ar(ri): variance in reward from stock i = 1 2 ij = E (rj ; j )(ri ; i )] = C ov(ri rj ) Budget B, target on expected portfolio reward 2 Slide 6 5 A Simple Portfolio Selection Problem 5.1 The Problem Objective: Minimize total portfolio variance so that: Expected reward of total portfolio is above target Total amount invested stay within our budget No short sales subject to Slide 7 Slide 8 min f (x) = x21 V ar(r1) + x22 V ar(r2) + 2x1x2 12 X E X i ri xi ] = (Linearly constrained NLP) X i i xi B i xi (exp reward of portf:) xi 0 i = 1 2 6 A Real Portfolio Optimization Problem 6.1 Data We currently own zi shares from stock i, i 2 S Pi : current price of stock i We consider buying and selling stocks in S, and consider buying new stocks from a set B (B \ S = ) Set of stocks B S = f1 : : : ng Data: Forecasted prices next period (say next month) and their correlations: E P^i] = i C ov(P^i P^j ) = E (P^i ; i)(P^j ; j )] = ij = ij = (1 : : : n) 0 3 Slide 9 Slide 10 6.2 Issues and Objectives Mutual funds regulations: we cannot sell a stock if we do not own it Transaction costs Turnover Liquidity Volatility Objective: Maximize expected wealth next period minus transaction costs 6.3 Decision variables xi = By convention: # shares bought or sold if i 2 S # shares bought if i 2 B xi 0 xi < 0 Slide 11 Slide 12 buy sell 6.4 Transaction costs Small investors only pay commision cost: ai $/share traded Transaction cost: ai jxij Large investors (like portfolio managers of large funds) may aect price: price becomes Pi + bi xi Price impact cost: (Pi + bi xi )xi ; Pixi = bi x2i Total cost model: ci (xi ) = ai jxij + bi x2i 6.5 Liquidity Suppose you own 50% of all outstanding stock of a company How dicult is to sell it? Reasonable to bound the percentage of ownership on a particular stock + xi Thus, for liquidity reasons zzi total i i zitotal =# outstanding shares of stock i i maximum allowable percentage of ownership 4 Slide 13 Slide 14 6.6 Turnover Because of transaction costs: jxij should be small jxij i ) ;i xi i Slide 15 Alternatively, we might want to bound turnover: n X Pi jxij t i�1 6.7 Balanced portfolios Need the value of stocks we buy and sell to balance out: n n X Pixi L ) ;L X Pixi L i�1 i�1 No short sales: Slide 16 i2 BS z i + xi 0 6.8 Expected value and Volatility Expected value of portfolio: "n # n X^ X E Pi (zi + xi) = i (zi + xi) i�1 Slide 17 i�1 Variance of the value of the portfolio: "n # X^ V ar Pi(zi + xi ) = (z + x) (z + x) 0 i�1 6.9 Overall formulation n X n X (ai jxij + bi x2i ) max i (zi + xi ) ; i�1 i�1 s:t: (z + x) �(z + x) 2 zi + xi i zitotal ;i xi i 0 ;L n X i�1 n X i�1 Pixi L Pi jxi j t zi + xi 0 5 Slide 18 7 The general problem f (x): 0 : ;! cp (x ) cp (x ) 8p 2 Pw 8w 2 W where cp (x) is the travel time of path p and X cp (x) = cij (xij ) 8p 2 Pw 8w 2 W � � (i j ) 0 � 0 on p 10 Optimal Routing Given a data net and a set W of OD pairs w = (i j) each OD pair w has input trac dw Optimal routing problem: X X xp ) M in C (x) = Ci j ( s:t: X p2Pw xp 0 ij p: (i j )2p x p = dw 8w 2 W 8p 2 Pw w2W 11 The general problem again f (x): 0 such that x 2 F is a global minimum of N LOP if f (x) f (y) for all y 2 F 12 Convex Sets A subset S Slide 31 0 f (x) = x1 for x > 0 f (x) = ex 13.2 Properties If f1 (x) and f2 (x) are convex functions, and a b 0, then f (x) := af1 (x) + bf2 (x) is a convex function If f (x) is a convex function and x = Ay + b, then g(y) := f (Ay + b) is a convex function 13.3 Recognition of a Convex Function A function f (x) is twice di erentiable at x if there exists a vector rf (x) (called the gradient of f ()) and a symmetric matrix H(x) (called the Hessian of f ()) for which: f (x ) = f (x) + rf (x) (x ; x ) + 21 (x ; x ) H(x)(x ; x ) + R(x)jjx ; x jj2 where R(x) ! 0 as x ! x The gradient vector is the vector of partial derivatives: @f (x ) x ) @f ( rf ( x) = @x1 : : : @xn Slide 34 Slide 35 0 0 0 10 Slide 36 The Hessian matrix is the matrix of second partial derivatives: @ 2 f (x) H(x)ij = @x i @xj 13.4 Examples For LP, f (x) = c x, rf (x) = c For NLP, f (x) = 8x21 ; x1 x2 + x22 + 8x1, at x = (1 0), f (x) = 16 and rf (x ) = (16x1 ; x2 + 8 ;x1 + 2x2) = (24 ;1). H (x) = ;161 ;2 1 Property: f (x) is a convex function if and only if H(x) is positive semi-de nite (PSD) for all x Recall that A is PSD if u Au 0 8u Property: If H(x) is PD for all x, then f (x) is a strictly convex function 0 Slide 37 0 Slide 38 0 13.5 Examples in n Dimensions Slide 39 f (x) = a x + b f (x) = 21 x Mx ; c x where M is PSD f (x) = jjxjj for any norm jj jj m P f (x) = ; ln(bi ; ai x) for x satisfying Ax < b 0 0 0 0 i�1 14 Convex Optimization 14.1 Convexity and Minima Slide 40 min f (x) s.t. x 2 F Theorem: Suppose that F is a convex set, f : F ! < is a convex function, and x is a local minimum of P . Then x is a global minimum of f over F . � � 14.1.1 Proof Assume that x is not the global minimum. Let y be the global minimum. From the convexity of f (), f (y ( )) = f ( x + (1 ; )y ) f (x ) + (1 ; )f (y ) < f (x ) + (1 ; )f (x ) = f (x ) � � � � 11 � � Slide 41 for all 2 (0 1). Therefore, f (y ( )) < f (x ) for all resulting in a contradiction � 2 (0 1), and so x is not a local minimum, � 14.2 COP C OP : min f (x) s:t: g1(x) 0 .. . gm (x) 0 Ax = b C OP is called a convex optimization problem if f (x) g1(x) : : : gm (x) are convex functions Note that this implies that the feasible region F is a convex set In C OP we are minimizing a convex function over a convex set Implication: If C OP is a convex optimization problem, then any local minimum will be a global minimum. 15 Examples of COPs The Fermat-Weber Problem - COP m P wijjx ; cijj min i�1 s:t: x 2 P The Ball Circumscription Problem - COP min s:t: jjx ; ci jj i = 1 ::: m 12 Slide 42 Slide 43 Slide 44 15.1 Is Portfolio Optimization a COP? max n X i�1 i (zi + xi ) ; n X i�1 Slide 45 (ai jxij + bi x2i ) s:t: (z + x) �(z + x) 2 zi + xi i zitotal 0 ;i xi i n X ;L Pixi L n X i�1 i�1 Pi jxi j t zi + xi 0 15.2 Quadratically Constrained Problems 0 0 0 This is a COP Slide 46 min (A0x + b0 ) (A0x + b0) ; c0 x ; d0 s:t: (Aix + bi) (Aix + bi) ; ci x ; di 0 i = 1 ::: m 0 16 Classi cation of NLPs Linear: f (x) = ctx, gi(x) = Ati x ; bi, i = 1 ::: m Unconstrained: f (x),