# Length of intervals in Fibonacci Line Search

I am self-learning basic optimization techniques and trying to implement the 1-dimensional line search algorithms from the book - Algorithms for Optimization by Kochenderfer and Wheerler, MIT Press. I had a couple of rather straight-forward questions about the Fibonacci method.

On page 37, the authors write:

Suppose we can query $$f$$ twice. If we query $$f$$ on the one-third and two-third points of the interval, then we are guaranteed to remove one-third of our interval.

We can guarantee a tighter bracket by moving our guesses towards the center. In the limit $$\epsilon \to 0$$, we are guaranteed to shrink our guess by a factor of $$2$$ as shown below.

In any iteration $$k$$, the search interval is shrunk to $$1-\rho_k$$ times the original length.

Question. Does the second picture above tell that, as the process converges, $$c$$ and $$d$$ are quite close to each other, and the reduction factor approaches $$1/2$$?

With three queries, we can shrink the interval by a factor of three. We first query $$f$$ on the one-third and two-third points on the interval, discard one-third of the interval, and then sample just next to the better sample as shown in the figure.

For $$n$$ queries, the length of the intervals are related to the Fibonacci sequence: $$1,1,2,3,5,8,13,\ldots$$.

Question. I deduced this mathematically. For instance, if $$N=5$$,

\begin{align*} I_2 &= (1- \rho_1) I_1 = \frac{F_5}{F_6}I_1 = \frac{8}{13} I_1\\ I_3 &= (1- \rho_2) I_2 = \frac{F_4}{F_5}I_2 = \frac{5}{8} \cdot \frac{8}{13} I_1\\ I_4 &= (1- \rho_3) I_3 = \frac{F_3}{F_4}I_3 = \frac{3}{5}\cdot \frac{5}{8} \cdot \frac{8}{13} I_1\\ I_5 &= (1- \rho_4) I_4 = \frac{F_2}{F_3}I_4 = \frac{2}{3} \cdot \frac{3}{5}\cdot \frac{5}{8} \cdot \frac{8}{13} I_1\\ I_6 &= (1- \rho_5) I_4 = \frac{F_1}{F_2}I_5 = \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{3}{5}\cdot \frac{5}{8} \cdot \frac{8}{13} I_1 = \frac{1}{13}I_1 \end{align*}

The visual description was not super-intuitive to me. It's apparent that $$I_1=I_2 + I_3$$ and so forth. Any insights into the visual description?

First question: Theoretically, yes (assuming you are talking about the reduction factor per pair of observations). Practically speaking, there is a minimum gap you can have between $$c$$ and $$d$$, below which rounding error makes the comparison of $$f(c)$$ and $$f(d)$$ too dicey to trust. So the reduction factor per pair of iterations approaches something slightly less than 1/2 (but close enough to 1/2 for government work, as the saying goes). This is similar to bisection search using gradients (where you evaluate $$f'(x)$$ at the midpoint, rather than $$f(x)$$ at and near the midpoint).
As an aside, my understanding is that with $$N=5$$ measurement points, the first fraction should be $$F_4/F_5 = 5/8$$ rather than $$F_5/F_6$$, and so on.