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>
2
4
3.0 0.5 0.5
0.5 3.0 0.5
0.5 0.5 3.0
3
5
| {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) = 1
3
1 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: 10
The python notebook MultiScenario.ipynb computes the e�cient frontier for the op-
timization problem
min max1km kVkxk2 ,
s.t. min1km µ
>
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 min1km
�
µ>k x� � kVkxk2
,
s.t. 1
>
x = 1,Pn
i=1 x
�
i 4.
3. [15]Integer knapsack problem Total points: 15
Consider the following integer knapsack problem
max
P5
i=1 vixi
subject to
P5
i=1 wixi 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{Vi�1(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(w�wi) �
Vi�1(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) � Vi�1(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: 20
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