The analysis about how and why the search methods work is pretty amazing and are very worth exploring. However, since this note is set to be concise, I may not include the analysis here (or I may in the future). I highly recommend doing some reading on this topic, which should be very helpful.
If $f $ has only one local minimizer, we say the function $f $ is unimodal.
Golden section search is a search method that can narrow down the minimizer $x^*$ of a unimodal function $f: \R \to \R $ over a closed interval $[a_0, b_0]$.
Golden section search is an iterative method, and is defined as follows:
Let $\rho = \frac{ 3 - \sqrt[ ]{ 5 }}{ 2 } = 1 - .6180339887… $
-
Let $l_n = b_n - a_n, s^\pare{n}_a = l_n (1- \rho), s^\pare{n}_b = l_n \rho$.
-
Compare $f(s^\pare{n}_a)$ and $f(s^\pare{n}_b) $:
-
if $f(s^\pare{n}_a) \geq f(s^\pare{n}_b)$ then $x^* \in [a_n, s^\pare{n}_b]$.
set $a_{n+1} = a_n, b_{n+1} = f(s^\pare{n}_b) $. Iterate. Notice that $s^\pare{n+1}_a = s^\pare{n}_a$. -
if $f(s^\pare{n}_a) < f(s^\pare{n}_b)$ then $x^* \in [s^\pare{n}_a, b_n]$.
set $a_{n+1} = f(s^\pare{n}_a), b_{n+1} = b_n $, iterate. Notice that $s^\pare{n+1}_b = s^\pare{n}_b$.
$N$ steps of reduction using the golden section method reduces the range by the factor
$$(1 - \rho)^N \approx (0.61803)^N $$