Optimization Methods MIT 2.098/6.255/15.093 Final exam Date Given: December 19th, 2006 P1. [30 pts] Classify the following statements as true or false. All answers must be well-justified, either through a short explanation, or a counterexample. Unless stated otherwise, all LP problems are in s tandard form. (a) If there is a unique primal optimal solution to a linear programming problem, then the reduced costs of all the nonbasic variables are strictly positive. (b) For a network flow problem with capacity constraints, there always exists an optimal solution that is tree-s tructured. (c) When minimizing a convex function over a convex set, the optimal solution is always on the boundary of the set. (d) For a convex optimization problem with constraints, if a feasible point satisfies the KKT conditions then it is a global optimum. (e) For a nonlinear optimization problem, if Newton’s method converges, then it converges to a local minimum. (f) (g) For an LP in standard form, if c ≥ 0 then the primal is either bounded or infeasible. On very degenerate LP problems, the simplex method p erforms better than interior point methods. (h) The primal iterates xk generated by the affine scaling algorithm are always in the interior of the primal feasible set. (i) The feasible set of a s em idefinite programming problem is always convex. (j) For a quadratic function f(x) = xT Ax + bT x + c, the convergence rate of Newton’s method depends on the condition number of the matrix A. Solution: (a) FALSE. This is true only if the unique optimal solution is nondegenerate. (b) FALSE. In the capacitated case, optimal solutions do not necessarily have to be trees, a simple counterexample is a network with nodes {A, B, C, D} and edges A − B, A − C, B − D, C − D of unit capacity. (c) FALSE. Solutions can be in the interior. As an example, consider minimizing x2 on [−1, 1]. (d) TRUE. This is proven in the book and in the lecture notes. (e) FALSE. Newton’s m ethod can converge to global maxima. (f) TRUE. If c is nonnegative, then if the problem is feasible we have cT x ≥ 0, and thus is it bounded. (g) FALSE. For degenerate problems, interior point methods are a much better choice. (h) TRUE. By construction, the primal iterates in the affine scaling method (with β < 1) are always strictly feasible. (i) TRUE. The feas ible set of an SDP problem is convex, since it is the intersection of two convex sets (an affine subspace and the cone of PSD matrices). (j) FALSE. For quadratic functions, Newton’s method converges exactly in one iteration. 1P2. [25 pts] You are planning on having access to a car for the next N years, where N is a fixed number. The price of a new car is P dollars. For reliability reasons, you will only own relatively new cars, at most m years old. The yearly cost of repairing and maintaining a car during its kth year is rk, and it satisfies r1 < r2 < < rm (i.e., it increases over time). At · · · the end of any given year, you have the option of exchanging your k-year old car for a new one, with the corresponding trade-in value tk of your old car satisfying t1 > t2 > > tm· · · (i.e., depreciating over time). You want to find the most economical sequence of buys and trade-ins, i.e., want to minimize the total cost ove r the N -year perio d. This includes all the money spent, either in buying or repairing (notice that you can sell your car at the end of the N years). (a) Propose a shortest path (or network flow) formulation for this problem. (b) Propose a dynamic programming formulation for this problem. Express clearly what are the state and decision variables, and the corresponding iteration. (c) Use your DP formulation to solve the problem for the following data: N = 5, m = 3, P = 20000, the repairing costs r1 = 1200, r2 = 1600, r3 = 2400, and the trade-in values t1 = 16000, t2 = 12000, t3 = 10000. What is the optimal sequence of actions? Is it unique? Solution: (a) Define a network whose nodes are on a N ×m grid with two additional nodes: a source node s and a sink node t. A node on the gride is indexed by (time index) t = 1, . . . , N and (car age) a = 1, . . . , m. From node (t, a), there is a directed edge • to node (t + 1, a + 1) with cost ra if t < N and a < m (car is maintained for one year) • to node (t + 1, 1) with cost P − tk + r1 if t < N (car is traded in) • to a sink node t if t = N with cost −ta. Node s is connected to the grid node (1, 1) with cost P + r1. Node s a supply of 1 and node t a demand of 1. A min-cost flow solution will correspond to an optimal purchase/maintenance plan for the car over the time horizon N (b) Let the time index t run from 1 to N . Define the state a at time t as the age of the car at the end of the current period. Let Vt(a) be the expected cost given that the car is a-year old at the end of the time period t. At time t < N, if a = m, the car has to be exchanged and maintained for one year with cost P − tm + r1, whereas there are two available options in state a ∈ {1, . . . , m − 1}: • maintain the car, with a cost of ra, leading to (a + 1)-year old car at the next perio d • trade-in the car for a new one and maintain it for a year, with a cost P − ta + r1, leading to a one-year old car in the next period. At time t = N, the car is sold for its value ta. Bellman’s equations for this problem are VN (a) = −ta, a = 1, . . . , m, Vt(m) = P − tm + r1 + Vt+1(1), t < N Vt(a) = min (ra + Vt+1(a + 1), P − ta + r1 + Vt+1(1)) , a = 1, . . . , m − 1, t < N. 2(c) Solving Bellman’s recursion yields the optimal cost of $26, 500. 3� � � P3. [20 pts] Consider the following transshipment problem: The supply nodes are A, B, the demand nodes are D, E, and the transshipment node is node C. There are four unknowns a, b, c and d. The supply/demand amounts in the different nodes are: A : a, B : 400, D : −b, E : −200, where as usual a positive amount indicates supply and a negative amount indicates demand. We are interested in finding an optimal (minimum cost) transshipment …