[SOLVED] Ece490 homework 2 p0

Required reading: Wright and Recht, Ch. 3.
1 Let a continuously differentiable function f : Rn →R and a point x ∈Rn be given, such that ∇f(x) 6= 0.
Prove that the set of all descent directions for f at x is convex.
2 Let f : Rn →R be a differentiable, m-strongly convex function. Prove that
, for all x ∈Rn.
Hint: Use the fact that f satisfies
[∇f(x) −∇f(y)]T(x − y) ≥ mkx − yk2, for all x,y ∈Rn.
3 (Exercise 5 from Wright and Recht, Ch. 3) Suppose that f : Rn → R is m-strongly convex, L-smooth, and has (unique) minimizer x∗. Use the co-coercivity property proved in Homework 1 and the fact that ∇f(x∗) = 0 to prove that the kth iterate of the steepest descent method applied to f with constant steplength satisfies
,
where is the condition number of the problem.
4 (Exercise 7(a-f) from Wright and Recht, Ch. 3) Let A be an N × d matrix with N < d and rank(A) = N [that is, the rows of N are linearly independent]. Consider the least-squares optimization problem
minf(x), where x
where b ∈RN is a given vector.
(a) Assume that there exists a z such that Az = b. Characterize the solution space of the linear system Ax = b.
Hint: Recall the definition of the nullspace (or the kernel) of A, ker(A) := {x ∈Rd : Ax = 0}. (b) Compute the Lipschitz constant of the gradient of f in terms of A.
(c) If you run the steepest descent method on f starting at x0 = 0 with appropriate choice of steplength, how many iterations are required to find a solution with N1kAx − bk2 ≤ ε? (d) Consider the regularized problem
minfµ(x), where x
for some µ > 0. Find the minimizer xµ of fµ in closed form.
1

(e) If you run the steepest descent method on fµ starting at x0 = 0 with appropriate choice of steplength, how many iterations are required to find a solution with fµ(x) − fµ(xµ) ≤ ε?
(f) Suppose xˆ satisfies fµ(xˆ) − fµ(xµ) ≤ ε. Find a tight upper bound on f(xˆ).
2