MIT 2 098J 6 255J 15 093J Optimization Methods Fall 2009 Problem Set 7 Due Lec 20 in class Note Problem 1 is worth signi cant credit in this HW 1 TSP Performance of Di erent Algorithms BT Exercise 11 17 Submit a hardcopy of your code 2 Dynamic Programming Exercise Consider the matrix multiplication problem we saw in Lecture 16 We want to nd an optimal sequence of multiplications for computing M1 M2 M3 M4 Suppose the dimensions of the four matrices are 5 4 4 6 6 2 and 2 7 Use the DP recursion in the lecture to compute the optimal sequence of multiplications Show all the steps 3 Di raction Law in Optics Let p and q be two points on the plane that lie on opposite sides of a horizontal axis Assume that the speed of light from p and from q to the horizontal axis is v and w respectively and that light reaches a point from other points along paths of minimum travel time Formulate a non linear optimization problem to nd the path that a ray of light would follow from p to q 4 Characterizing Convex Concave Functions Which of the following functions is convex concave strictly convex strictly concave or none of the above Why 2 1 f x1 x21 ex1 2 f x1 x2 2x21 4x1 x2 10x1 5x2 3 f x1 x2 x1 e x1 x2 4 f x1 x2 x3 x21 3x22 2x23 4x1 x2 2x1 x3 4x2 x3 1 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 1
View Full Document