555 HW4
1 Theoretical Problems
1. Let X ⊂ Rd×Rd be a maximal monotone set. Recall that this means that for any (x1, y1), (x2, y2) ∈ X,
we have
〈x1 − x2, y1 − y2〉 ≥ 0. (1)
(a) Show that the proximal map of X is firmly non-expansive, i.e. that
‖ProxX(x1)− ProxX(x2)‖2 ≤ 〈ProxX(x1)− ProxX(x2), x1 − x2〉. (2)
(b) Show that a firmly non-expansive map is non-expansive (Hint: Use Cauchy-Schwartz).
(c) Show that the composition of two non-expansive maps is non-expansive.
2. Consider the following constrained optimization problem:
min
x1≥0
x2≥0
x1+x2≤2
(x1 − 3)2 + (x2 − 2)2. (3)
(a) Write down the KKT conditions for this problem.
(b) Is this problem convex? Is the Slater condition satisfied? What conclusion can we draw from
this?
(c) Solve the KKT conditions. (Hint: Figure out what the active constraints are first.) Which
constraints are active? Which constraints are slack? Which Lagrange multipliers are slack?
3. Let x0 ∈ Rd and consider the plane {x : Ax = b}, where A has full row rank. We wish to project the
point x0 onto the plane, i.e. to solve the problem
min
Ax=b
1
2
‖x− x0‖2. (4)
(a) Show that this is equivalent to the proximal map Proxχ{Ax=b}(x0) of the characteristic function
χ{Ax=b}(x) =
{
∞ Ax 6= b
0 Ax = b.
(5)
(b) Write down the KKT conditions for this problem. Show that the optimal multiplier for this
problem is
λ∗ =
(
AAT
)−1
(b−Ax0)
and that the solution is given by
x∗ = x0 +AT
(
AAT
)−1
(b−Ax0) .
(c) Consider the special case where the rows of A are orthonormal, what is the projection in this
case?
1
2 Computational Problems
1. The goal of this problem is to numerically solve the optimization problem
min
Ax=b
|x|1, (6)
using the Douglas-Rachford iteration. This optimization problem appears, for instance, in compressed
sensing. In our case, the constraint Ax = b will be a constraint on some Fourier coefficients of x.
(a) Let x∗ be the 512-dimensional vector (1, 0, · · · , 0). Numerically calculate the real Fourier trans-
form of x∗ (this should be a built in function, for instance ‘rfft’ in numpy).
(b) Randomly choose 10% of the Fourier coefficients to form the vector b. We want to solve the
problem
min
Ax=b
|x|1, (7)
where A is the operator which picks out the selected 10% of the Fourier coefficients. In other
words, we want x to match the same Fourier coefficients of x∗ in the selected 10%, and to minimize
|x|1. (Note here that Ax = b is an underdetermined system.)
(c) Write this objective as
min |x|1 + χ{Ax=b}(x), (8)
where χ{Ax=b} is given by
χ{Ax=b}(x) =
{
∞ Ax 6= b
0 Ax = b.
(9)
The proximal map of |x|1 and χ{Ax=b} we calculated in a previous assignment. Implement both
of these proximal maps.
(d) Using the proximal maps for both of these pieces, implement Douglas-Rachford splitting to solve
the problem (6). Compare the solution with the original x∗. Notice that we have recovered x∗
from just 10% of its Fourier transform.
(e) Repeat this experiment with a different x∗. It is important that x∗ is sparse, i.e. has only a few
non-zero entries. Try to see how many non-zero entries you can have while still recovering x∗
from 10% of the Fourier coefficients.
2

欢迎咨询51作业君