{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Tutorial 08 - Optimization"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Search for extremes of functions, golden section search, parabolic interpolation search, gradient descent."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"import matplotlib as mpl\n",
"import matplotlib.pyplot as plt\n",
"from scipy import linalg, optimize"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Golden-section search"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"[Golden-section search](https://en.wikipedia.org/wiki/Golden-section_search)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"**Exercise 08.1:** Implement the golden-section search method.\n",
" \n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def golden_section_search(f, a, b, error_tolerance=1.0e-15, max_iterations=500):\n",
" \"\"\"\n",
" Finds the minimum of function using golden section search.\n",
" Args:\n",
" f (function): A strictly unimodal function on [a, b]\n",
" a (float): Left endpoint of the interval\n",
" b (float): Right endpoint of the interval\n",
" error_tolerance (float): Error tolerance\n",
" max_iterations (int): Maximum number of iterations\n",
" Returns:\n",
" float: A coordinate of minimum\n",
" Raises:\n",
" RuntimeError: Raises an exception when the minimum is not found\n",
" \"\"\"\n",
"\n",
" # add your code here\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You may evaluate the correctness of your implementation using the [`scipy.optimize.minimize_scalar`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize_scalar.html) function."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def f(x):\n",
" return np.sin(x)\n",
"try:\n",
" np.testing.assert_array_almost_equal(golden_section_search(f, -2.0, 0.0, 1.0e-7), \n",
" optimize.minimize_scalar(f, bracket=[-2.0, 0.0], tol=1.0e-7, method=\"golden\").x, decimal=7)\n",
"except AssertionError as E:\n",
" print(E)\n",
"else:\n",
" print(\"The implementation is correct.\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"**Exercise 08.2:** Find a local minimum of the following function,\n",
"\n",
"$$\n",
"f(x) = 3 \\sin(x + 2) + x^2 - 3x + 5,\n",
"$$\n",
"\n",
"in the interval $ [-5, 5] $ with the error tolerance of $ 10^{-7} $ using the golden-section search method. \n",
" \n",
"1. Print the coordinate of the minimum.\n",
"2. Plot the function $ f $ and mark the minimum. \n",
" \n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"\n",
"# add your code here\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Parabolic interpolation search"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"[Parabolic interpolation search](https://en.wikipedia.org/wiki/Successive_parabolic_interpolation)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"**Exercise 08.3:** Implement the parabolic interpolation search method.\n",
" \n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def parabolic_interpolation_search(f, a, b, c, error_tolerance=1.0e-15, max_iterations=500):\n",
" \"\"\"\n",
" Finds the minimum of function using parabolic interpolation search.\n",
" Args:\n",
" f (function): A strictly unimodal function on [a, b]\n",
" a (float): Left endpoint of the interval\n",
" b (float): Point inside the interval\n",
" c (float): Right endpoint of the interval\n",
" error_tolerance (float): Error tolerance\n",
" max_iterations (int): Maximum number of iterations\n",
" Returns:\n",
" float: A coordinate of minimum\n",
" Raises:\n",
" RuntimeError: Raises an exception when the minimum is not found\n",
" \"\"\"\n",
"\n",
" # add your code here\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You may evaluate the correctness of your implementation using the [`scipy.optimize.minimize_scalar`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize_scalar.html) function."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def f(x):\n",
" return np.sin(x)\n",
"try:\n",
" np.testing.assert_array_almost_equal(parabolic_interpolation_search(f, -2.0, -1.0, 0.0, 1.0e-7), \n",
" optimize.minimize_scalar(f, bracket=[-2.0, 0.0], tol=1.0e-7, method=\"golden\").x, decimal=7)\n",
"except AssertionError as E:\n",
" print(E)\n",
"else:\n",
" print(\"The implementation is correct.\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"**Exercise 08.4:** Find a local minimum of the following function,\n",
"\n",
"$$\n",
"f(x) = \\ln(1 + \\left| x - 1 \\right|^2) - \\arctan x\n",
"$$\n",
"\n",
"in the interval $ [-5, 5] $ with the error tolerance of $ 10^{-7} $ using the parabolic interpolation search method. \n",
" \n",
"1. Print the coordinate of the minimum.\n",
"2. Plot the function $ f $ and mark the minimum. \n",
" \n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"scrolled": false
},
"outputs": [],
"source": [
"\n",
"# add your code here\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Steepest descent"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The [steepest descent](https://en.wikipedia.org/wiki/Gradient_descent) method"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"**Exercise 08.5:** Implement the steepest descent method for a function of one unknown.\n",
" \n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def steepest_descent(f, x_0, step, error_tolerance=1.0e-15, max_iterations=1e5):\n",
" \"\"\"\n",
" Finds the minimum of function using the method of steepest descent.\n",
" Args:\n",
" f (function): A strictly unimodal and differentiable function in a neighborhood of a point x_0\n",
" x_0 (float): Initial guess\n",
" step (float): Step size multiplier\n",
" error_tolerance (float): Error tolerance\n",
" n_max (int): Maximum number of iterations\n",
" Returns:\n",
" float: A coordinate of minimum\n",
" Raises:\n",
" RuntimeError: Raises an exception when the minimum is not found\n",
" \"\"\"\n",
"\n",
" # add your code here\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You may evaluate the correctness of your implementation using the [`scipy.optimize.minimize_scalar`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize_scalar.html) function."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def f(x):\n",
" return np.sin(x)\n",
"try:\n",
" np.testing.assert_array_almost_equal(steepest_descent(f, -2.0, 1.0e-3), \n",
" optimize.minimize_scalar(f, bracket=[-2.0, 0.0], tol=1.0e-7, method=\"golden\").x, decimal=7)\n",
"except AssertionError as E:\n",
" print(E)\n",
"else:\n",
" print(\"The implementation is correct.\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"**Exercise 08.6:** Find a local minimum of the following function,\n",
" \n",
"$$\n",
"f(x) = -x^3 \\mathrm{e}^{-(x + 1)^2} + 10 \\, x \\tanh(x + 2)\n",
"$$\n",
"\n",
"with the error tolerance of $ 10^{-7} $ using the steepest descent method. Use the point $ x_0 = 0 $ as an initial guess.\n",
" \n",
"1. Print the coordinate of the minimum.\n",
"2. Plot the function $ f $ and mark the minimum. \n",
" \n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"scrolled": true
},
"outputs": [],
"source": [
"\n",
"# add your code here\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"**Exercise 08.7:** Implement the steepest descent method for a function of $ n \\in \\mathbb{N} $ unknowns.\n",
" \n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def steepest_descent_nd(f, x_0, step, error_tolerance=1.0e-15, max_iterations=1e5):\n",
" \"\"\"\n",
" Finds the minimum of function using the method of steepest descent.\n",
" Args:\n",
" f (function): A strictly unimodal and differentiable function in a neighborhood of a point x_0\n",
" x_0 (float): Initial guess\n",
" step (float): Step size multiplier\n",
" error_tolerance (float): Error tolerance\n",
" n_max (int): Maximum number of iterations\n",
" Returns:\n",
" float: A coordinate of minimum\n",
" Raises:\n",
" RuntimeError: Raises an exception when the minimum is not found\n",
" \"\"\"\n",
"\n",
" # add your code here\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You may evaluate the correctness of your implementation using the [`scipy.optimize.minimize`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html) function."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def f(x):\n",
" return np.sin(x[0]) * np.sin(x[1])\n",
"try:\n",
" np.testing.assert_array_almost_equal(steepest_descent_nd(f, np.array([-2.0, -2.0]), 1.0e-3), \n",
" optimize.minimize(f, np.array([-2.0, -2.0])).x, decimal=7)\n",
"except AssertionError as E:\n",
" print(E)\n",
"else:\n",
" print(\"The implementation is correct.\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"**Exercise 08.8:** Find a local minimum of the following function,\n",
" \n",
"$$\n",
"f(x, y) = (1 - x)^2 + 100 (y - x^2)^2,\n",
"$$\n",
"\n",
"with the error tolerance of $ 10^{-7} $ using the steepest descent method. Use the point $ (x_0, y_0) = (0, 0) $ as an initial guess.\n",
" \n",
"1. Print the coordinate of minimum.\n",
"2. Plot the function $ f $ and mark the minimum.\n",
" \n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"scrolled": false
},
"outputs": [],
"source": [
"\n",
"# add your code here\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"**Note:** The function in Exercise 08.8 is called the [Rosenbrock function](https://en.wikipedia.org/wiki/Rosenbrock_function) and is used as a performance test problem for optimization algorithms. The global minimum of this function is located inside a long, narrow, parabolic shaped flat valley. \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.8.5"
}
},
"nbformat": 4,
"nbformat_minor": 2
}