# 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
```
You will need a flag (integer or logical variable) to indicate whether the left or right sub-intervals are being kept.

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
```
At iteration 1 also evaluate f at x(3) = 0.5 ( x(1) + x(5) ).
Before entering the loop copy the upper bound to point 5, not point 4.

Course Organiser