Optimization Methods - Dynamic Programming

1 Outline 1. 2. 3. 4. 5. 6. 7. Slide 1 The knapsack problem The traveling salesman problem The general DP framework Bellman equation Optimal inventory control Optimal trading Multiplying matrices 2 The Knapsack problem maximize subject to De ne n X j �1 n X Slide 2 cj xj wj xj j �1 xj 2 f0 1g Ci (w) = maximize subject to i X j �1 i X K cj xj wj xj j �1 xj 2 f0 1g w 2.1 A DP Algorithm  Ci (w): the maximum value that can be accumulated using some of the rst i items subject to the constraint that the total accumulated weight is equal to w  Recursion Ci+1(w) = max Ci (w) Ci (w ; wi+1 ) + ci+1  By considering all states of the form (i w) with w complexity O(nK) 1
K, algorithm has Slide 3 3 The TSP     G = (V A) directed graph with n nodes cij cost of arc (i j) Approach: choice of a tour as a sequence of choices We start at node 1 then, at each stage, we choose which node to visit next.  After a number of stages, we have visited a subset S of V and we are at a current node k 2 S 3.1 A DP algorithm  C(S k) be the minimum cost over all paths that start at node 1, visit all Slide 4 Slide 5 nodes in the set S exactly once, and end up at node k ;  (S k) a state this state can be reached from any state of the form S n fkg m , with m 2 S n fkg, at a transition cost of cmk  Recursion   ;  S n f k g m + c k2S C(S k) = m2min C mk S nfkg ;  Length of an optimal tour is  C f1g 1 = 0:  ; ;   min C f1 : : : ng k + ck1 k   Complexity: O n22n operations 4 Guidelines for constructing DP Algorithms  View the choice of a feasible solution as a sequence of decisions occurring in stages, and so that the total cost is the sum of the costs of individual decisions.  De ne the state as a summary of all relevant past decisions.  Determine which state transitions are possible. Let the cost of each state transition be the cost of the corresponding decision.  Write a recursion on the optimal cost from the origin state to a destination state. The most crucial step is usually the de nition of a suitable state. 2 Slide 6 5 The general DP framework      Discrete time dynamic system described by state xk , k indexes time. uk control to be selected at time k. uk 2 Uk (xk ). wk randomness at time k N time horizon Dynamics: xk+1 = fk (xk uk wk)  Cost function: additive over time  E gN (xN ) + NX ;1 k�0 Slide 7 ! gk (xk uk wk) 5.1 Inventory Control  xk stock available at the beginning of the kth period  uk stock ordered at the beginning of the kth period  wk demand duirng the kth period with given probability distribution. Slide 8 Excess demand is backloged and lled as soon as additional inventory is available.  Dynamics xk+1 = xk + uk ; wk  Cost  ! NX ;1 E R(xN ) + (r(xk ) + cuk ) k�0 6 The DP Algorithm  De ne Jk (xk ) to be the expected optimal cost starting from stage k at state xk .  Bellman's principle of optimality JN (xN ) = gN (xN ) Jk (xk ) =  min E g (x u w ) + Jk+1 (fk (xk uk wk)) uk 2Uk (xk ) wk k k k k  Optimal expected cost for the overall problem: J0(x0 ). 3 Slide 9 7 Inventory Control  If r(xk ) = ax2k , wk  N (k k2), then Slide 10 Jk (xk ) = bk xk2 + fk xk + ek uk = ck xk + dk  If r(xk ) = p max(0 ;xk ) + h max(0 xk ) , then there exist Sk :  < Sk uk = 0Sk ; xk ifif xxk  k Sk 8 Optimal trading  S shares of a stock to be bought within a horizon T .  t = 1 2 : : : T discrete trading periods.  Control: St number of shares acquired in period t at price Pt, t = 1 2 : : : T T X  Objective: min E t�1 Slide 11 Pt St s:t: T X t�1 St = S  Dynamics: Pt = Pt;1 + St + t where  > 0, t  N (0 1) 8.1 DP ingredients Slide 12  State: (Pt;1 Wt) Pt;1 price realized at the previous period Wt # of shares remaining to be purchased  Control: St number of shares purchased at time t  Randomness: t  Objective: min E PT t�1 Pt St  Dynamics: Pt = Pt;1 + St + t Wt = Wt;1 ; St;1 W1 = S WT +1 = 0 Note that WT +1 = 0 is equivalent to the constraint that S must be executed by period T 4 Slide 13 8.2 The Bellman Equation Jt (Pt;1 Wt) = min E PtSt + Jt+1 (Pt Wt+1) St t Slide 14 JT (PT ;1 WT ) = min E P W ] = (PT ;1 + WT )WT ST T T T Since WT +1 = 0 ) ST = WT 8.3 Solution = = JT ;1(PT ;2 WT ;1) = Slide 15 min ET ;1 PT ;1ST ;1 + JT (PT ;1 WT ) ST ;1 min ET ;1 (PT ;2 + ST ;1 + T ;1 )ST ;1 + ST ;1 JT PT ;2 + ST ;1 + T ;1 WT ;1 ; ST ;1 ST ;1 = JT ;1 (PT ;2 WT ;1) = WT ;1 2 WT ;1 (PT ;2 + 43 WT ;1) Continuing in this fashion, ST ;k = JT ;k (PT ;k;1 WT ;k ) = S1 = J1(P0 W1) = WT ;k k+1 k + 2 W ) WT ;k (PT ;k;1 + 2(k + 1) T ;k S T 2 S P0S + 2 1 + T1 S1 = S2 =    = ST = TS 5 Slide 16 8.4 Dierent Dynamics Pt Xt = = Slide 17 Pt;1 + St + Xt + t Xt;1 + t X1 = 1 >0 2 (;1 1) where t  N (0 2) and t  N (0 
2) 8.5 Solution Slide 18 ST ;k = WT ;k + bk;1 X k+1 2ak;1 T ;k JT ;k (PT ;k;1 XT ;k WT ;k ) = PT ;k;1WT ;k + ak WT2;k + bk XT ;k WT ;k + ck XT2 ;k + dk for k = 0 1 : : : T ; 1, where: ak = 2 1 + k +1 1 bk = ck = dk = a0 =   + 2abk;1 k;1 2 ck;1 22 ; 4abk;1 k;1 dk;1 + ck;1
2 b0 =  c0 = 0 d0 = 0 : 9 Matrix multiplication  Matrices: Mk : nk  nk+1  Objective: Find M1  M2    MN  Example: M1  M2  M3  M1 : 1  10, M2 : 10  1, M3 : 1  10. Slide 19 M1 (M2 M3 ) 200 multiplications (M1 M2 )M3 20 multiplictions.  What is the optimal order for performing the multiplication? 6 Slide 20  m(i j) optimal number of scalar multiplications for multiplying Mi : : :Mj .  m(i i) = 0  For i < j : m(i j) = imin (m(i k) + m(k + 1 j ) + ni nk+1nj +1 ) k