Skip to the content of the web site.

11.1 Golden-mean Search

Introduction Theory HOWTO Error Analysis Examples Questions Applications in Engineering Matlab Maple

Introduction

The golden-mean search is simple, robust, and straight-forward: take an interval [a, b] such that it is known that there is a minimum on the interval. Select two points on the interval, a < c1 < c2 < b, and compare f(c1) and f(c2) to determine whether the root lies on [a, c2] or [c1, b].

Repeat until the interval is sufficiently small.

Background

Useful background for this topic includes:

References

  • Mathews, Section 8.1, Golden Ratio Search, p.411.

Theory

Given a continuous real-valued function f(x) of a single variable, let us assume that a minimum exists on that interval.

Unlike the bisection method where we selected a single point on the interval [a, b], we cannot use just one point to help us find a minimum. For example, consider the two functions in Figures 1 and 2. Each evaluates to the same points at (1, 4), (2, 1) and (3, 3), but Figure 1 has a minimum on the left-hand sub-interval and Figure 2 has a minimum on the right-hand subinterval.

Figure 1. Function with a minimum on [1, 2].

Figure 2. Function with a minimum on [2, 3].

If, however, we divide the interval into three by choosing two interior points, for example, c1 = 1.666⋅⋅⋅ and 2.333⋅⋅⋅, then we may use the relative differences between these two points to determine whether the minimum is on the left sub-interval [1, 2.333⋅⋅⋅] (Figure 3) or the right sub-interval [1.666⋅⋅⋅, 3] (Figure 4).

Figure 3. Finding the minimum of Figure 1 on the sub-interval [1, 2.333⋅⋅⋅].

Figure 4. Finding the minimum of Figure 2 on the sub-interval [1.666⋅⋅⋅, 3].

Choosing the Interior Points

In the above example, we choose the points:

  • c1 = 2/3 a + 1/3 b, and
  • c2 = 1/3 a + 2/3 b.

Therefore, the width of the sub-interval is 2/3 (ba).

We can generalize the choice of interior points by choosing λ ∈ (1/2, 1), in which case, we can define

  • c1 = λ a + (1 − λ) b, and
  • c2 = (1 − λ) a + λ b.

In our first case, we choose λ = 2/3.

If the width of the interval is b − a, then the width of either sub-interval [a, c2] or [c1, b] is λ(ba).

Let us experiment with our choice of λ = 2/3. Let us assume that the minimum always occurs at the left sub-interval, starting with the interval [0, 1]. This is shown in Table 1.

Table 1. Subdividing [0, 1] using λ = 2/3.

ac1c2b
01/32/31
02/94/92/3
04/278/274/9
08/8116/818/27

Note that at each step, we introduce two new points at which we must evaluate the function: first we evaluate f(1/3) and f(2/3), then f(2/9) and f(4/9), then f(4/27) and f(8/27), and finally f(8/81) and f(16/81). Also note that we never use the calculation of f(1/3) again after the first step.

If, however, we use λ = φ − 1 ≈ 0.6180, then we have the pattern shown in Table 2.

Table 2. Subdividing [0, 1] using λ = φ − 1 ≈ 0.6180.

ac1c2b
00.38200.61801
00.23610.38200.6180
00.14590.23610.3820
00.09020.14590.2361

In this case, note how one interior point becomes the opposite interior point at the next iteration. Thus, as well as having faster convergence (φ - 1 < 2/3), we require only half the number of function evaluations.

Proof

To prove that this is the case, recall that φ-2 = 1 − φ-1. Thus, let us begin with a general interval [a, b]. Choosing the interior points based on λ = φ-1, we get the two interior points:

Case 1

Suppose we determine that the minimum lies in the interval [a, (2 − &phi)a + (φ − 1)b]. If we subdivide this new interval into three sub-intervals using λ = 1 − φ, we get

If we expand both of these interior points and use the fact that φ2 = φ + 1, we get the values:

Thus we note that the second point is the first point in our initial subdivision.

Case 2

Suppose we determine that the minimum lies in the interval [(φ − 1)a + (2 − φ)b, b]. If we subdivide this new interval into three sub-intervals using λ = 1 − φ, we get:

If we expand both of these interior points and use the fact that φ2 = φ + 1, we get the values:

Thus we note that the first point is the second point in our initial subdivision.

Therefore, we conclude in either case, we may always use on of the previous values in calculating the next.

HOWTO

Problem

Given a function of one variable, f(x), find a local minima of that function.

Assumptions

We will assume that the function f(x) is continuous.

Tools

We will use sampling, bracketing, and iteration.

Initial Requirements

We have an initial bound [a, b] on the minima.

Iteration Process

