Golden Ratio Search

Definitions:

Golden Ratio:
Unimodal Function	A function f (x) is unimodal on [a,b] if there exist a unique number p in [a,b] such that - f (x) is decreasing on [a,p] and increasing on [p,b] (for a minumum) or - f (x) is inreasing on [a,p] and decreasing on [p,b] (for a maximum)

If f (x) is known to be unimodal on [a,b], it is possible to replace the interval with a subinterval on which f (x) takes on its minimum (or maximum) value.

The golden search requires that two interior points

c = a + (r – 1) (b – a)

and

d = a + r (b – a)

be used where r is the golden ratio. This results in

a < c < d < b.

The condition that f (x) is unimodal guarantees that the functional values, f (c) and f (d), are less than max [ f (a),f (b)] when there is a minimum, or more than min [f (a),f (b)] when there is a maximum.

For the case when there is a minimum:

If f (c) £ f (d), then the minimum must occur in the subinterval [a,d] and we replace b with d and continue the search in the new subinterval. If f (d) < f (c), then the minimum must occur in [c,b] and we replace a with c and continue the search.

For the case when there is a maximum:

If f (c) ³ f (d), then the maximum must occur in the subinterval [a,d] and we replace b with d and continue the search in the new subinterval. If f (d) > f (c), then the maximum must occur in [c,b] and we replace a with c and continue the search.