{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "(minimization-1D)=\n", "# Finding the Minimum of a Function of One Variable Without Using Derivatives — A Brief Introduction" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**References:**\n", "\n", "- Section 13.1 *Unconstrained Optimization Without Derivatives* of {cite}`Sauer`,\n", "in particular sub-section 13.1.1 *Golden Section Search*.\n", "- Section 11.1, *One-Variable Case* in Chapter 11 *Optimization* of {cite}`Chenney-Kincaid`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Introduction\n", "\n", "The goal of this section is to find the minimum of a function $f(x)$ and more specifically to find its location: the argument $p$ such that $f(p) \\leq f(x)$ for all $x$ in the domain of $f$.\n", "\n", "Several features are similar to what we have seen with zero-finding:\n", "\n", "- Some restictions on the function $f$ are needed:\n", " - with zero-finding, to guarantee *existence* of a solution, we needed at least an interval $[a, b]$ on which the function is continuous and with a sign change between the endpoints;\n", " - for minimization, the criterion for existence is simply an interval $[a, b]$ on which the function is continuous.\n", " \n", "- With zero-finding, we needed to compare the values of the function at three points $a < c < b$ to determine a new, smaller interval containing the root;\n", "with minimzation, we instead need to compare the values of the function at four points $a < c < d < b$ to determine a new, smaller interval containing the minimum.\n", "\n", "- There are often good reasons to be able to do this without using derivatives." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As is often the case, a guarantee of a *unique* solution helps to devise a robust algorithm:\n", "\n", "- to guarantee uniqueness of a zero in interval $[a, b]$, we needed an extra condition like the function being *monotonic*;\n", "\n", "- to guarantee uniqueness of a minimum in interval $[a, b]$, the condition we use is being *monomodal*:\n", "The function is decreasing near $a$, increasing near $b$, and changes between decreasing and increasing only once (which must therefore happen at the minimum.)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So we assume from now on that the function is *monomodal* on the interval $[a, b]$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Step 1: finding a smaller interval within $[a, b]$ that contains the minimum\n", "\n", "As claimed above, three points are not enough: even if for $a < c < b$ we have $f(a) > f(c)$ and $f(c) < f(b)$,\n", "the minimum could be either to the left or the right of $c$.\n", "\n", "So instead, choose two internal points $c$ and $d$, $a < c < d < b$.\n", "- if $f(c) < f(d)$, the function is increasing on at least part of the interval $[c, d]$, so the transition from decreasing to increasing is to the left of $d$: the minimum is in $[a, d]$;\n", "- if instead $f(c) > f(d)$, the \"mirror image\" argument shows that the minimum is in $[c, b]$.\n", "\n", "What about the borderline case when $f(c) = f(d)$?\n", "The monomodal function cannot be either increasing or decreasing on all of $[c, d]$ so must first decrease and then increase:\n", "the minimum is in $[c, d]$, and so is in either of the above intervals.\n", "\n", "So we almost have a first algorithm, except for the isue of *choosing*;\n", "given an interval $[a, b]$ on which function $f$ is monomodal:\n", "1. *Choose* two internal points $c$ and $d$, with $a < c < d < b$\n", "2. Evaluate $f(c)$ and $f(d)$.\n", "3. If $f(c) < f(d)$, replace the interval $[a, b]$ by $[a, d]$; else replace it by $[c, b]$.\n", "4. If the new interval is short enough to locate the minimum with sufficient accuracy (e.g. its length is less that twice the error tolerance) stop; its midpoint is a sufficiently accurate approximate answer);\n", "othewise, repaeat from step (1)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Step 2: choosing the internal points so that the method is guaranteed to converge\n", "\n", "There are a couple of details that need to be resolved:\n", "\n", "(A) Deciding how to choose the internal points $c$ and $d$.\n", "\n", "(B) Verifying that the interval does indeed shrink to arbitrarily small length after enough iterations, so that the algorithm succeeds.\n", "\n", "Once we have done that and got a working algorithm, there will be the issue of speed:\n", "\n", "(C) Amongst the many ways that we could choose the internal points, finding one that (typically at least) is fastest, in the sense of minimizing the number of functions evaluations needed." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For now, I will just describe one \"naive\" approach that works, but is not optimal for speed; **Trisection:**\n", "\n", "Take $c$ and $d$ to divide the interval $[a, b]$ into three equal-width sub-intervals:\n", "$c = (2a +b)/3$, $d = (a + 2b)/3$, so that each of $[a, c]$, $[c, d]$ and $[d, b]$ are of length $(b-a)/3$.\n", "\n", "Then the new interval is $2/3$ as long as the previous one, and the errors shrink by a factor of $(2/3)^k$ after $k$ steps, eventually getting as small as one wishes." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Step 3: choosing the internal points so that the method converges as fast as possible\n", "\n", "Coming soon: this leads to the [Golden Section Search](https://en.wikipedia.org/wiki/Golden-section_search) ...\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "This work is licensed under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.9.16" } }, "nbformat": 4, "nbformat_minor": 4 }