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.

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.
Give an example where the Newton iteration does not converge.
Show that the function $f(x) = \min_{y \in K} \|x-y\|^2$ for a convex set $K$ is a convex function.
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.
(bonus) Suggest an idea to speed up gradient descent and justify your answer.