# 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 = []