Monday, February 1, 2010

Golden Ratio

The function [Graphics:Images/GoldenRatioSearchMod_gr_4.gif] is unimodal on [Graphics:Images/GoldenRatioSearchMod_gr_5.gif], if there exists a unique number [Graphics:Images/GoldenRatioSearchMod_gr_6.gif] such that

[Graphics:Images/GoldenRatioSearchMod_gr_7.gif] is decreasing on [Graphics:Images/GoldenRatioSearchMod_gr_8.gif],
and
[Graphics:Images/GoldenRatioSearchMod_gr_9.gif] is increasing on [Graphics:Images/GoldenRatioSearchMod_gr_10.gif].

Golden Ratio:

If [Graphics:Images/GoldenRatioSearchMod_gr_11.gif] is known to be unimodal on [Graphics:Images/GoldenRatioSearchMod_gr_12.gif], then it is possible to replace the interval with a subinterval on which [Graphics:Images/GoldenRatioSearchMod_gr_13.gif] takes on its minimum value. One approach is to select two interior points [Graphics:Images/GoldenRatioSearchMod_gr_14.gif]. This results in [Graphics:Images/GoldenRatioSearchMod_gr_15.gif]. The condition that [Graphics:Images/GoldenRatioSearchMod_gr_16.gif] is unimodal guarantees that the function values [Graphics:Images/GoldenRatioSearchMod_gr_17.gif] and [Graphics:Images/GoldenRatioSearchMod_gr_18.gif] are less than [Graphics:Images/GoldenRatioSearchMod_gr_19.gif].
If [Graphics:Images/GoldenRatioSearchMod_gr_20.gif], then the minimum must occur in the subinterval [Graphics:Images/GoldenRatioSearchMod_gr_21.gif], and we replace b with d and continue the search in the new subinterval [Graphics:Images/GoldenRatioSearchMod_gr_22.gif]. If [Graphics:Images/GoldenRatioSearchMod_gr_23.gif], then the minimum must occur in the subinterval [Graphics:Images/GoldenRatioSearchMod_gr_24.gif], and we replace a with c and continue the search in the new subinterval [Graphics:Images/GoldenRatioSearchMod_gr_25.gif]. These choices are shown in Figure 1 below.


[Graphics:Images/GoldenRatioSearchMod_gr_26.gif]

If [Graphics:Images/GoldenRatioSearchMod_gr_28.gif], then squeeze from the right and use the

new interval [Graphics:Images/GoldenRatioSearchMod_gr_30.gif] and the four points [Graphics:Images/GoldenRatioSearchMod_gr_31.gif].

[Graphics:Images/GoldenRatioSearchMod_gr_27.gif]

If [Graphics:Images/GoldenRatioSearchMod_gr_29.gif], then squeeze from the left and use the

new interval [Graphics:Images/GoldenRatioSearchMod_gr_32.gif] and the four points [Graphics:Images/GoldenRatioSearchMod_gr_33.gif].

Figure 1. The decision process for the golden ratio search.

The interior points c and d of the original interval [Graphics:Images/GoldenRatioSearchMod_gr_34.gif], must be constructed so that the resulting intervals [Graphics:Images/GoldenRatioSearchMod_gr_35.gif], and [Graphics:Images/GoldenRatioSearchMod_gr_36.gif] are symmetrical in [Graphics:Images/GoldenRatioSearchMod_gr_37.gif]. This requires that [Graphics:Images/GoldenRatioSearchMod_gr_38.gif], and produces the two equations


(1)
[Graphics:Images/GoldenRatioSearchMod_gr_39.gif],
and
(2)
[Graphics:Images/GoldenRatioSearchMod_gr_40.gif],

where [Graphics:Images/GoldenRatioSearchMod_gr_41.gif] (to preserve the ordering [Graphics:Images/GoldenRatioSearchMod_gr_42.gif]).

We want the value of r to remain constant on each subinterval. If r is chosen judicially then only one new point e (shown in green in Figure 1) needs to be constructed for the next iteration. Additionally, one of the old interior points (either c or d) will be used as an interior point of the next subinterval, while the other interior point (d or c) will become an endpoint of the next subinterval in the iteration process. Thus, for each iteration only one new point e will have to be constructed and only one new function evaluation [Graphics:Images/GoldenRatioSearchMod_gr_43.gif], will have to be made. As a consequence, this means that the value r must be chosen carefully to split the interval of [Graphics:Images/GoldenRatioSearchMod_gr_44.gif] into subintervals which have the following ratios:


(3)
[Graphics:Images/GoldenRatioSearchMod_gr_45.gif] and [Graphics:Images/GoldenRatioSearchMod_gr_46.gif],
and
(4)
[Graphics:Images/GoldenRatioSearchMod_gr_47.gif] and [Graphics:Images/GoldenRatioSearchMod_gr_48.gif].

If [Graphics:Images/GoldenRatioSearchMod_gr_49.gif] and only one new function evaluation is to be made in the interval [Graphics:Images/GoldenRatioSearchMod_gr_50.gif], then we must have

[Graphics:Images/GoldenRatioSearchMod_gr_51.gif].

Use the facts in (3) and (4) to rewrite this equation and then simplify.

[Graphics:Images/GoldenRatioSearchMod_gr_52.gif],

[Graphics:Images/GoldenRatioSearchMod_gr_53.gif],

[Graphics:Images/GoldenRatioSearchMod_gr_54.gif],

[Graphics:Images/GoldenRatioSearchMod_gr_55.gif].

Now the quadratic equation can be applied and we get

[Graphics:Images/GoldenRatioSearchMod_gr_56.gif].

The value we seek is [Graphics:Images/GoldenRatioSearchMod_gr_57.gif] and it is often referred to as the "golden ratio." Similarly, if [Graphics:Images/GoldenRatioSearchMod_gr_58.gif], then it can be shown that [Graphics:Images/GoldenRatioSearchMod_gr_59.gif].

No comments:

Post a Comment

Introductory Methods of Numerical Analysis