Assigned Mon Mar 7, due Tue Mar 22

In class we derived a lower bound for the complexity of gradient methods on strongly convex functions; see the last 5 pages of my notes which are taken from p. 66-68 of Nesterov's book. Nesterov then derives several methods that attain this bound. However, the derivation is very complicated. So, all we did in class was to present the simplest one given on the last page of my notes (see also (2.2.11), p.81 of his book). This assignment simply asks you to program this optimal method and compare the results with the ordinary gradient method, using two different choices of

- the quadratic defined by the Hilbert matrix that you used in HW4 using the same starting point (the vector of all ones) as in HW4
- the example of Exercise 9.30 (BV page 519) that you used in HW4, using the same starting point (zero) as in HW4
- Nesterov's worst case example mentioned above, with the given
starting point (zero) and with the order of the tridiagonal matrix truncated to
**n=10,000**, with**m=1**and two values for**M**: M=100 and M=10,000. (Recall Nesterov uses μ and L for m and M.) Be sure to code the tridiagonal matrix as a**sparse**matrix (type**help sparse**in Matlab) so that matrix-vector multiplies with the tridiagonal matrix are efficient.