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\u00a0Fibonacci search\u00a0is 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.<\/p>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\u00a0issue with Fibonacci. One of the main requirements for Fibonacci, like GSS,\u00a0is that a function must be unimodal. Now what does unimodal mean? \u00a0IF 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.<\/p>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.<\/p>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.<\/p>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.<\/p>Code Starts here<\/p>\n
\n%array to get values of our function\nz = -5:.001:5;\n\n% our function y=x^2 + 3x + 7\ny = z.^2+3*z+7;\n\n%number of iterations, feel free to change\niter = 5;\nepsilon=0.05; %epislon to prevent double value at last iteration\n\n% Fibonacci calculation sequence\nfib = zeros(1,iter+2);\nfib(1)=1;\nfib(2)=1;\nfor i =3:iter+2\nfib(i) = fib(i-1)+fib(i-2) ;\nend\nrho = zeros(1,iter);\n\n%calculate z values from above Fibonacci Sequence\nfor i=0:iter\nrho(i+1) = 1-(fib(end-i-1)\/fib(end-i)) ;\nend\n\n%our search interval\nx1=-3;\nx2=1;\n\n%finding our first two internal points\nx3 = x1+rho(1)*(x2-x1);\nx4 = x1 +(1-rho(1))*(x2-x1);\n\nx30 = x1+rho(1)*(x2-x1);\nx40 = x1 +(1-rho(1))*(x2-x1);\nfor i = 1:iter-1\n% evaluate our function at the two internal points\nfx3 = x3.^2+3*x3+7;\nfx4 = x4.^2+3*x4+7;\n%check if we are at the last iteration\nif rho(i+1)==0.5\nrho(i+1)= 0.5-epsilon;\nend\n%determine which interval we want to keep\nif fx3>fx4\nx1=x3;\nx3=x4;\nx4 = x1 +(1-rho(i+1))*(x2-x1); %find new x4 point\nelse\nx2=x4;\nx4=x3;\nx3 = x1+rho(i+1)*(x2-x1); %find new x3\nend\n\nx3a(i) = x3;\nx4a(i)=x4;\nend\n\nmin = (x3+x4)\/2 %our "boxed in" min\nminf = min.^2+3*min+7 % our function evaluated at our min\n\n%plot our results\nplot(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')\ntitle('Fibonacci example')\nxlabel('x')\nylabel('y')\n\n<\/pre>-Marcello<\/p>\n","protected":false},"excerpt":{"rendered":"
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\u00a0Fibonacci search\u00a0is 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… <\/p>\n