� � � � 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 1 2 3 Area 1 14 10 7 4 Area 2 25 19 16 14 Area 3 20 14 11 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 define 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 finished 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 g2(x2, u2) + 0 u2∈{0,...,x2} = J2()⊤ = [20, 14, 11, 8] (ie notation for J2(0) = 20, J2(1) = 14, etc).⇒J1(x1) = min g1(x1, u1) + J2(x1 − u1) 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 g0(x0, u0) + J1(x0 − u0) u0∈{0,...,3} = 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 Definition. A norm � · � on Rn is a mapping from Rn to R that satisfies: 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: 1 The Euclidean Norm (or L2-norm): �x�2 = √x x = • ⊤�in =1 xi 2 2 ; • The L1-norm: �x�1 = in =1 |xi|; 1 • The p-norm (p ≥ 1): �x�p = n |xi|p p (L1 and L2 are p -norms); i=1 • The L∞-norm (or max norm) : �x�∞ = 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: 2a) A is positive definite. b) All eigenvalues of A are > 0. c) x⊤Ax > 0, ∀x ∈ Rn \ {0}. • The following are equivalent: a) A is positive semi-definite. b) All eigenvalues of A are ≥ 0. c) x⊤Ax ≥ 0, ∀x ∈ Rn . Definition. Let f : Rn R. Then, when they exist, →∂f f(x+αei)−f(x) • ∂xi = limα→0 α is the ith partial derivative of f at x.  ∂f ∂x1 f(x) =  ...  is the gradient of f at x.• ▽∂f ∂xn   ∂2f∂2f ∂x2 . . . ∂x1xn1   2f(x) =  ... ... ...  is the hessian of f at x.   • ▽ ∂2f ∂2f . . . ∂xnx1 ∂x2 n 3 How to determin e 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) = 1 x ⊤Qx + b⊤ x are convex if Q is PSD (positive semi-• 2 definite). • Norms are convex functions (the proof is left an exercise, using the properties of norms defined above). • g(x) = �ik =1 aifi(x) is convex if ai ≥ 0, fi convex, ∀i ∈ {1, . . . , k}. Alternatively, if a function is differentiable, we can use the following facts: • ▽ 2f(x) is PSD ∀x = ⇒ f is convex. • ▽ 2f(x) is PD (positive definite) ∀x = ⇒ f is strictly convex. 3� � � � � � Finally, if the function is not differentiable and we cannot use one of the above ap-proaches, we check the definition of convexity: Definition. A function f : Rn R is convex i f ∀x, y ∈ Rn, we have →f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y), ∀λ ∈ [0, 1]. 3.1 Example Let f : Rn R, (x1, x2) �→ x1x22 − x1. So →x f(x) = 22 − 1 ,• ▽2x1x2 2f(x) =0 2x2 .• ▽ 2x2 2x1 To solve for the eigenvalues of the hessian, we get the following quadratic in λ: det � 2 f(x) � = det −λ 2x2 = 0,▽ 2x2 2x1 − λ λ2 − 2x1λ − 4x 22 = 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. 4MIT OpenCourseWarehttp://ocw.mit.edu 15.093J / 6.255J Optimization Methods Fall 2009 For information about citing these materials or our Terms of Use, visit: