Fibonacci search method

The sequence having been named after Leonardo Fibonacci (1180-1225), a pioneer in the study of infinite series, the technique about to be described is called the Fibonacci search method. 

The optimum seeking methods which have been found to be particularly useful are the modified Fibonacci search (search by golden section) for one-dimensional searches and the Hooke-Jeeves search for multi-dimensional searches. Beveridge and Schechter (8) give a complete description of these searches. 

The last cycle of the method will be a dichotomous search, which we know is minimax for two experiments. Keifer (Kl) and Johnson (J2) show that the Fibonacci search is in fact minimax among all sequential techniques. In order to reduce the interval of uncertainty to less than 1% it only takes 11 Fibonacci experiments, three less than for a sequential dichotomous search. The advantage increases with the number of experiments. 

It should be remembered that all of these methods are very conservative, since they are all based on the assumption that nothing is known about the function y except that it is unimodal. If, as is often the case with physical systems, the function is known to be smooth and continuous, the engineer may wish to fit a curve to his points and estimate the maximum by ordinary differentiation. When doing this, however, it is worthwhile to locate the points according to the Fibonacci sequence so as to be able to shift to a Fibonacci search if the function does not behave according to preliminary estimates. 

Federal environment regulations, 75-78 Feed-tray location in distillation towers, lo Fiberglass reinforced plastics (FRP), 436-437 Fibonacci search, 407 Fifo method for materials accounting, 148... 

Other line search methods that involve only function evaluations, that is, no derivative calculations, are the dichotomous search, the Fibonacci search (Kiefer 1957), and the quadratic fit line search. The Fibonacci search is the most efficient derivative-free line search technique in the sense that it requires the fewest function evaluations to attain a prescribed degree of accuracy. The quadratic fit method... 

Comparison methods such as Fibonacci s method and golden section search exploit function unimodality within a specific interval of uncertainty with the aim... 

The determination of the minimum of the objective function by changing the values of Ani can be performed iteratively or with the help of appropriate solvers (e.g., one-dimensional search routines, such as the method of the golden section or the Fibonacci search [11]). 

Various optimum search methods exist for the minimization of objective functions, which can be used for the estimation of kinetic constants [3], for example, the Fibonacci method, the golden section method, the Newton-Raphson method, the Levenberg-Marquardt method, and the simplex method. Recently, even genetic algorithms have been... 

Indirect methods solve the necessary conditions for an optimum (looking at the shape of the function) directly via iteration. Region elimination techniques such as Fibonacci and Golden Section searches use function evaluations only to delete a portion of the independent variable range at each iteration. Interpolation techniques use polynomial fitting (quadratic or cubic oftentimes) to predict the location of the optimum. 

So far we have only discussed methods where the number of experiments, or equivalently, the size of the final interval desired, is known in advance. It often happens, however, that the experimenter does not decide in advance how many trials to perform. He just keeps trying until satisfied. If a dichotomous search is used, the sequence does not depend on the ultimate number of experiments, since at each stage the remaining interval is bisected. On the other hand, the exact location of the first two Fibonacci trials in principle depends on n, the total number of experiments to be performed. Fortunately, the ratio F -2/Fn is very near its limit 0.38 for n greater than 4. A very nearly optimal Fibonaccian method would be to take... 

Another method based on function comparison is the golden section method. The golden section method was proposed before the Fibonacci method. The golden section also exploits the position of the point still inside the new interval of uncertainty, in a sequential search. 

II. 12-6.88 = 4.24 far from t. Whatever the best point, the final interval of uncertainty after four points is 4.24, vhereas the Fibonacci method yields a final range equal to 4 (or less with a value of d < 1). Nevertheless, if the search is stopped at the third point, the interval of uncertainty is 6.88 for the golden section and 7 for the Fibonacci method, which is only optimized for four points and a value of d = 1. 

In root-finding, Bolzano s method is combined with other efficient methods because of its robustness. Unfortunately, in the case of one-dimensional optimization, neither the robust methods, golden search nor Fibonacci, can be satisfactorily combined with efficient methods. 

---