# coding: utf-8

# # CSC338. Homework 9
# 
# Due Date: Wednesday March 25, 9pm
# 
# Please see the guidelines at https://www.cs.toronto.edu/~lczhang/338/homework.html
# 
# ### What to Hand In
# 
# Please hand in 2 files:
# 
# - Python File containing all your code, named `hw9.py`.
# - 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.
# 
# 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.
# 
# **Make sure to remove or comment out all matplotlib or other expensive code before submitting your homework!**
# 
# 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.

# In[ ]:


import math
import numpy as np


# ## Question 1. Golden Section Search
# 
# ### Part (a) -- 6 pt
# 
# Write a function `golden_section_search` that uses the Golden Section search
# to find a minima of a function `f` on the interval `[a, b]`. You may assume
# that the function `f` is unimodal on `[a, b]`.
# 
# The function should evaluate `f` only as many times as necessary. There will
# be a penalty for calling `f` more times than necessary.
# 
# Refer to algo 6.1 in the textbook, or
# slide 19 of the posted slides accompanying the textbook.

# In[ ]:


def golden_section_search(f, a, b, n=10):
    """ Return the Golden Section search intervals generated in 
    an attempt to find a minima of a function `f` on the interval
    `[a, b]`. The returned list should have length `n+1`.
   
    Do not evaluate the function `f` more times than necessary.
    
    Example: (as always, these are for illustrative purposes only)

    >>> golden_section_search(lambda x: x**2 + 2*x + 3, -2, 2, n=5)
    [(-2, 2),
     (-2, 0.4721359549995796),
     (-2, -0.4721359549995796),
     (-1.4164078649987384, -0.4721359549995796),
     (-1.4164078649987384, -0.8328157299974766),
     (-1.1934955049953735, -0.8328157299974766)]
    """


# ### Part (b) -- 2 pt
# 
# Consider the following functions, both of which are unimodal on `[0, 2]`
# 
# $f_1 (x) = 2 x^2 - 2x + 3$
# 
# $f_2 (x) = - x e^{-x^2}$
# 
# Run the golden section search on the two functions for $n=10$ iterations.
# 
# Save the returned lists in the variables `golden_f1` and `golden_f2`

# In[ ]:


golden_f1 = None
golden_f2 = None


# ## Question 2. Newton's Method in One Dimension
# 
# 
# ### Part (a) -- 6 pt
# 
# Implement Newton's Method to find a minima of a real function
# in one dimension.

# In[ ]:


def newton_1d(f, df, ddf, x, n=10):
    """ Return the list of iterates computed when using 
    Newton's Method to find a local minimum of a function `f`,
    starting from the point `x`. The parameter `df` is the 
    derivative of `f`. The parameter `ddf` is the second 
    derivative of `f`. The length of the returned list 
    should be `n+1`.
    
    Example: (as always, these are for illustrative purposes only)
    
    >>> newton_1d(lambda x: x**3, 
    ...           lambda x: 3 * (x**2),
    ...           lambda x: 6 * x, 
    ...           x=1.0, n=5)
    [1, 0.5, 0.25, 0.125, 0.0625, 0.03125]
    """


# ### Part (b) -- 4 pt
# 
# Consider `f1` and `f2` from Question 1 Part (b). 
# 
# Complete the functions `df1`, `df2` which compute the derivatives of `f1` and `f2`.
# 
# Complete the functions `ddf1`, `ddf2` which compute the second derivatives of `f1` and `f2`.

# In[ ]:


def df1(x):
    return None
def ddf1(x):
    return None

def df2(x):
    return None
def ddf2(x):
    return None


# ### Part (c) -- 2 pt
# 
# Run Newton's Method on the two functions $f_1$ and $f_2$ for $n=30$ iterations,
# starting at $x = 1$.
# 
# Save the returned lists in the variables `newton_f1` and `newton_f2`.

# In[ ]:


newton_f1 = None
newton_f2 = None


# ## Question 3.
# 
# Consider the function 
# 
# $$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 $$
# 
# ### Part (a) -- 2 pt
# 
# Derive the gradient. Include your solution in your PDF writeup.
# 
# ### Part (b) -- 2 pt
# 
# Derive the Hessian. Include your solution in your PDF writeup.
# 
# ### Part (c) -- 6 pt
# 
# Write a function `steepest_descent_f` that uses a variation of the 
# steepest descent method to solve for a local minimum of $f(x_0, x_1)$
# from part (a). Instead of performing a line search as in Algorithm 6.3,
# the parameter $\alpha$ will be provided to you as a parameter.
# Likewise, the initial guess $(x_0, x_1)$ will be provided.
# 
# Use `(1, 1)` as the initial value and perform 10 iterations
# of the steepest descent variant on the function $f$.
# Save the result in the variable
# `steepest`. (The result `steepest` should be a list of length 11)

# In[ ]:


def steepest_descent_f(init_x0, init_x1, alpha, n=5):
    """ Return the $n$ steps of steepest descent on the function 
    f(x_0, x_1) given in part(a), starting at (init_x0, init_x1).
    The returned value is a list of tuples (x_0, x_1) visited
    by the steepest descent algorithm, and should be of length
    n+1. The parameter alpha is used in place of performing
    a line search.
    
    Example:
    
    >>> steepest_descent_f(0, 0, 0.5, n=0)
    [(0, 0)]
    """
    return []

steepest = []