This is gonna be a brief post as most of the limitations of Fibonacci search were covered in my post on GSS. This makes sense because Fibonacci search is just a GSS with a different reduction at each step. So if follows that the limitations for GSS will also apply to the Fibonacci search. If you weren’t here for the GSS part 3 post I will go over the basic limitations.
Fibonacci search will find a minimum on the interval you choose however, this minimum might not be a global minimum. Local vs global minimum is a major issue with Fibonacci. One of the main requirements for Fibonacci, like GSS, is that a function must be unimodal. Now what does unimodal mean? IF you remember, this basically means that the function has a single local extremum. This makes it so the search method does not get stuck in an “incorrect” local minimum. This also depends on the interval you choose If you choose an interval that does not contain a minimum, Fibonacci search won’t (can’t) find it.One thing unique to the Fibonacci search is that it has a set amount of iterations chosen at the beginning of the method. If the user does not choose enough iterations the error surrounding the minimum can be large. However, if too many iterations are chosen then the method becomes arduous and expensive calculation wise. Having an idea of the tolerance you need for your minimum and the relative location is invaluable when using the fibonacci search method.To review, when should be use GSS or Fibonacci search : Function has one minimum (unimodal), you have an idea of the interval that contains the minimum, the function is of one variable.Here is the code i used to create the graphs from Part 2. This is written in matlab code. I will post a python version later.Code Starts here
%array to get values of our function
z = -5:.001:5;
% our function y=x^2 + 3x + 7
y = z.^2+3*z+7;
%number of iterations, feel free to change
iter = 5;
epsilon=0.05; %epislon to prevent double value at last iteration
% Fibonacci calculation sequence
fib = zeros(1,iter+2);
fib(1)=1;
fib(2)=1;
for i =3:iter+2
fib(i) = fib(i-1)+fib(i-2) ;
end
rho = zeros(1,iter);
%calculate z values from above Fibonacci Sequence
for i=0:iter
rho(i+1) = 1-(fib(end-i-1)/fib(end-i)) ;
end
%our search interval
x1=-3;
x2=1;
%finding our first two internal points
x3 = x1+rho(1)*(x2-x1);
x4 = x1 +(1-rho(1))*(x2-x1);
x30 = x1+rho(1)*(x2-x1);
x40 = x1 +(1-rho(1))*(x2-x1);
for i = 1:iter-1
% evaluate our function at the two internal points
fx3 = x3.^2+3*x3+7;
fx4 = x4.^2+3*x4+7;
%check if we are at the last iteration
if rho(i+1)==0.5
rho(i+1)= 0.5-epsilon;
end
%determine which interval we want to keep
if fx3>fx4
x1=x3;
x3=x4;
x4 = x1 +(1-rho(i+1))*(x2-x1); %find new x4 point
else
x2=x4;
x4=x3;
x3 = x1+rho(i+1)*(x2-x1); %find new x3
end
x3a(i) = x3;
x4a(i)=x4;
end
min = (x3+x4)/2 %our "boxed in" min
minf = min.^2+3*min+7 % our function evaluated at our min
%plot our results
plot(z,y,-3,y,3,y,x30,y,'g',x40,y,'g',x3a(1),y,'r',x4a(1),y,'r',x3a(2),y,'c',x4a(2),y,'c',x3a(3),y,'y',x4a(3),y,'y',x3a(4),y,'m',x4a(4),y,'m')
title('Fibonacci example')
xlabel('x')
ylabel('y')
-Marcello