CO250: Introduction to Optimization
Assignment 9
Fall 2022
Due: Mon Nov 28, 2022, midnight
Instructions
• Collaboration on this assignment is not allowed, but you can ask for clarification on Piazza
or during office hours.
• Justify all your answers, unless stated otherwise.
Problems
Question 1. [15 marks]
(a) Prove that, if f, g : Rn → R are convex functions and t ≥ 0, then the function h(x) =
f(x) + tg(x) is convex.
(b) For which triples (a, b, c) of real numbers is the function f(x) = ax2 + bx + c convex? Prove
your answer without using any calculus.
(c) For which integers n ≥ 1 is the function f(x) = xn convex? You may use the fact that a
function f : R→ R such that f ′′(x) ≥ 0 for all x is convex, but not the converse of this fact.
(d) Is it true that the product of two convex functions f, g : R → R is always convex? Prove or
give a counterexample.
(e) Bonus: Give an example of a function f : R→ R such that f(12x1 + 12x2) ≤ 12f(x1) + 12f(x2)
for all x1, x2 ∈ R, but f is not convex. (Hint : this is a very very weird function. The fact
that R is a vector space over Q is relevant to its construction.).
Question 2. [10 marks] Let f : Rn → R be a convex function. In this question, we want to
prove that if M ∈ R and f(x) ≤M for all x, then f is a constant function.
(a) Prove that f(x¯+ t(y¯ − x¯)) ≥ f(x¯) + t(f(y¯)− f(x¯)) for all x¯, y¯ ∈ Rn and t ≥ 1.
(b) Suppose that f(x) ≤M for all x ∈ Rn, but f is not constant. Then there exist a, b ∈ Rn with
f(a) < f(b). Use this fact, together with part (a), to find some c with f(c) > M , giving a
contradiction.
Question 3. [15 marks]
(a) Let f, g1, . . . , gm be convex functions from Rn → R. Prove that the set of optimal solutions to
the NLP {min f(x) : g1(x) ≤ 0, g2(x) ≤ 0, . . . , gm(x) ≤ 0} is a convex set.
(b) Let f : Rn → R be a convex function. Prove that, if λ1, λ2, . . . , λk satisfy
∑k
i=1 λi = 1 and
λi ≥ 0 for all i, then
f
(
k∑
i=1
λixi
)
≤
k∑
i=1
λif(xi).
(c) Let f, g : Rn → R be convex functions with epigraphs epi(f) and epi(g). Find a function
h : Rn → R for which epi(h) = epi(f) ∩ epi(g), and prove your answer.
1
CO250: Introduction to Optimization
Assignment 9
Fall 2022
Due: Mon Nov 28, 2022, midnight
(d) Recall from class that, if f : Rn → R is a convex function, then for all β ∈ R, the level set
{x ∈ Rn : f(x) ≤ β} is a convex set. Prove that the converse of this implication is false.