Our next one dimensional search method or line search method is the Fibonacci Search method. Like the golden section search method, the Fibonacci search method is a method of finding an extrema of a unimodal function. Also like the GSS, Fibonacci search’s name directly describes how the search method reduces its search space. In GSS, we use the golden ratio to reduce our space. In Fibonacci search, we use, you guessed it, the fibonacci sequence.
Just a brief refresher, the Fibonacci sequence is defined by the following recursive equation:
Each number in the sequence is the sum of the two numbers in the sequence before it. By convention, when k=-1 F=0 and when k = 0 F=1. This allows us to calculate values for all k>0.OK back to the search method. With the GSS method we were limited on the reduction of our search interval. Each interval would reduce proportionally by 0.618 (remember (1-z) from the previous pots). This limits the speed convergence and how close our search method can get to our minimum. Fibonacci search remedies this. Fibonacci search allow us to vary our z values so that the space we search decreases much faster and gets closer to our target. The follow up question is obvious, how do we determine how z changes? Well that is an optimization problem in itself.Quickly going back to the GSS, we know that with every iteration our uncertainty range reduces by 0.618 or (1-z). So it follows that for N iterations, we have a total reduction factor of (0.618)^N or (1-z)^N. Now if we are allowed to vary z we get the following reduction factor:
The objective is to minimize the above. Minimizing this function results in a smaller final uncertainty range. However, we cannot just pick any z values for this equations. The are subject to certain requirements or constraints. The first is that for any z it must be greater or equal to 0 and less than or equal to 1/2. 1/2 is chosen as un upper limit to ensure that only one new testing point is needed for each iteration. If we have a reduction of 1/2 the two test points coincide in the middle of the interval. This prevents the method from continuing. The new z values must also satisfy the condition that the distance between our two test points must be equal to the distance from the selected test point to the nearest boundary point. With these constraints we can form the optimization problem and find our minimum.How does the Fibonacci sequence fit into all this? It happens to be that the optimal solution to our minimization problem involves the ratio of two sequential numbers in the sequence. The optimal z values are as follows:
This leads is to our first limitation. Fibonacci search, unlike GSS, requires a finite number of predetermined iterations. As seen by Zn, the end of the search is the beginning of the Fibonacci sequence. We need to take a quick pause at the last Z. When we plug in F1 and F2 of the FS we get Zn = 1/2. Earlier i warned of the dangers of a 1/2 reduction. To avoid falling into that pit, we introduce an ε (epsilon) which gently moves our Zn away from 1/2. In order for the epsilon fix to work, ε must be small. Now that we have our step reduction we can find our test points.We find our test points just like in GSS. X1 and X2 are the initial boundaries, X3 and X4 are calculated by the following equations:
With all this information we can form our search. The method takes on the same form of GSS, where the range is split into sections and one section is chosen and the other rejected. The accepted section is then further split and the method repeats. Now that we have the basics down and a rough outline of how to proceed we can try our method. Thats for part 2.-Marcello