2
$\begingroup$

The problem is as follows: given black box access to a strictly quasiconvex (or unimodal) function $f$ on an interval, say [0, 1], query $f$ repeatedly at various points to find a subinterval containing the minimum. After $n$ queries to $f$, if the interval's length is reduced by a factor of $t$, the algorithm's score is $\sqrt[n]{t}$, which is the amortized factor by which each query to $f$ reduces the length of the interval.

For example, standard ternary search starts with $f(0)$ and $f(1)$, additionally queries $f(\frac{1}{3})$ and $f(\frac{2}{3})$, and obtains a subinterval with size $\frac{2}{3}$. It then iterates and each subsequent iteration starts with $f$ evaluated at the endpoints of the subinterval and reduces the subinterval's length by a factor of $\frac{2}{3}$. Thus the score is $\sqrt{\frac{2}{3}}$.

A better ternary search instead queries at $\frac{1}{2}-\varepsilon$ and $\frac{1}{2}+\varepsilon$ and iterates for a score of $\sqrt{\frac{1}{2}+\varepsilon}$.

An even better algorithm is "pentanary search", starting with $f(0)$, $f(\frac{1}{2})$, and $f(1)$ and querying $f(\frac{1}{4})$ and $f(\frac{3}{4})$ to obtain a subinterval that is the first, middle, or last half of $[0, 1]$. It then iterates. The key is that 3 points from each iteration can be used in the next. Thus the score is $\sqrt{\frac{1}{2}}$.

The best I know of, "golden search", starts with $f(0)$, $f(1)$, and either $f(1-\frac{1}{\phi})$ or $f(\frac{1}{\phi})$, querying for the other of those two, where $\phi$ is the golden ratio. The subinterval is either $[0, \frac{1}{\phi}]$ or $[1-\frac{1}{\phi}, 1]$ and 3 values from the previous iteration can be reused, achieving a score of $\frac{1}{\phi}$.

Can we do better than "golden search"? Do we know the optimal score for this problem?

$\endgroup$
2
$\begingroup$

Avriel and Wilde, in their article Optimality proof for the symmetric Fibonacci search technique, showed that Fibonacci search is optimal in the following sense: if you want to bracket the minimum in an interval of length $\delta$ using at most $k$ evaluations, then Fibonacci search maximizes the length of your initial interval.

$\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.