Fibonacci Search Algorithm

Question

Can someone show me an example of using this method for 'find the minimum of $$F(x) = x^2 - 6x + 2 \; \text{ on } [0,10] $$' ?

I'm trying to follow the algorithm detailed above, but I don't understand it. How do they know at what $k$ to stop at? Why are they stopping at $k = 2$?

Answer 1

Notice in the algorithm they specified, they have:

$$\Delta = \dfrac{\lambda_{k-2}}{\lambda_k}(b-a)$$

where $\lambda$ is the $n^{th}$ Fibonacci number.

What happens when $k = 2$? We have:

$$\Delta = \dfrac{\lambda_{2-2}}{\lambda_2}(b-a) = \dfrac{\lambda_{0}}{\lambda_2}(b-a) = \dfrac{1}{2}(b-a)$$

Thus, we have gotten to the last $\Delta$ evaluation we can do, so we are left with doing one last function evaluation to choose our last range which contains the minimum value of $f$ at $\hat x$.

The way they wrote this algorithm is a bit difficult to read and other authors use a different approach for the number of iterations.

I rewrote the algorithm to one that is easier to follow (I hope):

• Step 1: Choose $f(x), a, b$
• Step 2: Choose a desired accuracy $\epsilon$ and calculate the number of steps $n = \dfrac{b-a}{\epsilon}$
• Step 3: $k = n$
• Step 4: $\Delta = \dfrac{\lambda_{k-2}}{\lambda_k}(b-a)$
• Step 5: Set $ap = a + \Delta$ and $bp = b - \Delta$
• Step 6: If $f(ap) \ge f(bp)$, set $a = ap, b = b$, else set $a = a, b = bp$.
• Step 7: $k = k - 1$
• Step 8: If $k > 2$, repeat from Step 4 through Step 7.
• Step 9: Since $k = 2$, If $f(a) \ge f(b)$, set $ap = \dfrac{1}{2}(a+b) - \epsilon, a = ap$, else set $bp = \dfrac{1}{2}(a+b) + \epsilon, b = bp$
• Step 10: Print $(a, b)$
• Step 11: Set the minimum point as $\hat x = \dfrac{1}{2}(a + b)$

For the example you gave, you should find $\hat x = 3 ~\pm ~\epsilon$

Update Note that a better approach to calculating the number of iterations is to find $k$ such that:

$$\lambda_{k+1} < \dfrac{b-a}{\epsilon}$$

Set $n = k$.