APM462 Midterm Project1
Due: Sat Mar 9 (before 9pm) on Crowdmark
(1) Let f : Rn → R be a C1 convex function. Show that ∂f(x0) =
{∇f(x0)}. Hint: take v ∈ ∂f(x0), so that f(x) ≥ f(x0)+vT (x−x0)
all x, and show that v must equal ∇f(x0). One way to do this is to
fix a direction w ∈ Rn and take x = x0 + sw, so that f(x0 + sw) ≥
f(x0) + v
T (sw) all s. Now combine the last inequality with the 1st
order Taylor approximation f(x0+sw) = f(x0)+s∇f(x0)Tw+o(s)
and let s go to zero.
(2) Conside the convex set C := {(x, y) ∈ R2 | (x−1)2+y2 ≤ 2 and x ≥
0}, and let δC(x, y) be its indicator function. Find ∂δC(x0, y0)
where (x0, y0) is a boundary point of C. Hint: Draw a picture.
There should be 4 cases to consider. Note that C = C1 ∩ C2 where
C1 = {(x, y) ∈ R2 | (x−1)2+y2 ≤ 2} and C2 = {(x, y) ∈ R2 | x ≥ 0}.
(3) Let F (x, y) = f(x) + g(y) where f, g : R1 → R. You can assume all
functions here are subdifferentiable and convex.
(a) Prove that ∂F (x0, y0) = ∂f(x0)×∂g(y0). Recall that the prod-
uct of two sets A×B = {(a, b) | a ∈ A, b ∈ B}.
(b) Use the formula in part (a) to compute ∂F (x0, y0) for the func-
tion F (x, y) = |x2 − 3|+ |y|.
(4) Consider the following problem:
minimize: f(x, y)
subject to: g(x, y) = ex − y ≤ 0,
where f(x, y) = max{|x− 2|, |y − 3|}.
(a) Compute ∂f(x0, y0) and ∂g(x0, y0).
(b) Usesubdifferentials to descrive the minimizer (x0, y0).
(5) Consider the following optimization problem in R2:
minimize: f(x) = |aTx|+ |bTx|
subject to: g(x) = |x− x0|2 − r2 ≤ 0.
Here a and b are two linearly independent vectors in R2. Note that
the sets La := {x ∈ R2 | aTx = 0} and Lb := {x ∈ R2 | bTx = 0} are
two lines through the origin. You can assume the the disc g(x) ≤ 0
does not intersect either of these lines (so it is contained “between
the lines”).
1Copyright ©2024 J. Korman. Sharing or selling this material without permission of
author is a copyright violation.
1
2(a) Show that the function f(x) = |aTx| is a convex function on R2
and calculate its subdifferential ∂f(x). Hint |aTx| = max{aTx,−aTx}.
(b) Use subdifferentials to solve the optimization problem above.
Hint: it may be convenient to note that the problem does not
change if we use −a instead of a or −b instead of b.
Discussion: This problem can be, more or less, interpreted as hav-
ing a circular lake situated between two straight roads. Where on
the edge of the lake, should a house be built, in order to minimize
the sum of the distances from the house to the two roads?
(6) Consider the optimization problem:
min f(x, y) = (x− 2)2 + (y − 3)2
subject to: g(x, y) = |x|+ |y| ≤ 1
Note that {g ≤ 1} is a rhombus with centre at the origin.
(a) Solve this problem using subdifferentials. Hint: after you draw
a picture the solution should be pretty clear. Once you know
what the solution should be, you will know what to aim for.
(b) Use the 1st order Kuhn-Tucker neccessary conditions for a local
min to find the candidate(s) for minimizer(s) and then solve
the optimization problem. Hint: you should first replace the
constraint g ≤ 1 with four other constraints so as to get rid of
the absolute values.
(7) Let A,B,C ∈ R2 be three distinct points in the plane that form an
acute triangle. Let f(x) := max{f1(x), f2(x), f3(x)} where f1(x) =
|x−A|2, f2(x) := |x−B|2, f3(x) := |x−C|2 are the distances squared
from x to the three points. Consider the following unconstrained
3minimization problem:
minimize: f(x)
x ∈ R2
(a) Show that f(x) is a convex function and compute its subdiffer-
ential ∂f(x). Hint: consider several cases depending on which
of the functions fi equals f at x. For example, one case is
{x ∈ R2 | f1(x) > f2(x), f3(x)}.
(b) Use subdifferentials to find the minimizer. Hint: use the fact
that the triangle ABC is acute to argue that 0 ∈ ∂f(x) iff
f1(x) = f2(x) = f3(x). You do not need to find a formula for x
but show that there is only one x s.t. f1(x) = f2(x) = f3(x).
Discussion: This problem can be interpreted as having three towns
A,B and C. Where should a fire station be built in order minimize
its distance to the furthest town ?