{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CSC338. Homework 9\n",
    "\n",
    "Due Date: Wednesday March 25, 9pm\n",
    "\n",
    "Please see the guidelines at https://www.cs.toronto.edu/~lczhang/338/homework.html\n",
    "\n",
    "### What to Hand In\n",
    "\n",
    "Please hand in 2 files:\n",
    "\n",
    "- Python File containing all your code, named `hw9.py`.\n",
    "- PDF file named `hw9_written.pdf` containing your solutions to the written parts of the assignment. Your solution can be hand-written, but must be legible. Graders may deduct marks for illegible or poorly presented solutions.\n",
    "\n",
    "If you are using Jupyter Notebook to complete the work, your notebook can be exported as a .py file (File -> Download As -> Python). Your code will be auto-graded using Python 3.6, so please make sure that your code runs. There will be a 20% penalty if you need a remark due to small issues that renders your code untestable.\n",
    "\n",
    "**Make sure to remove or comment out all matplotlib or other expensive code before submitting your homework!**\n",
    "\n",
    "Submit the assignment on **MarkUs** by 9pm on the due date. See the syllabus for the course policy regarding late assignments. All assignments must be done individually."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 1. Golden Section Search\n",
    "\n",
    "### Part (a) -- 6 pt\n",
    "\n",
    "Write a function `golden_section_search` that uses the Golden Section search\n",
    "to find a minima of a function `f` on the interval `[a, b]`. You may assume\n",
    "that the function `f` is unimodal on `[a, b]`.\n",
    "\n",
    "The function should evaluate `f` only as many times as necessary. There will\n",
    "be a penalty for calling `f` more times than necessary.\n",
    "\n",
    "Refer to algo 6.1 in the textbook, or\n",
    "slide 19 of the posted slides accompanying the textbook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def golden_section_search(f, a, b, n=10):\n",
    "    \"\"\" Return the Golden Section search intervals generated in \n",
    "    an attempt to find a minima of a function `f` on the interval\n",
    "    `[a, b]`. The returned list should have length `n+1`.\n",
    "   \n",
    "    Do not evaluate the function `f` more times than necessary.\n",
    "    \n",
    "    Example: (as always, these are for illustrative purposes only)\n",
    "\n",
    "    >>> golden_section_search(lambda x: x**2 + 2*x + 3, -2, 2, n=5)\n",
    "    [(-2, 2),\n",
    "     (-2, 0.4721359549995796),\n",
    "     (-2, -0.4721359549995796),\n",
    "     (-1.4164078649987384, -0.4721359549995796),\n",
    "     (-1.4164078649987384, -0.8328157299974766),\n",
    "     (-1.1934955049953735, -0.8328157299974766)]\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part (b) -- 2 pt\n",
    "\n",
    "Consider the following functions, both of which are unimodal on `[0, 2]`\n",
    "\n",
    "$f_1 (x) = 2 x^2 - 2x + 3$\n",
    "\n",
    "$f_2 (x) = - x e^{-x^2}$\n",
    "\n",
    "Run the golden section search on the two functions for $n=10$ iterations.\n",
    "\n",
    "Save the returned lists in the variables `golden_f1` and `golden_f2`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "golden_f1 = None\n",
    "golden_f2 = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 2. Newton's Method in One Dimension\n",
    "\n",
    "\n",
    "### Part (a) -- 6 pt\n",
    "\n",
    "Implement Newton's Method to find a minima of a real function\n",
    "in one dimension."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def newton_1d(f, df, ddf, x, n=10):\n",
    "    \"\"\" Return the list of iterates computed when using \n",
    "    Newton's Method to find a local minimum of a function `f`,\n",
    "    starting from the point `x`. The parameter `df` is the \n",
    "    derivative of `f`. The parameter `ddf` is the second \n",
    "    derivative of `f`. The length of the returned list \n",
    "    should be `n+1`.\n",
    "    \n",
    "    Example: (as always, these are for illustrative purposes only)\n",
    "    \n",
    "    >>> newton_1d(lambda x: x**3, \n",
    "    ...           lambda x: 3 * (x**2),\n",
    "    ...           lambda x: 6 * x, \n",
    "    ...           x=1.0, n=5)\n",
    "    [1, 0.5, 0.25, 0.125, 0.0625, 0.03125]\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part (b) -- 4 pt\n",
    "\n",
    "Consider `f1` and `f2` from Question 1 Part (b). \n",
    "\n",
    "Complete the functions `df1`, `df2` which compute the derivatives of `f1` and `f2`.\n",
    "\n",
    "Complete the functions `ddf1`, `ddf2` which compute the second derivatives of `f1` and `f2`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def df1(x):\n",
    "    return None\n",
    "def ddf1(x):\n",
    "    return None\n",
    "\n",
    "def df2(x):\n",
    "    return None\n",
    "def ddf2(x):\n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part (c) -- 2 pt\n",
    "\n",
    "Run Newton's Method on the two functions $f_1$ and $f_2$ for $n=30$ iterations,\n",
    "starting at $x = 1$.\n",
    "\n",
    "Save the returned lists in the variables `newton_f1` and `newton_f2`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "newton_f1 = None\n",
    "newton_f2 = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 3.\n",
    "\n",
    "Consider the function \n",
    "\n",
    "$$f(x_0, x_1) = 2x_0 ^4 + 3 x_1^4 - x_0^2 x_1^2 - x_0^2 - 4 x_1^2 + 7 $$\n",
    "\n",
    "### Part (a) -- 2 pt\n",
    "\n",
    "Derive the gradient. Include your solution in your PDF writeup.\n",
    "\n",
    "### Part (b) -- 2 pt\n",
    "\n",
    "Derive the Hessian. Include your solution in your PDF writeup.\n",
    "\n",
    "### Part (c) -- 6 pt\n",
    "\n",
    "Write a function `steepest_descent_f` that uses a variation of the \n",
    "steepest descent method to solve for a local minimum of $f(x_0, x_1)$\n",
    "from part (a). Instead of performing a line search as in Algorithm 6.3,\n",
    "the parameter $\\alpha$ will be provided to you as a parameter.\n",
    "Likewise, the initial guess $(x_0, x_1)$ will be provided.\n",
    "\n",
    "Use `(1, 1)` as the initial value and perform 10 iterations\n",
    "of the steepest descent variant on the function $f$.\n",
    "Save the result in the variable\n",
    "`steepest`. (The result `steepest` should be a list of length 11)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def steepest_descent_f(init_x0, init_x1, alpha, n=5):\n",
    "    \"\"\" Return the $n$ steps of steepest descent on the function \n",
    "    f(x_0, x_1) given in part(a), starting at (init_x0, init_x1).\n",
    "    The returned value is a list of tuples (x_0, x_1) visited\n",
    "    by the steepest descent algorithm, and should be of length\n",
    "    n+1. The parameter alpha is used in place of performing\n",
    "    a line search.\n",
    "    \n",
    "    Example:\n",
    "    \n",
    "    >>> steepest_descent_f(0, 0, 0.5, n=0)\n",
    "    [(0, 0)]\n",
    "    \"\"\"\n",
    "    return []\n",
    "\n",
    "steepest = []"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}