Description
P1. (10 points) Express the problems below as linear programs by adding suitable additional
variables.
(A) minx1,x2,x3∈R3 max(2×1 + 3×2 − 5×3, x1, x2, 2×1 − x2 + x3).
(B) minx1,x2,x3∈R3 (|x1 + x2| + |x2 − x3| + |x3 − x1| + |x1 + x2 + x3|).
(C)
min max (|x1|, |x2|, |x3|, |x1 + x2|)
subj.to x1 − x2 ≤ 5
x2 ≤ 3
P2. (15 points) The attached spreadsheet provides values of insulin input u(t) and the blood
glucose levels G(t) for a patient with type-1 diabetes. Our goal is to use an ARMAX model that
predicts the output G(t + 1) as a function of the past glucose and insulin values:
G(t + 1) = a0G(t) + a1G(t − 1) + · · · + a10G(t − 10) + b0u(t) + · · · + b5u(t − 5)
Use linear regression using L1 norm on the given data to learn the arma model coefficients
a0, a1, . . . , b0, . . . , b5. Attach your code to this assignment, write down the coefficients obtained,
and plot the residuals. You are encouraged to use MATLAB or Python to solve this problem.
Please attach all the problem related work in a single place in your assignment (in other words,
arrange your writeup carefully so that we can find all the information in one place).
Hint: First the problem needs to be posed as a regression problem of the form Ax ‘ b. Identify
what A, b and x are for this problem.
P3 (25 points). Consider the linear programming problem below:
max −2×1 −3×2 −x3 −x4 +x6
s.t. x1 −x2 −x6 ≤ 3
x1 −x4 −x5 ≤ −1
−x3 −x6 ≤ −2
−x2 −x3 +x4 +x6 ≤ 4
x1 +x3 +x5 +x6 ≤ 6
−x1 −x4 +x5 −x6 ≤ −2
x1, . . . , x6 ≥ 0
We add slack variables w1, w2, . . . , w6 for the 6 constraints. For your convenience, the problem
data is provided separately for easy cut and paste into your python/matlab/other code.
1
(A) Compute and write out the dictionaries for the following set of basic variables. If no dictionaries
exist, say why.
1. {x1, x2, x3, w1, w2, w3}.
2. {x1, x2, x5, w3, w5, w6}.
3. {x1, x2, x6, w4, w5, w6}.
(B) Perform one step of the revised simplex method for the dictionary with the basis:
{x3, x4, x5, w1, w2, w6}
1. Compute the constant column and objective rows of this dictionary.
2. Choose the entering variable with the largest coefficient.
3. Set up the equations to construct the column for the entering variable.
4. Choose the leaving variable.
5. Write down the basic variables in the next dictionary.
You may use MATLAB or Python to perform the matrix calculations required. You are encouraged to code up this process as this will be important for your programming assignment.
(C) Write down the final dictionary for the problem. First you may want to solve the problem using
your favorite Simplex solver and work out what the basic variables should be from your solution.
(D) We wish to now update the objective function to a new function
(−2×1 − 3×2 − x3 − x4 + x6) + µ(x1 + x2 + x6)
where µ is a parameter. Write down the range of values of µ for which the final dictionary from
part (D) continues to remain final as the objective is changed.
(E) Going back to (C), we wish to update the right hand sides of the original problem to
3
−1
−2
4
6
−2
+ λ
1
1
0
0
0
−1
Calculate the range of values for λ for which, the dictionary in (C) remains feasible.
2