3
$\begingroup$

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.

enter image description here

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.

enter image description here

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$?

enter image description here

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.

enter image description here

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

enter image description here

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.