The Golden Ratio Search for a Minimum


Bracketing Search Methods

An approach for finding the minimum of  [Graphics:Images/GoldenRatioSearchMod_gr_1.gif]  in a given interval is to evaluate the function many times and search for a local minimum.  To reduce the number of function evaluations it is important to have a good strategy for determining where  [Graphics:Images/GoldenRatioSearchMod_gr_2.gif]  is to be evaluated.  Two efficient bracketing methods are the golden ratio and Fibonacci searches.  To use either bracketing method for finding the minimum of  [Graphics:Images/GoldenRatioSearchMod_gr_3.gif],  a special condition must be met to ensure that there is a proper minimum in the given interval.

Definition (Unimodal Function)  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],  
[Graphics:Images/GoldenRatioSearchMod_gr_9.gif]  is increasing on  [Graphics:Images/GoldenRatioSearchMod_gr_10.gif].  

Golden Ratio Search

    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]                              [Graphics:Images/GoldenRatioSearchMod_gr_27.gif]

[Graphics:Images/GoldenRatioSearchMod_gr_28.gif], then squeeze from the right and use the                       If [Graphics:Images/GoldenRatioSearchMod_gr_29.gif], then squeeze from the left and use the
new interval [Graphics:Images/GoldenRatioSearchMod_gr_30.gif] and the four points  [Graphics:Images/GoldenRatioSearchMod_gr_31.gif].                      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  


    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:

[Graphics:Images/GoldenRatioSearchMod_gr_45.gif]    and    [Graphics:Images/GoldenRatioSearchMod_gr_46.gif],  
[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


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





Now the quadratic equation can be applied and we get  


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].  

Proof  Golden Ratio Search  Golden Ratio Search  


Algorithm (Golden Ratio Search for a Minimum).  To numerically approximate the minimum of  [Graphics:Images/GoldenRatioSearchMod_gr_60.gif]  on the interval  [Graphics:Images/GoldenRatioSearchMod_gr_61.gif]  by using a golden ratio search.  Proceed with the method only if  [Graphics:Images/GoldenRatioSearchMod_gr_62.gif]  is a unimodal function on the interval  [Graphics:Images/GoldenRatioSearchMod_gr_63.gif].  Terminate the process after  max iterations have been completed.  

Computer Programs  Golden Ratio Search   Golden Ratio Search  


Mathematica Subroutine (Golden Ratio Search for a Minimum).


The next example compares the secant method for root-finding with the golden ratio search method.  


Algorithm (Secant Method).  Find a root of  [Graphics:Images/GoldenRatioSearchMod_gr_65.gif]  given two initial approximations  [Graphics:Images/GoldenRatioSearchMod_gr_66.gif]  using the iteration  

    [Graphics:Images/GoldenRatioSearchMod_gr_67.gif]   for    [Graphics:Images/GoldenRatioSearchMod_gr_68.gif].

Computer Programs  Secant Method  Secant Method  

Mathematica Subroutine (Secant Method).


Example 1. Find the minimum of the unimodal function  [Graphics:Images/GoldenRatioSearchMod_gr_70.gif]  on the interval  [Graphics:Images/GoldenRatioSearchMod_gr_71.gif].  
Solution 1.


The following changes can be made in the golden ratio search subroutine so that it can try to determine the minimum with desired accuracy [Graphics:Images/GoldenRatioSearchMod_gr_132.gif] for the abscissa and ordinate, respectively.  

Algorithm (Golden Ratio Search for a Minimum).  To numerically approximate the minimum of  [Graphics:Images/GoldenRatioSearchMod_gr_133.gif]  on the interval  [Graphics:Images/GoldenRatioSearchMod_gr_134.gif]  by using a golden ratio search.  Proceed with the method only if  [Graphics:Images/GoldenRatioSearchMod_gr_135.gif]  is a unimodal function on the interval  [Graphics:Images/GoldenRatioSearchMod_gr_136.gif].  Terminate the iteration when we have achieved either  [Graphics:Images/GoldenRatioSearchMod_gr_137.gif]  or  [Graphics:Images/GoldenRatioSearchMod_gr_138.gif].  

Mathematica Subroutine (Golden Ratio Search for a Minimum).


Example 2.  Find the local minimum of the function  [Graphics:Images/GoldenRatioSearchMod_gr_140.gif]  over  [Graphics:Images/GoldenRatioSearchMod_gr_141.gif].
Solution 2.


Example 3.  Find the local maximum of the function  [Graphics:Images/GoldenRatioSearchMod_gr_152.gif]  in the interval  [Graphics:Images/GoldenRatioSearchMod_gr_153.gif].
Solution 3.


Exercise 4.  Find the maximum of the function  [Graphics:Images/GoldenRatioSearchMod_gr_177.gif]  for  [Graphics:Images/GoldenRatioSearchMod_gr_178.gif].  Use the Golden Ratio Search.  
Solution 4.


Exercise 5.  The voltage input to an electrical component is  [Graphics:Images/GoldenRatioSearchMod_gr_203.gif]  for  [Graphics:Images/GoldenRatioSearchMod_gr_204.gif].  The manufacturer states that the voltage is not to exceed  [Graphics:Images/GoldenRatioSearchMod_gr_205.gif] or else the component will "burn out."  Can we expect that the component will be o.k. or will it  "burn out."  
Solution 5.


Various Scenarios and Animations for the Secant Method.


Example 6. Find the minimum of  [Graphics:Images/GoldenRatioSearchMod_gr_223.gif]  on the interval  [Graphics:Images/GoldenRatioSearchMod_gr_224.gif].  
Solution 6.


Animations (Golden Ratio Search  Golden Ratio Search).  Internet hyperlinks to animations.

Research Experience for Undergraduates

Golden Ratio Search  Golden Ratio Search  Internet hyperlinks to web sites and a bibliography of articles.  


Download this Mathematica Notebook The Golden Ratio Search




















(c) John H. Mathews 2004