Hello Internet! This is Oscar Veliz again
continuing our series on minimization
this time looking at Fibonacci search
I'll go over the history and
visualization as well as the algorithm
and an example
as a primer you should already be
familiar with ternary search and
dichotomous search recall that with both
of these methods the values for c and d
are never reused let's refer back to
optimum seeking methods by Wilde in it
the author writes "powerful as the
dichotomous technique is there exists a
method that is even better the epsilon
minimax sequential search scheme was
found by Kiefer in 1953" in "sequential
minimax search for a maximum" Kiefer uses
the fibonacci sequence to find a maximum
starting with 0 & 1 adding those two
terms to come up with the next term in
the series to give 1 then using 1 and 1
to get 2 and so on giving the famous
Fibonacci sequence here's the rest of
that paragraph but don't panic let's
look at another paper
three years later Johnson published "best
exploration for maximum is Fibonaccian"
in which he writes "when the author
obtained the results presented here he
thought it was new subsequently it was
found that the result had previously
been published by Kiefer" in his version
the Fibonacci sequence he starts from
one and one
going back to Kiefer's paper there are
two important ratios that we'll be using
using these two ratios as an example
let's let n be the value of 6 and our
Fibonacci sequence would look like this
I'm ignoring the 0 just to keep things
simple
our first ratio would be 5 over 13 and
our second would be 8 over 13 but how
does this look visually imagine a line
segment of length 13 that's a Fibonacci
number using the previous two Fibonacci
numbers we can divide it into five and
eight at some point c then using the
ratio with 8 we can compute this new
value d notice how it is symmetric using
the 8 on the right side we can divide it
up again into its previous Fibonacci
numbers of 3 and 5 using the same
approach of 5 now we can compute a new
value for d taking the 5 on the right
side we can divide that up again into
its two previous Fibonacci numbers 2 and
3 the same with 3 on the right side into
1 and 2 2 on the right side into 1 and 1
because this process is symmetric it
doesn't really matter if you choose the
left or right side eventually you can
break this down into 1 and 1 we'll now
use this process to find a minimum here
we'll use the last 3 digits in our
Fibonacci sequence of 3 5 and 8 to come
up with 3 over 8 and 5 over 8 we'll use
these equations to come up with our new
values c and d then using what we know
from ternary search when f(c) is less
than f(d) we eliminate the rightmost
interval
and this time we'll replace c with d and
d with b we also have lowered our
Fibonacci terms to be two three and five
using our numbers for c we will pick two
over five to compute our next value here
f(c) is still less than  f(d) eliminate the right side
we lowered our Fibonacci terms again in
this case we'll need a new value for c
which is 1 over 3 this example we want
to eliminate the leftmost interval
now we've reached 1 & 1 so we'll stop
Wilde again "now we can see what it is
about the Fibonacci search plan that
makes it better than the dichotomous
technique. In a Fibonacci scheme each new experiment serves to
reduce the interval of uncertainty but
in a dichotomous scheme it takes two new
experiments to cut down the interval of
uncertainty" going back to our line
segments we stopped one once we reached
any two 1 by 1's going from 13 down to 2
each unit interval is essentially b
minus a over 13 or b minus a over F_6
more generally we can write this as F_n down to some 2x2 interval we can
rewrite it as b minus a over F_n
equal to some epsilon also b minus a
over epsilon equal to some F_n
the trouble then becomes how do you find
F_n from our equation and as an
example we'll use b minus a equal to 1
and epsilon of .01 plugging that
in we get 100 this means we need to find
the Fibonacci term of 100 or larger
scrolling down the first value we find is
144 giving N of 11
Johnson again he notes that F_20 is
greater than 10,000 giving an epsilon
accuracy of 10 to the minus 4 requiring
20 function calls
whereas dichotomous search would take 28
and reality we shouldn't represent them
now as one by ones but rather epsilons
this does mean that our final ending
condition has a length of 2 Epsilon if
that really bothers you you can always
switch to another search technique
afterwards or start with F_n+1
the algorithm for Fibonacci search looks
something like this starting with some
unimodal function f(x) and the interval
a b start with the Fibonacci sequence at
1 1 and set N equal to 1 then add 1 to n
and compute the next term in the
Fibonacci sequence if this does not give
you a small enough epsilon go and
compute the next term in the case that
it does start computing c and d and then
save the function calls at f(c) and f(d) then check if n is equal to 2 when
it is that's our minimum you can return a
plus b over 2 in this case you could
absolutely return c or d because those
will also get the midpoints and then
stop when it isn't remove one from N and
then check if f(c) is less than f(d)
what it is that means we'll eliminate
our interval on the right and then save
off our values for c and f(c) then
compute a new value for c and a new f(c)
otherwise we'd eliminate the term on
the left and do the opposite side then
repeat the process
using again the same example from the
other videos
it took Fibonacci search 28 iterations
to find our ending interval ternary
required 34 iterations but dichotomous
was even faster 19 how is that better
than Fibonacci's 28
well the real power comes from the
number of function calls that the method
requires as a fun fact this method
actually found our minimum in the first
iteration but it doesn't know that until
it shrinks the interval small enough
in that example our b - a was equal to
1 and our ending epsilon was 10 to the
minus 6 which would mean we need a
Fibonacci value of at least a million
which happened after F_30 meaning n
was 30 our value for d was this number
and our minimum was that number
very close
going back to Kieffer one last time he
lets mu be the value of 0.618 and then
our ratios be mu and one - mu to give
"the same geometric configuration" what
does he mean by that
Johnson also refers to this 0.618 number
noting "this constant ratio to determine
the next x would be useful in a
computing-machine code" referring to
the "golden section" ... foreshadowing?
before you go Fibonacci search is guaranteed to
find a minimum and it's gonna do so with
a linear order but it will save on
function calls compared to ternary
search and dichotomous search there is
some overhead though with computing the
Fibonacci sequence and finding what term
you'll want to use for n but this leads
right into the Golden-section search the
topic for another video the code that
are used for this example will be hosted
on github
as always thank you for watching I hope
it was able to visualize how Fibonacci
search worked in a way that made sense
if you want to see the video on Golden-
section search make sure to subscribe to
the channel and turn on notifications
so you can see when it comes out again
thank you for watching
