{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework: Numerical Algorithms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exiercise 1** \n",
    "\n",
    "Simpsons rule is given by the follwoing approximation\n",
    "\n",
    "![Simpsons](https://wikimedia.org/api/rest_v1/media/math/render/svg/a0cdf0804bb8810e4438cbea898dc7a2fedb3e57)\n",
    "\n",
    "- 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)\n",
    "- Use this function to estimate the probability mass of the standard normal distribution between -1 and 1. (10 points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 2**\n",
    "\n",
    "- 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 \n",
    "\n",
    "$$\n",
    "x_{k+1} = x_k - \\alpha \\nabla f(x_k)\n",
    "$$\n",
    "\n",
    "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)\n",
    "\n",
    "Given\n",
    "```python\n",
    "def f(x):\n",
    "    \"\"\"Funciton to minimize.\"\"\"\n",
    "    return (1 - x[0])**2 + 100*(x[1] - x[0]**2)**2\n",
    "```\n",
    "\n",
    "- Use the `gd1` function to find the minimum value of the function `f` given starting at $x_0 = (4,-4)$ (5 points)\n",
    "- Make a contour plot of the function and plot the path taken by $x_k$ on the plot. (15 points)\n",
    "\n",
    "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\n",
    "\n",
    "$$\\nu_{k+1} = \\gamma \\nu{k} + \\alpha \\nabla f(x_k - \\gamma \\nu_k) \n",
    "$$ \n",
    "\n",
    "$$\n",
    "x_{k+1} = x_{k} - \\nu_{k+1}\n",
    "$$\n",
    "\n",
    "- Implement `gd2(x0, f, fprime, alpha=0.001, gamma=0.9, tol=1e-6, max_iter=10000)` with the momentum update. (15 points)\n",
    "- 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)\n",
    "\n",
    "This function has a minimum value of 0 at the point (1,1)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}