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 justi ed either through a short explanation or a counterexample Unless stated otherwise all LP problems are in standard 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 ow problem with capacity constraints there always exists an optimal solution that is tree structured 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 satis es 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 For an LP in standard form if c 0 then the primal is either bounded or infeasible g On very degenerate LP problems the simplex method performs better than interior point methods h The primal iterates xk generated by the a ne scaling algorithm are always in the interior of the primal feasible set i The feasible set of a semide nite 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 method 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 a ne scaling method with 1 are always strictly feasible i TRUE The feasible set of an SDP problem is convex since it is the intersection of two convex sets an a ne subspace and the cone of PSD matrices j FALSE For quadratic functions Newton s method converges exactly in one iteration 1 P2 25 pts You are planning on having access to a car for the next N years where N is a xed 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 satis es 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 nd the most economical sequence of buys and trade ins i e want to minimize the total cost over the N year period 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 ow 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 t1 16000 t2 12000 t3 10000 and the trade in values What is the optimal sequence of actions Is it unique Solution a De ne 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 ow 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 De ne 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 period 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 Vt m P tm r1 Vt 1 1 Vt a min ra Vt 1 a 1 P ta r1 Vt 1 1 2 a 1 m t N a 1 m 1 t N 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 di erent 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 nding an optimal minimum cost transshipment plan a State conditions on a b c d such that the above problem is feasible b Consider the spanning tree given by the edges A D B C C D C E State conditions on a b c d for which the spanning tree solution will be feasible c State conditions on a b c d for which the spanning tree solution …