II with constant l >">

Suppose the function f: R" R is strongly convex and twice differentiable, i.e V2 f(x) > II with constant l > 0. Also, its gradient is Lipschitz continuous with constant L> 0, i.e. we have that Vf(x) - Vf(y)| L||x-y|| for any z, y. (5 pt) Prove f(y) f(x) + (Vf(x), y-x)+||-|| (10 pt) Prove f(y) f(x) - Vf(x)||2 (hint: f(y)2 min, f(y)) (15 pt) Then if we run gradient descent for t iterations with step size a = prove it will give a linear convergence rate, i.e. f(x+) - f* (1-1)(f(x) - *) by using exact line search,