Given the interval [a, b], define c1 = (φ − 1)a + (2 − φ)b and c2 = (2 − φ)a + (φ − 1)b. Then

  • if f(c1) = f(c2), then halt, as we cannot continue searching,
  • if f(c1) < f(c2) then the minima must lie on [a, c2], so assign b = c2,
  • else f(c1) > f(c2) and the minimum must lie on [c1, b], so assign a = c1.

Halting Conditions

There are two conditions which may cause the iteration process to halt:

  1. We halt if the width of the interval (after the assignment) is sufficiently small, that is b - a < εstep,
  2. If f(c1) = f(c2), in which case, we cannot choose the next sub-interval.

If we halt due to Condition 1, we choose the point which has the minimum function value.

If we halt due to Condition 2, then we have to choose different initial points.

Error Analysis

If the width of the interval is h = b - a, then the width of the interval after one iteration is φ-1 h ≈ 0.618 h.

You may wish to recall that φ is defined as:

and it happens that φ-1 = φ - 1 is given by:

For example, if the initial interval is of width 1, then the width after 19 iterations is still approximately 0.0001.

Examples

Example 1

Find an approximation to the minimum of f(x) = x(x − 1) starting with the interval [0, 2] and iterate until the width of the interval is less than 0.1

.

Table 1. The golden-mean search applied to f(x) = x(x − 1).

a b c1 c2 f(c1) f(c2) Update b − a
020.763931.2361-0.180340.29180b = c21.2
01.23610.472140.76393-0.24922-0.18034b = c20.76
00.763930.291800.47214-0.20665-0.24922a = c10.47
0.291800.763930.472140.58359-0.24924-0.24301b = c20.29
0.291800.583590.403250.47214-0.24064-0.24922a = c10.18
0.403250.583590.472140.51471-0.24922-0.24978a = c10.11
0.472140.583590.514710.54102-0.24978-0.24832b = c20.06

In this case, we note that f(a), f(c1), f(c2), and f(b) are -0.2492235, -0.2499975, -0.2497836, and -0.2483173, and therefore we choose c1 = 0.49844 to be the approximation of the minimum.

Questions

Question 1

Using Matlab, use the golden-mean search to find a minimum of f(x) = x2 starting with the interval [-1, 2] and use εstep = 0.1 and εabs = 0.1 .

Answer: the last points are [-0.0212862, 0.0031056, 0.0181806, 0.0425725] and thus we use 0.0031056.

Question 2

Suppose you began with an interval of width h. How many iterations would be required to get the width less than ε?

Answer: ⌈logφ - 1( ε/h )⌉.

Applications to Engineering

To be completed.

Matlab

The golden-mean search in Matlab is quite straight-forward. Assume a file f.m with contents

function y = f(x)
   y = cos(x)

exists. Then:

>> phi = (sqrt(5) + 1)/2;
>> a = 0;
>> b = 4;
>> eps_step = 1e-2;
>> c1 = (phi - 1)*a + (2 - phi)*b;
>> c2 = (2 - phi)*a + (phi - 1)*b;
>> for i=1:100
    if ( f( c1 ) < f( c2 ) )
      b = c2;
      c2 = c1;
      c1 = (phi - 1)*a + (2 - phi)*b;
    else
      a = c1;
      c1 = c2;
      c2 = (2 - phi)*a + (phi - 1)*b;
    end

    if ( (b - a) < eps_step )
        break;
    elseif i == 100 
        error( 'unable to find minimum' );
    end
end
>> pts = [a c1 c2 b];
>> fpts = f( [a c1 c2 b] );
>> format long
>> [minima, posn] = min( fpts )
minima = -0.999999741074561
posn = 3
>> pts( posn )
ans = 3.14087303500967

exists. Then:




Maple

The golden-mean search in Maple is quite straight-forward:

> a := 0.0:
> b := 2.0:
> f := x -> x*(x - 1):
> epsilon[step] := 0.1:
> phi := (sqrt(5.) - 1)/2:
> for i from 1 to 100 do
     c[1] := phi*a + (1 - phi)*b;
     c[2] := (1 - phi)*a + phi*b;
  
     if f(c[1]) < f(c[2]) then
        b := c[2];
        c[2] := c[1];
        c[1] := phi*a + (1 - phi)*b;
     else
        a := c[1];
        c[1] := c[2];
        c[2] := (1 - phi)*a + phi*b;
     end if;
  
     if b - a < epsilon[step] then
        break;
     end if;
  end do:
> a, c[1], c[2], b;
        0.4721359542, 0.4984471891, 0.5147084265, 0.5410196611

> f(a), f(c[1]), f(c[2]), f(b);
      -0.2492235950, -0.2499975888, -0.2497836622, -0.2483173874