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)
“Where there is no style, there is in effect no point of view. There is, essentially, no anger, no conviction, no self. Style is opinion, hung washing, the calibre of a bullet, teething beads.... One’s style holds one, thankfully, at bay from the enemies of it but not from the stupid crucifixions by those who must willfully misunderstand it.”
—Alexander Theroux (b. 1940)
“Judge Ginsburg’s selection should be a model—chosen on merit and not ideology, despite some naysaying, with little advance publicity. Her treatment could begin to overturn a terrible precedent: that is, that the most terrifying sentence among the accomplished in America has become, “Honey—the White House is on the phone.””
—Anna Quindlen (b. 1952)