APM462: Midterm Project
Due: Sat July 13 before 11:59pm
Submit your solutions to the homework on Crowdmark.
(1) Let C ⊂ Rn be a nonempty closed convex set and a ∈ Rn a point outside of
C. Suppose x0 ∈ C is the projection of a onto C, that is |x0 − a| ≤ |x− a|
for all x ∈ C. Prove that x0 is unique.
(2) Let D = {(x, y) ∈ R2|x2 + y2 ≤ r} ⊂ R2 and let ∂D denote its boundary.
Let d : D → R be the distance from a point a ∈ D to its boundary:
d(a) = min
x∈∂D
|a− x|.
Prove that d is a concave function on D.
(3) Let C ⊂ Rn be the non negative orthant (C = {(x1, . . . , xn) ∈ Rn|xi ≥
0, i = 1, . . . , n}) and f : Rn → R be convex. Consider the following
problem
minimise f(x)
subject to x ∈ C
and assume that it has a minimiser. Prove that if there exists some y ∈ C
such that there is some v ∈ ∂f(y) with v ∈ intC, then the set of minimisers
to the problem is bounded.
(4) Consider the set C = {(x, y) ∈ R2|x2 + y2 ≤ 1, y ≥ 0, y ≤ x}. Let δC(x, y)
be its indicator function. Let (x0, y0) be a boundary point of C. Find
∂δC(x0, y0).
(5) Consider the following problem:
minimise f(x, y) = (x− 1)2 + (y − 3)2
subject to g(x, y) = |x|+ 2y − 2 ≤ 0
(a) Solve the problem using subdifferentials.
(b) Convert this problem into an equivalent minimisation problem which
you can apply the KKT conditions to. Then use the KKT FONC to
find candidates for minimisers. Do you get the same candidates as in
part a?
(6) Consider the following problem:
minimise f(x, y) = 3x2 − 2y
subject to g(x, y) = |x+ 2|+ |y − 3| − 1 ≤ 0
(a) Find ∂f(x, y) and ∂g(x, y).
1
(b) Solve the problem using subdifferentials.
(7) Consider the following problem:
minimise f(x, y) = max{|x|, y + 2}
subject to g1(x, y) = 2x
2 + y2 − 1 ≤ 0
g2(x, y) = |x| − 2y − 1 ≤ 0
(a) Find ∂f(x, y), ∂g1(x, y), and ∂g2(x, y).
(b) Solve the problem using subdifferentials.
The following 3 problems—the ones indexed by Roman numerals—are
for practice only and are not to be turned in.
I. Let x = (x1, . . . , xn) ∈ Rn. The ℓ∞ norm of a vector is defined as follows:
|x|∞ = max
1≤i≤n
|xi|.
Let f(x) = |x|∞. Find ∂f(0).
II. Let f : Rn → R be convex and C1. Prove that ∂f(x) = {∇f(x)}.
III. On the interval [1, 3], approximate the function x2 by the affine function
ax+ b such that the quantity
sup
x∈[1,3]
|x2 − (ax+ b)|
is minimised.
2

学霸联盟