IEOR E4007 December 1, 2021 G. Iyengar Homework # 8 1. Active set method for mean-variance portfolio Total points: 40 Consider the following three asset portfolio selection problem max 2 2 1 | {z } μ x x> 243.0 0.5 0.50.5 3.0 0.5 0.5 0.5 3.0 35 | {z } Q x subject to 1 1 1 x = 1 x 0 (a) [5]What would be the sign of the dual variables corresponding to the inequality con- straints x 0 Note that this is a maximization problem. (b) [10]x(0) = 131 is a feasible point for this QP. Construct the equality constrained QP where you only keep the constraints tight at the point x(0). Rewrite the QP in terms of the deviation y = x x(0), and solve for the y and the dual variables corresponding to the tight constraints at x(0). (c) [10]The y that you computed in (b) is not equal to zero, i.e. x(0) is not a critical point of its active set. Compute the step length and the new iterate x(1). (d) [10]Repeat (b) for x(1). If your computations work out right, you will find that y = 0, i.e. x(1) is a critical point for its active set. Show that x(1) is a critical point for the original QP. Is it optimal for the original QP (e) [5]Suppose we were to introduce a risk-free asset in the market and relax the portfolio constraint to 1>x 1. Would the point that you computed in part (d) still remain optimal 2. [10]Utility maximization with multiple scenario Total points: The python notebook MultiScenario.ipynb computes the ecient frontier for the op- timization problem min max1 k m kVkxk2 , s.t. min1 k mμ>k x r, 1>x = 1, |x| B1. whereVk = sqrtm(Qk), Qk denotes the variance-covariance matrix for the k-th scenario, and μk denotes the mean vector for the k-th scenario. The data for this code is in the file multiscenario.mat. The notebook MultiScenario.ipynb reads in this file and converts the data into numpy arrays. 1 Modify this code to solve the following utility maximization problem max min1 k m μ>k x kVkxk2 , s.t. 1>x = 1,Pn i=1 x i 4. 3. [15]Integer knapsack problem Total points: Consider the following integer knapsack problem max P5 i=1 vixi subject to P5 i=1wixi W xi 2 Z+ The data for the problem is as follows n = 5; v = [1,6,18,22,28]’; w = [1,2,5,6,7]’; W = 11; We saw in class that the recursion for this problem is given by Vi(w) = max{Vi1(w), vi + Vi(w wi)} where Vi(w) = Maximum revenue from objects j i and weight budget w In the recursion above, it is optimal to pick up one unit of object i only if vi+Vi(wwi) Vi1(w). We want compute V5(11), and recover the optimal solution. Solve this recursion using python. 1. You will start with V1(w)and work your way up to V5(11). 2. In another array Di(w), keep track of the optimal decision. It is optimal to pick up one unit of object i only if vi + Vi(w wi) Vi1(w). 3. In order to compute the optimal decision, you will work backward from the V5(11). If it is optimal to pick up object 5, you will put it in your bag, and consider the optimal decision at V5(11 w5) = V5(4). Otherwise you will move to V4(11) and look into the optimal solution at that stage. 2 4. [20]Project management Total points: A construction company has four projects in progress. According to the current allo- cation of manpower, equipment, and materials, the four projects can be completed in 15, 20, 18, and 25 weeks. Management wants to reduce the completion times and has decided to allocate an additional $35,000 to all four projects. The new completion times as functions of the additional funds allocated to each projects are given in the table below. Write a code to compute how $35,000 should be allocated among the projects to achieve the largest total reduction in completion times Assume that the additional funds can be allocated only in blocks of $5000. Additional funds (×1000 dollars) Project 1 Project 2 Project 3 Project 4 0 15 20 18 25 5 12 16 15 21 10 9 13 12 18 15 8 11 10 16 20 7 9 9 14 25 6 8 8 12 30 5 7 7 11 35 4 7 6 10 3
