Dichotomous search

From Glossary

Jump to: navigation, search

This finds the maximum of a unimodal function on an interval, LaTeX: (a, b), by evaluating points placed near the center, approximating the bisection method. With LaTeX: \varepsilon being a small positive value, let LaTeX: x = (a+b)/2 - \varepsilon and LaTeX: y = (a+b)/2 + \varepsilon. Then, if LaTeX: f(x) < f(y), the new interval of uncertainty is LaTeX: (x, b); if LaTeX: f(x) > f(y), it is LaTeX: (a, y); if LaTeX: f(x) = f(y), it is LaTeX: (x, y). With LaTeX: N=2M function evaluations, the interval of uncertainty can be reduced to within LaTeX: (b-a)r, where

LaTeX: r = 2^{-M} + [1 - 2^{-M}]\varepsilon .

The same reduction occurs with LaTeX: N=2M+1, as an even number of evaluations is required. For example, with LaTeX: N=20, LaTeX: 2^{-10}=0.0009765, so the interval reduction is LaTeX: 0.0009765 + 0.999756\varepsilon. See fibonacci search   for a more efficient method.

Personal tools