Homework 3 Solution

Description

1. (50 pts) In this computer experiment, we will implement the gradient descent method and Newton’s method. Let f (x, y) = − log(1−x−y)−log x−log y with domain D = {(x, y) : x+y < 1, x > 0, y > 0}.

1. 1. Find the gradient and the Hessian of f on paper.

1. 2. Begin with an initial point in w₀ ∈ D with η = 1 and estimate the global minimum of f using the Gradient descent method, which will provide you with points w₁, w₂, . . . ,. Report your initial point w₀ and η of your choice. Draw a graph that shows the trajectory followed by the points at each iteration. Also, plot the energies f (w₀), f (w₁), . . . , achieved by the points at each iteration. Note: During the iterations, your point may “jump” out of D where f is undefined. If that happens, change your initial starting point and/or η.

1. 3. Repeat part (b) using Newton’s method.

1. 4. Compare the speed of convergence of gradient descent and Newton’s method, i.e. how fast does each method approach the estimated global minimum?

2. (50 pts) Perform the following steps:

1. 1. Let x_I = i, i = 1, . . . , 50.

1. 2. Let y_I = i + u_I, i = 1, . . . , 50, where each u_I should be chosen to be an arbitrary real number between −1 and 1.

1. 3. Find the linear least squares fit to (x_I, y_I), i = 1, . . . , 50 analytically using the matrix pseudoin-

verse. Note that the linear least squares fit is the line y = w₀ + w₁x, where w₀ and w₁ should be

chosen to minimize P	50	(yI − (w0	+ w1xI))2.
	I=1

(d) Plot the points (x_I, y_I), i = 1, . . . , 50 together with their linear least squares fit.

50		+ w1xI))2 (derivatives with respect to w0
(e) Find (on paper) the gradient of PI=1	(yI − (w0		and w1).

6. (Re)find the linear least squares fit numerically using the gradient descent algorithm. Compare with (c).

1