Length of intervals in Fibonacci Line Search

Question

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?

Answer 1

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).

Second question: The picture does not specifically convey the use of the Fibonacci sequence. It just shows how points are added and interval of uncertainty shrinks. I you drew a free-hand diagram for golden section search, I suspect it would be indistinguishable from the given diagram.

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.