[SOLVED] Ece490 homework 6 p0

Required reading: Wright and Recht, Ch. 9 and 10.
1 (Exercise 4 in Wright and Recht, Ch. 9) Let f be m-strongly convex and L-smooth. Define the function
.
(a) Prove that fm is convex with (L − m)-Lipschitz gradients.
(b) Write down the proximal-gradient algorithm for the function

where we take fm to be the “smooth” part and to be the “convex but possibly nonsmooth” part.
(c) Does there exist a steplength α such that this proximal-gradient algorithm has the same iterates as gradient descent applied to f for some (possibly different) constant steplength? Explain.
(d) Find a steplength for the proximal-gradient method such that

where x∗ is the unique minimizer of f.
2 (Exercise 1 in Wright and Recht, Ch. 10) Consider minimization of a smooth function f : Rn →R over the polyhedral set defined by a combination of linear equalities and inequalities as follows:
{x ∈Rn : Ex = g,Cx ≥ d}
where E ∈Rm×n, g ∈Rm, C ∈Rp×n, and d ∈Rp, and where Cx ≥ d means that each coordinate of the vector Cx − d ∈Rp is nonnegative.
Show that the first-order necessary condition for x∗ to be a solution of this problem is that there exist vectors λ ∈Rm and µ ∈Rp, such that
∇f(x∗) − ET λ − CT µ = 0, Ex∗ = g, 0 ≤ µ ⊥ Cx∗− d ≥ 0
where 0 ≤ u ⊥ v ≥ 0 for two vectors u,v ∈Rp indicates that, for all i = 1,2,…,p, we have ui ≥ 0, vi ≥ 0, and uivi = 0.
Hint: Introduce slack variables s ∈Rp and reformulate the problem to the equivalent problem
min f(x) x∈Rn,s∈Rp subject to Ex = g, Cx − s = d, s ≥ 0.
Now define X, A, and b appropriately and use Theorem 10.5 to find the optimality conditions for this reformulation, then eliminate s.
1