2 098 6 255 15 093 Recitation 8 Michael Frankovich and Shubham Gupta November 13 2009 1 Dynamic Programming The number of crimes in 3 areas of a city as a function of the number of police patrol cars assigned there is indicated in the following table n 0 Area 1 14 Area 2 25 Area 3 20 1 10 19 14 2 7 16 11 3 4 14 8 We have a total of only 3 police cars to assign Solve the problem of minimizing the total number of crimes in the city by assigning patrol cars using dynamic programming Solution Firstly we de ne the following elements of our dynamic program We let N 3 so we have 4 stages At k 0 we assign some number of cars to area 1 then we are nished with area 1 Then at stage k 1 we assign from our remaining cars some number to area 2 and so on At k N 3 we are done and any leftover cars have no cost 1 State xk number of patrol cars available at stage k 2 Control uk number of patrol cars to assign at stage k to area k 1 3 Randomness k constant 4 Dynamics xk 1 xk uk 5 Boundary Conditions JN xN 0 xN 6 Recursion Jk xk min gk xk uk k Jk xk 1 min gk xk uk Jk xk uk uk Uk uk Uk 1 J2 x2 min u2 0 x2 g2 x2 u2 0 g1 x1 u1 J2 x1 u1 J2 20 14 11 8 ie notation for J2 0 20 J2 1 14 etc J1 x1 min u1 0 x1 J1 25 20 min 25 14 19 20 min 25 11 19 14 16 20 min 25 8 19 11 16 14 14 20 45 39 33 30 J0 3 min u0 0 3 g0 x0 u0 J1 x0 u0 min 14 30 10 33 7 39 4 45 43 So the optimal cost is 43 crimes Tracing the argminima we see that the optimal solution is to assign one car to each of the three areas 2 Linear Algebra Calculus Review for NLP De nition A norm on Rn is a mapping from Rn to R that satis es a x 0 x Rn b cx c x c R x Rn c x 0 x 0 d x y x y x y Rn The following are common norms The Euclidean Norm or L2 norm x 2 The L1 norm x 1 ni 1 xi The p norm p 1 x p n p i 1 xi The L norm or max norm x x x n 2 i 1 xi 12 p1 L1 and L2 are p norms max x1 xn Let A be a real valued symmetric i e A A n n matrix Then Its eigenvalues are real The following are equivalent 2 a A is positive de nite b All eigenvalues of A are 0 c x Ax 0 x Rn 0 The following are equivalent a A is positive semi de nite b All eigenvalues of A are 0 c x Ax 0 x Rn De nition Let f Rn R Then when they exist f xi lim 0 f x e i f x is the ith partial derivative of f at x f x1 f x is the gradient of f at x f xn 2f x21 2f x1 xn 2f xn x1 2f x2n 2 f x 3 is the hessian of f at x How to determine whether a function is convex Once we know a few basic classes of convex functions we can use the following facts Linear functions f x a x b are convex Quadratic functions f x 12 x Qx b x are convex if Q is PSD positive semi de nite Norms are convex functions the proof is left an exercise using the properties of norms de ned above g x ki 1 ai fi x is convex if ai 0 fi convex i 1 k Alternatively if a function is di erentiable we can use the following facts 2 f x is PSD x f is convex 2 f x is PD positive de nite x f is strictly convex 3 Finally if the function is not di erentiable and we cannot use one of the above ap proaches we check the de nition of convexity De nition A function f Rn R is convex if x y Rn we have f x 1 y f x 1 f y 3 1 0 1 Example Let f Rn R x1 x2 x1 x22 x1 So 2 x2 1 f x 2x1 x2 0 2x2 2 f x 2x2 2x1 To solve for the eigenvalues of the hessian we get the following quadratic in 2 2x2 0 det f x det 2x2 2x1 2 2x1 4x22 0 Since the constant term is negative we cannot have two roots i e eigenvalues of the same sign Hence f can be neither convex nor concave 4 MIT OpenCourseWare http ocw mit edu 15 093J 6 255J Optimization Methods Fall 2009 For information about citing these materials or our Terms of Use visit http ocw mit edu terms