Golden Ratio Search

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  .  

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.  

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    .

Mathematica Subroutine (Secant Method).