Probe Point Selection
From the diagram above, it is seen that the new search interval will be either between and with a length of a+c, or between and with a length of b . The golden section search requires that these intervals be equal. If they are not, a run of "bad luck" could lead to the wider interval being used many times, thus slowing down the rate of convergence. To ensure that b = a+c, the algorithm should choose .
However there still remains the question of where should be placed in relation to and . The golden section search chooses the spacing between these points in such a way that these points have the same proportion of spacing as the subsequent triple or . By maintaining the same proportion of spacing throughout the algorithm, we avoid a situation in which is very close to or, and guarantee that the interval width shrinks by the same constant proportion in each step.
Mathematically, to ensure that the spacing after evaluating is proportional to the spacing prior to that evaluation, if is and our new triplet of points is, and then we want:
However, if is and our new triplet of points is, and then we want:
Eliminating c from these two simultaneous equations yields:
or
where φ is the golden ratio:
The appearance of the golden ratio in the proportional spacing of the evaluation points is how this search algorithm gets its name.
Read more about this topic: Golden Section Search
Famous quotes containing the words probe, point and/or selection:
“The middle years are ones in which children increasingly face conflicts on their own,... One of the truths to be faced by parents during this period is that they cannot do the work of living and relating for their children. They can be sounding boards and they can probe with the children the consequences of alternative actions.”
—Dorothy H. Cohen (20th century)
“I would rather produce my passions than brood over them at my expense; they grow languid when they have vent and expression. It is better that their point should operate outwardly than be turned against us.”
—Michel de Montaigne (1533–1592)
“Historians will have to face the fact that natural selection determined the evolution of cultures in the same manner as it did that of species.”
—Konrad Lorenz (1903–1989)