Math 110B Name:
Summer Session II 2021
Take-Home Midterm Exam Student ID:
Due Fri 8/27/2021 at 11:59pm in Canvas
? There are 3 questions for a total of 100 points.
? Some questions have several parts.
? For full credit show ALL of your work, explain your process fully. Make sure that I can understand
exactly HOW you got your answer.
? Please box your final answer, when applicable.
Question: 1 2 3 Total
Points: 40 30 30 100
Score:
Page 1 of 4
1. Consider the LP
maximize cTx,
subject to Ax ≤ b, (1)
where c ∈ Rn, b ∈ Rm, and A ∈ Rm×n.
(a) (10 points) Find the dual problem to the above problem.
(b) (10 points) Let b = 0 and suppose the dual problem in (a) has a feasible solution. Then what is
the maximum value for the optimization problem in (1)? Why is that? What is an optimal solution
x? for (1)?
(c) (10 points) Let b > 0 and c 6= 0 (here b > 0 means all entries are positive). If the dual problem
in (a) has optimal feasible solutions, prove (1) has an optimal solution and the optimal objective
value will always be positive.
(d) (10 points) Let b < 0. If the linear equation ATy = 0 with constraint y ≥ 0 only has one solution
y = 0, prove Ax ≤ b must have a solution. Hint: Search for Gordan’s transposition theorem in
chapter 17 of the Chong, Zak text.
Page 2 of 4
2. Consider the following constrained problem. Suppose a1, a2, ..., an are all positive.
maximize a1x1 + a2x2 + · · ·+ anxn,
subject to x21 + x
2
2 + · · ·+ x2n = n.
(2)
(a) (10 points) If a1 = a2 = · · · = an, prove x1 = x2 = · · · = xn = 1 is an optimal solution.
(b) (10 points) If x1 = x2 = · · · = xn = 1 is an optimal solution, show that a1 = a2 = · · · = an.
(c) (10 points) Find the dual problem for the optimization problem at (2).
Page 3 of 4
3. Consider the problem
minimize x21 + x
2
2
subject to x1 + x2 = 3.
x21 ? 4x2 ≤ 0
(3)
(a) (15 points) What is the KKT condition for the above problem (3)?
(b) (15 points) Solve the problem using your KKT condition.
Page 4 of 4