Hello Internet! This is Oscar Veliz this time with a video on the gold standard
and minimization golden-section search I'll go over the history and derivation of
the golden ratio before showing the algorithm and an example for scaffolding
it's recommended that you have some familiarity with ternary search and
optionally check out my video on Fibonacci search let's refer back to
algorithms for minimization without derivatives by Richard Brent in it the
author writes if f is unimodal on the interval a b then the minimum for f can
be located to any desired accuracy by the well-known methods of Fibonacci
search or golden section search the reader is referred to Wilde for an
excellent description of these methods this is Wilde's book optimum seeking
methods in it he writes the epsilon minimax sequential search scheme
Fibonacci search was found by Kiefer in 1953 referring of this paper there is
however another technique which while nearly as efficient as the Fibonacci
search is completely independent of the number of experiments available he goes
on to say let us instead hold the ratio of successive lengths constant calling
this ratio tau we have this equation we obtain tau squared is equal to tau plus
1 only one root of this equation is positive and so we see that tau is equal
to 1 plus the square root of 5 over 2 the results of these two experiments will determine
which segment is to be explored further as usual the remaining segment will
contained one of the previous trials one merely places a next experiment
symmetrically we call this procedure search by golden section
recall ternary search we check if f(c) is less than f(d) when it is we
eliminate the rightmost interval and replace our value for d with b we then come up
with new values for c and d this was our old value of c it'd be helpful if this
could be used again for example calling this value d and coming up with some new
value c somewhere between a and d the trouble is that these two intervals are
not the same size and from the universal law a bad luck if a method has a choice
to shrink the search space it will always pick a larger one and in this
example f(c) was greater than f(d) eliminate the left side our next a b is
going to be either a d or c b therefore we want to try to pick c to keep a
constant ratio of our next a b to our current a b if we label our chords
like this you want to decide where to put c such that our chord ratios will be
the same knowing this equality we're going to take our longer chord a b and
split it up into the sum of cb plus ac then split up that summation and then
simplify afterwards knowing our equality from the top we
can rewrite it to be like this multiply both sides by that cb over ac fraction
and we get this equality such that cb over ac squared is equal to cb over ac plus
one rewrite it so that it's equal to zero this means our ratio is equal to
one plus the square root of five over two known as the golden ratio
now that we've solved for the golden ratio we can actually solve for c to do
that rewrite our chord ab to be b - a and our chord cb to be b-c then
multiply both sides by the denominator and expand the right side then move our
c term over and everything else to the right side then divide everything by the
golden ratio and we have our equation for c we did the same process to find
our value for d
our algorithm for golden section search looks like this from our
starting point and given our unimodel function f over some interval a b
compute c and d using our equations from earlier then save the function calls at
f(c) and f(d) then check it b - a is less than some epsilon when it is
we've found our minimum we return a plus b over 2 and we can stop
when it isn't
check if f(c) is less than f(d) when that's the case remove the rightmost
interval and save off our values for c and f(c) then compute a new c and new
f(c) otherwise we do the opposite side then repeat the process
here's what that looks like visually using our equations we solve for c and d
then check if f(c) is less than f(d) in this case it is so we eliminate the
rightmost side afterwards replace c with d and d with b
now we compute a new c and a new f(c) then repeat our condition check in this
case we again eliminate the rightmost side we compute a new value for c and do
our condition check in this instance we would eliminate the leftmost side
and repeat the process here's a numerical example for the function
x cubed over 3 minus x squared over 2 minus X minus 1 with an ending epsilon
10 to the minus 6 over starting interval 1 2 it took golden-section search 29
iterations to find our solution notice that it also found the minimum in the
first iteration but it doesn't know that until it shrinks the interval space
small enough here's a table showing all of the minimum finding methods that
we've discussed so far on the same example using the same epsilon and
interval notice that the Dichotomous, Fibonacci, and Golden-section are all
clearly better than ternary with Fibonacci and Golden-section being the
most efficient Golden-section needed one more iteration that's because it has a
different end condition than Fibonacci
but how much is our interval being shrunk by every iteration if we label
our chords like this knowing that the ratios are all equal to the golden ratio
let's look at the left side what is this ratio equal to well you know that ad is
equal to cb therefore plugging that in we get the golden ratio again what if we
invert that ratio this gives us 1 over the golden ratio equal to 0.618 this
means that the Golden-section search reduces our search base by 0.618 each
iteration meanwhile ternary reduces it by two-thirds Wilde again
although both Kiefer and Johnson have suggested the search technique just
described the first man to divide a line segment as we have done here was none
other than Euclid himself and as one might expect he did it entirely with a
ruler and compass division of a segment into two unequal parts of the ratio of a
whole to the larger is equal to the ratio of the larger to the smaller came
to you know as the golden section
fans of the channel will know that the golden
ratio comes up a lot in my videos especially when solving the equation x
squared minus X minus 1 equal to 0 which has two solutions one plus the square
root of 5 over 2 and 1 minus the square root of 5 over 2 you can solve this using the
quadratic equation did you also know that 1 over the golden ratio gives you
0.618 and that the golden ratio minus 1 gives you 0.618
or even the absolute value of psi gives you 0.618
huh if we take our question for c and instead of doing division replace that
with 1 over the golden ratio we can rewrite it to be the golden ratio minus
one you can use the golden ratio minus one to avoid a lot of division
things to note about Golden-section search is that it is still guaranteed to
find a minim and it's gonna do so faster than ternary search although still with
a linear order while saving on function calls and avoiding the Fibonacci
sequence for more on a minimization I recommend checking out Jarratt's method and
Brent's minimization method each will have their own video the code that I
used will be hosted on GitHub
before you go I'd like to give a shout out to friend of the channel Mathemaniac
and his video on finding the golden ratio using game theory
as always thank you
for watching I had originally intended just to make a video on Golden-section
search but the project expanded into quite a number of videos thank you for
sticking with them and checking out everything in this series