MSBD5007 Optimization and Matrix Computation Homework 4
Due date: 27 November, Friday, 3pm.
1. Find explicit formulas for the projection of y ∈ Rn onto the following non-empty, closed, and convex sets S ⊂ Rn respectively.
(a) A hyperplane
forsomea∈Rn andb∈R.
(b) The unit 2-norm ball
S={x∈Rn |⟨a,x⟩=b} S={x∈Rn |∥x∥2 ≤1}.
(c) The unit ∞-norm ball
2. We are going to find the projection of y ∈ Rn onto the unit 1-norm ball by considering
(a) Prove the dual problem is
x2
max d(λ), λ≥0
S={x∈Rn |∥x∥∞ ≤1}. min 1∥x − y∥2, s.t. ∥x∥1 ≤ 1.
n
d(λ) = hλ(yi) − λ,
i=1
where hλ : R → R is the so-called Huber’s function (which is a smooth function consisting of a
quadratic and two linear pieces) defined by
hλ(t) =
(b) Prove the strong duality holds.
(c) Find λ∗ that solves the dual problem.
λ|t|−1λ2, if|t|≥λ, 2
1t2, 2
if |t| ≤ λ.
(d) Give an expression of the projection in terms of λ∗. 3. Consider the following optimization
min ∥Ax − b∥1 + λ∥Bx∥1, (1) x∈Rn
where b ∈ Rm, A ∈ Rm×n, and B ∈ Rp×n are given. The optimization problem arises frequently in image processing: the first term is to fit the linear model Ax ≈ b under an implulsive noise, and the second term is to enforce x sparse in the B-transformed domain. We can first convert it to a constrained optimization
min∥y−b∥2 +λ∥z∥1, s.t. Ax=y, Bx=z. x,y,z
Derive the ADMM method for solving it with explicit formulas for each step.
1