MIT, 2.098J/6.255J/15.093J Optimization Methods, Fall 2009 Problem Set #7 Due: Lec #20 (in class) Note: Problem 1 is worth significant credit in this HW. 1. (TSP - Performance of Different 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 find 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. (Diffraction 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 find 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? 1. f (x1) = x12 + ex 21 2. f (x1, x2) = 2x12 + 4x1x2 − 10x1 + 5x2 3. f (x1, x2) = x1e−(x1+x2) 4. f (x1, x2, x3) = −x12 − 3x22 − 2x32 + 4x1x2 + 2x1x3 + 4x2x3 1MIT OpenCourseWarehttp://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.
View Full Document
Unlocking...