Homework: Numerical Algorithms

%matplotlib inline

import numpy as np
import matplotlib.pyplot as plt

Exiercise 1

Simpsons rule is given by the follwoing approximation

Simpsons

• Write Simpsons rule as a function simpsons(f, a, b, n=100) where n is the number of equally spaced intervals from a to b. (20 points)
• Use this function to estimate the probability mass of the standard normal distribution between -1 and 1. (10 points)

Exercise 2

• Implement a gradient descent algorithm to find the minimum of a function. The gradient descent algorithm starts with some given starting point \(x_0\), then updates

\[x_{k+1} = x_k - \alpha \nabla f(x_k)\]

where \(\nabla f_{x_k}\) is the gradient of \(f\) ad \(x_{k}\) and \(\alpha\) is a parameter known as the learning rate. Write a function gd1(x0, f, fprime, alpha=0.0002, tol=1e-6, max_iter=10000) that stops when the norm of the step \(x_{k+1} - x_k\) less than tol or the number of iterations exceeds max_iter. The function should return the value of \(x_k\) in a list or array. (30 points)

Given

def f(x):
    """Funciton to minimize."""
    return (1 - x[0])**2 + 100*(x[1] - x[0]**2)**2

• Use the gd1 function to find the minimum value of the function f given starting at \(x_0 = (4,-4)\) (5 points)
• Make a contour plot of the function and plot the path taken by \(x_k\) on the plot. (15 points)

There have been many attempts to improve gradient descent, which is widely used in machine learning. One idea is to add momentum \(\nu\) to the update step

\[\nu_{k+1} = \gamma \nu{k} + \alpha \nabla f(x_k - \gamma \nu_k)\]

\[x_{k+1} = x_{k} - \nu_{k+1}\]

• Implement gd2(x0, f, fprime, alpha=0.001, gamma=0.9, tol=1e-6, max_iter=10000) with the momentum update. (15 points)
• Compare the end-point reached by gd1 and gd2 for the function f starting at \(x_0 = (4,-4)\). Which is closer to the true minimum (i.e. the function value at \(x\) is close to the true minimum). (5 points)

This function has a minimum value of 0 at the point (1,1).