Homework 2

Due: Mon, Sept 18th in class.

You can work on this problem set with other students. If you do, write down the names of all who you talked to.

  1. A function f:{\bf R}^n \rightarrow {\bf R} is convex if for any x,y \in {\bf R}^n and any \lambda \in (0,1), the function satisfies f(\lambda x + (1-\lambda) y) \le \lambda f(x) + (1-\lambda) f(y). Show that any local minimum of such a function (smallest in some neighborhood) is also a global minimum.
  2. Give an example where the Newton iteration does not converge.
  3. Show that the function f(x) = \min_{y \in K} \|x-y\|^2 for a convex set K is a convex function.
  4. Give an example where projected gradient descent applied to a convex function and a convex set takes \Omega(1/\epsilon) iterations to reach a point whose function value is within \epsilon of the minimum.
  5. (bonus) Suggest an idea to speed up gradient descent and justify your answer.