Golden-section search

The golden-section search is a technique for locating the minimum or maximum of a function inside a chosen interval. It suits a strictly unimodal function, where it narrows the interval step by step until the extremum is trapped; if the interval holds several extrema it converges to one of them, and if the only extremum sits on an edge it converges to that edge. Each step keeps function values at four points whose three interval widths stay in the ratio of the golden ratio to one to the golden ratio, which is where the name comes from and which makes the reuse of earlier evaluations as efficient as possible. Because it only shrinks the range it is relatively slow, but it is very robust. It is the limit of Fibonacci search for many evaluations, and both were discovered by Kiefer in 1953.