Bracketing Search Methods

    An approach for finding the minimum of    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    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  ,  a special condition must be met to ensure that there is a proper minimum in the given interval.

Definition (Unimodal Function)  The function    is unimodal on  ,  if there exists a unique number   such that  
    
          is decreasing on  ,  
    and
          is increasing on  .  

Golden Ratio Search

    If    is known to be unimodal on  ,  then it is possible to replace the interval with a subinterval on which    takes on its minimum value.  One approach is to select two interior points  .  This results in  .  The condition that    is unimodal guarantees that the function values and are less than  .  

    If  ,  then the minimum must occur in the subinterval , and we replace b with d and continue the search in the new subinterval .   If  , then the minimum must occur in the subinterval , and we replace a with c and continue the search in the new subinterval .  These choices are shown in Figure 1 below.  

If , then squeeze from the right and use the                       If , then squeeze from the left and use the
new interval and the four points  .                      new interval and the four points  .

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

    The interior points c and d of the original interval  ,  must be constructed so that the resulting intervals ,  and are symmetrical in  .   This requires that  ,  and produces the two equations  

(1)        ,  
    and
(2)        ,  

    where       (to preserve the ordering  ).

    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 , will have to be made.   As a consequence, this means that the value  r  must be chosen carefully to split the interval of into subintervals which have the following ratios:

(3)            and    ,  
    and
(4)            and    .  

If and only one new function evaluation is to be made in the interval , 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    and it is often referred to as the "golden ratio."   Similarly, if , then it can be shown that  .  

Proof  Golden Ratio Search  Golden Ratio Search  

Algorithm (Golden Ratio Search for a Minimum).  To numerically approximate the minimum of    on the interval    by using a golden ratio search.  Proceed with the method only if    is a unimodal function on the interval  .  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    given two initial approximations    using the iteration  

       for    .

Computer Programs  Secant Method  Secant Method  

Mathematica Subroutine (Secant Method).

Example 1. Find the minimum of the unimodal function    on the interval  .  
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 for the abscissa and ordinate, respectively.  

Algorithm (Golden Ratio Search for a Minimum).  To numerically approximate the minimum of    on the interval    by using a golden ratio search.  Proceed with the method only if    is a unimodal function on the interval  .  Terminate the iteration when we have achieved either    or  .  

Mathematica Subroutine (Golden Ratio Search for a Minimum).

Example 2.  Find the local minimum of the function    over  .
Solution 2.

Example 3.  Find the local maximum of the function    in the interval  .
Solution 3.

Exercise 4.  Find the maximum of the function    for  .  Use the Golden Ratio Search.  
Solution 4.

Exercise 5.  The voltage input to an electrical component is    for  .  The manufacturer states that the voltage is not to exceed   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    on the interval  .  
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