Golden Section Search - Probe Point Selection

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:

    Y’know scientists are funny. We probe and measure and dissect. Invent lights without heat, weigh a caterpillar’s eyebrow. But when it comes to really important things we’re as stupid as the caveman.... Like love. Makes the world go ‘round, but what do we know about it? Is it a fact? Is it chemistry? Electricity?
    Martin Berkeley, and Jack Arnold. Helen Dobson (Lori Nelson)

    Parents are led to believe that they must be consistent, that is, always respond to the same issue the same way. Consistency is good up to a point but your child also needs to understand context and subtlety . . . much of adult life is governed by context: what is appropriate in one setting is not appropriate in another; the way something is said may be more important than what is said. . . .
    Stanley I. Greenspan (20th century)

    The books for young people say a great deal about the selection of Friends; it is because they really have nothing to say about Friends. They mean associates and confidants merely.
    Henry David Thoreau (1817–1862)