Section 5.3.2.2: Algorithm for Bounded Search: Golden Section

Given: 
         x_low     lower bound on minimum 
         x_high    upper bound on minimum 
         x_tol     tolerance for convergence in x 

and a procedure to evaluate f(x).

   Evaluate f_low = f(x_low) and f_high = f(x_high)
   Set iteration counter = 1;
   set x(1) = x_low, x(4) = x_high
       f(1) = f_low, f(4) = f_high

! Iteration loop
   Do (until converged)
       calculate length of interval: L = x(4) - x(1)
       if iteration 1 or we kept the left hand sub-intervals
        from previous iteration,    then
           set x(2) = x(1) + 0.381966 L; 
           calculate f(2) = f(x(2))
       end if
       if iteration 1 or we kept the right hand sub-intervals
        from previous iteration,    then
           set x(3) = x(4) - 0.381966 L; 
           calculate f(3) = f(x(3))
       end if

       find point i with minimum f(i); 
       set i_min = i with min f(i) ! i_min is best point so far

       if L is smaller than xtol
           declare convergence
       otherwise
           if i_min is 1 or 2 then 
                keep the left two sub-intervals (set a flag)
           end if
           if i_min is 3 or 4 then
                keep the right two sub-intervals (set a flag)
           end if

           if keeping the left sub-intervals
                copy point 3 to point 4; copy point 2 to point 3
           if keeping the right sub-intervals
                copy point 2 to point 1; copy point 3 to point 2
           !  `copy' means copy both x and f values.
           !  It is important to copy the points 
           !     in the stated order.
       end if

       if we have convergence 
           x_opt = x(i_min); f_opt = f(i_min) ! solves the problem
           exit from the iteration loop
       end if
   end do

Remark: The three equal interval and (to some extent) the four-equal interval methods are easier to implement.

For 3 interval copy only the points adjacent to i_min to x(1), f(1) and x(4), f(4). This sets up the next iteration, but we must always do two function evaluations at the head of the loop at

    x(2) = x(1) + 0.333333 L;       x(3) = x(4) - 0.333333 L

4 interval has 5 points in the current range. Provided i_min is an interior point (not x(1) or x(5)), copy point i_min to point 3, and the adjacent points to new bound points 1 and 5. At each iteration do two function evaluations at the head of the loop at

    x(2) = x(1) + 0.25 L;           x(4) = x(5) - 0.25 L

Return to Section 5.3.2
Return to Section 5.3 Index
Return to Section 5 Index