In this homework, we will investigate various optimization algorithms discussed in the class.
1. Consider the cost function
J(w) = (w wo)T A(w wo);
where w 2 R2, wo = ( 2; 2)T and A = I (the identity matrix).
a) Make a contour plot showing the iso-contours of J(w) and a surface plot of the function.
b) Compute the expression of the gradient of J(w) and make a quiver plot of the gradient.
c) Write down the expression for the parameter updates under the gradient descent algorithm. Using as initialization the vector w(0) = (5; 15)T and a step size = 0:09, run the gradient descent algorithm until
jjw(n) wojj2 < 0:001:
Plot the values of w(n) obtained after each iteration on the contour plot of J(w). How many iterations were required for convergence?
d) Repeat c) for step sizes = 5 and found by a line search. Comment on the ability to converge and convergence speed of the di erent algorithms. How do you explain the di erent behaviors?
e) Write down the expression for the parameter updates under Newton’s method. This is of the form
w(n+1) = w(n) + F (w(n)):
Make a quiver plot of the function F (w). Comment on the di erences between this plot and that of b).
f) Using as initialization the vector w(0) = (5; 15)T , run Newton’s method until
jjw(n) wojj2 < 0:001:
Plot the values of w(n) obtained after each iteration on the contour plot of J(w). How many iterations were required for convergence?
g) Comment on the ability to converge and convergence speed of the algorithm as compared with the algorithms of c) and d). How do you explain the di erent behaviors?
2. Repeat Problem 1. with A = diag(2; 1). Compare your answers to all questions to those obtained in Problem 1. and discuss any di erences.
1
3. Repeat Problem 1. with A = diag(20; 1). Compare your answers to all questions to those obtained in Problems 1. and 2. and discuss any di erences.
4. It is known that the contours of J(w) are ellipses whose principal directions have angle =4 and =4 with the horizontal axis. The eigenvalues of A are 1 = 2 and 2 = 1. What is the matrix A?
Repeat Problem 1. for this A. Compare your answers to all questions to those obtained in Problems 1., 2., and 3. and discuss any di erences.
5. Repeat Problem 4. for 1 = 20 and 2 = 1.
2
