University of Vermont
EE 303: Convex Optimization with Applications
Spring 2021
Take-home Exam 1
March 26-29
Friday (3/26) after 12:01pm until Monday (3/29) until 11:59:00pm
Name:
Write your name clearly above and submit the exam a timely fashion – give yourself time to
succeed in both the work and the submission. Failure to submit in a timely fashion so risks a
penalty of 10 + (N/6)% applied to your final score, where N is the number of minutes late you
submitted your exam (e.g., 18-minute late submission incurs a 13% reduction in your final % score).
For this exam: you may use your class notes, Boyd’s book, any course materials I uploaded, your
Matlab, Julia, or Python setups, any calculator, and any summary sheet you created during your
studies. However, you may not use your classmates, online discussion forums, or other friends,
colleagues, or family members. nor is a calculator allowed.
Your submission should follow the same problem order as the exam.
All final answers should be clearly marked and boxed .
HONORS PLEDGE (sign after exam is completed - either electronic or scanned): I have neither
given nor received aid on this exam, nor have I observed a violation of the UVM Code of Academic
Integrity.
Signature:
(sign after the exam is completed)
Good luck!
Question: 1 2 3 4 5 Total
Points: 15 10 20 12 18 75
Score:
EE 303 Take-home Exam 1 - Page 2 of 9 March 26-29
MULTIPLE-CHOICE QUESTIONS: Circle your answers. No partial credit is awarded.
1. (15 points) Each question is worth 3 pts, unless otherwise noted.
(a) Circle all true statements about cones in some given vector space (e.g., Rn or Sn):
i) The intersection of convex cones is not always convex
ii) The intersection of convex cones is not always a cone
iii) Any conic combination of any set of vectors gives a convex cone
iv) The dual cone of a non-convex cone is always a convex cone
v) The union of convex cones may be convex
vi) For any x0 ∈ Rn, if C is a cone, then C + x0 is a cone,
(b) Circle all true statements regarding sets C and D and separating hyperplanes:
i) If C and D are non-empty, convex, and disjoint sets, then there exists a separating
hyperplane.
ii) If a separating hyperplane exists between convex C and D, then C ∩D = ∅.
iii) If C and D are disjoint, convex, and closed, then they can be strictly separated by
hyperplane.
iv) C and D are convex and disjoint if and only if there exists a separating hyperplane.
(c) Circle all true statements on differentiable f with open and convex domain D:
i) f is concave if and only if every tangent line is a global over-estimator
ii) f is strictly concave if and only if ∇2f(x) < 0 for all x ∈ D
iii) f is quasi-convex if and only if all sub-level sets of f are convex.
iv) f is concave if and only if epif is a concave set
(d) Circle all true statements. Let C ⊂ Rn be a closed, convex set and select K points,
x1, . . . , xK , on the boundary of C (bd C). Define P := conv{x1, . . . , xK}.
i) P ⊂ C
ii) C ⊂ P
iii) minx∈C c>x ≤ minx∈P c>x
iv) minx∈P c>x ≤ minx∈C c>x
(e) Given a function f(x), the conjugate f∗(y) := supx∈domf
(
y>x− f(x)).
Let f(x) = x− log(x). Then,
i) f∗(y) = +1− log(1− y)
ii) f∗(y) = +1− log(1 + y)
iii) f∗(y) = −1− log(1− y)
iv) f∗(y) = −1− log(1 + y)
EE 303 Take-home Exam 1 - Page 3 of 9 March 26-29
PROBLEMSWITH PARTIAL CREDIT: CLEARLY INDICATEWHAT IS YOUR
FINAL ANSWERS! YOU MUST SHOW ALL YOUR WORK!
2. (10 points) Recall that a polyhedron P = {x|Ax ≤ b, Cx = d} and the 2-norm ball B =
{x | ||x||2 ≤ 10} for x ∈ Rn.
i) (4 pts) Explain how the norm ball B may be formulated as a convex hull: conv(.). Provide
example or counter-example.
ii) (4 pts) Explain how the norm ball B may be formulated as a polyhedron. Provide example
or counter-example.
iii) (2 pts) Briefly compare the polyhedral and conv formulations.
EE 303 Take-home Exam 1 - Page 4 of 9 March 26-29
BLANK SHEET
EE 303 Take-home Exam 1 - Page 5 of 9 March 26-29
3. (20 points) Show your work. A correct answer is only worth something if supported
by adequate reasoning. For each statement, state whether it is true or false. Be sure to
justify your answer now and be precise in this justification!
i) (5 pts) The function
f(x) = min
t∈[0,10]
p(t)− max
t∈[0,10]
p(t)
is concave where p(t) = x1 + x2t + x3t
2 + . . . + xnt
n−1.
ii) (5 pts) Function g : Rn → R is convex on domg = {x ∈ Rn| gi(x) > 0}
g(x) =
m∑
i=1
e1/gi(x)
is convex, where gi are convex functions.
EE 303 Take-home Exam 1 - Page 6 of 9 March 26-29
iii) (5 pts) The set S = {[x, y, z]> ∈ R3 |xez/x ≤ y, x > 0} is not a convex set.
iv) (5 pts) Consider a function: f : Rn → R where, for n = 3,
f(x) =
1
x1 − 1x2− 1x3
First, find dom f and then show that over dom f , f is positive, convex, and decreasing.
EE 303 Take-home Exam 1 - Page 7 of 9 March 26-29
4. (12 points) Show your work. A correct answer is only worth something if supported
by adequate reasoning. For each statement, state whether it is true or false. Be sure to
justify your answer now.
i) (4 pts) If an LP has more than one optimal solution and has an optimal solution at a
vertex in the feasible set, then it must have at least two optimal optimal solutions at
vertices points.
ii) (4 pts) If an LP’s feasible set is unbounded, then the optimal solution is also unbounded.
iii) (4 pts) If the feasible set contains a line, then an LP has no bounded optimal solution.
EE 303 Take-home Exam 1 - Page 8 of 9 March 26-29
BLANK SHEET
5. (18 points) Applied problem. You will solve an “apocalyptic” version of the Diet Problem
for this part of the exam and examine how sensitive the optimal solution (food servings) is to
changes in the costs. CVX is sufficient here.
First, go to https://neos-guide.org/content/diet-problem to read about the simplified
Diet Problem. Note that they also apply a limit on how many servings of each food item you
can have. You are allowed to consume partial servings (i.e., do not use integers).
Then, answer the following:
i) (1 pts) What type of optimization problem is this?
ii) (5 pts) Implement the nominal problem in your favorite language and find the optimal
solution in terms of (Corn, 2% Milk, Wheat bread). Check that your answer is the same
as what given on the website.
iii) (3 pts) Now vary the Cost per serving for Corn uniformly in the range [0.14, 0.22] (e.g.,
use 20 uniformly spaced values) and for each cost value, solve the Diet problem. Then,
plot Corn’s costs vs. the optimal number of servings for each food item (i.e., one plot with
3 lines). Add one sentence to interpret the plot.
iv) (3 pts) Now vary the Cost per serving for Milk uniformly in the range [0.18, 0.28] (e.g.,
use 20 uniformly spaced values) and for each cost value, solve the Diet problem. Then,
plot Milk’s costs vs. the optimal number of servings for each food item (i.e., one plot with
3 lines). Add one sentence to interpret the plot.
v) (3 pts) Now vary the Cost per serving for Wheat bread uniformly in the range [0.04, 0.06]
(e.g., use 20 uniformly spaced values) and for each cost value, solve the Diet problem.
Then, plot Wheat bread’s costs vs. the optimal number of servings for each food item
(i.e., one plot with 3 lines). Add one sentence to interpret the plot.
vi) (3 pts) What can you conclude about the diet’s price sensitivity? Are there other ways to
test this sensitivity?
EE 303 Take-home Exam 1 - Page 9 of 9 March 26-29
BLANK SHEET

欢迎咨询51作业君