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作业君