Nonlinear Opt.: Gold section search 3

Index of contents

1. Theory

2. Mathematical formulation

3. Example for maximum

4. Sources

Theory

Golden section search is a part of unconstrained nonlinear optimization for strictly unimodal functions. This method is used to find a minimum or maximum by narrowing values in a specific interval. The extrema exists in the range. Based on the unimodal function, we assume that the local extrema is simultaneously the global extrema. In this method we do not use derivation, but rather a "step-by-step" approximation to the extrema.

Mathematical formulation (for maximum)

The method of the golden section search has the function Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f:\mathbb{R}^{n} \supseteq X \rightarrow \mathbb{R}^{n}

based on an interval (a₀,b₀), where “a” is smaller than ”b”. A termination tolerance of ε is given, with the objective ε to compare the distance between “a” and “b” in each iteration. Through each iteration, the interval will be diminished by the factor λ, which is given with the value 0,618. λ will be cut from the bigger part of the interval. k = n represents the iteration steps.

Step 0: Initialization

Set a₀ := a, b₀:= b, k := 0

       Calculate λk := ak + (1 – δ) * (bk – ak)
       and µk := ak + δ * (bk – ak)
       as well as f(λk) and f(µk)

Step1: Compare the distance with the termination tolerance. If the distance is smaller than the termination tolerance, stop the iteration, because the maximum has been reached.

If b_k – a_k < ε, then STOP.

Step 2: Compare the distance with the termination tolerance. If the distance is greater than the termination tolerance, continue with the following two cases:

Case a)

      If f(λk) < f(µk), 
      set ak+1 := λk,
      bk+1 := bk, 
      λk+1 := µk, 
      µk+1 := ak+1 + δ * (bk+1 – ak+1), 
      f(λk+1) := f(µk), 
      and compute f(µk+1)

the interval will be diminished from the right side

Case b)

      If f(λk) ≥ f(µk),
      set ak+1 := ak,
      bk+1 := µk,
      µk+1 := λk,
      λk+1 := ak+1 + (1 – δ) * (bk+1 – ak+1),
      f(µk+1) := f(λk),
      compute f(λk+1)
      set k = k+1, go to Step 1.

the interval will be diminished from the left side

The result is:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

figure 1: interval demonstration of the two possibilities

Example for maximum

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): max f(x)= -(x^{2})+ 4x + 2

where x ϵ $\mathbb {R}$ on interval [0, 5], termination tolerance ε = 0,8

Step 0:

a₀ and b₀ are the margins of the interval

        a0 := 0 ; b0 := 5 

k represents the iteration steps

        k := 0 

Compute λ_k with the formula:

        λk := ak + (1 – δ) * (bk – ak)
        λ0 := 0 + (1 – 0,618) * (5 – 0) 
        => λ0 = 1,91 

and then µ₀ with the formula:

        µk := ak + δ * (bk – ak)
        µ0 := 0 + 0,618 * (5 – 0) 
        => µ0 = 3,09

λ₀ := 0 + (1 – 0,618) * (5 – 0) => λ₀ = 1,91

µ₀ := 0 + 0,618 * (5 – 0) => µ₀ = 3,09

Afterwards we compute λ_k and µ₀ we insert, in succession, λ₀ and µ₀ in the start function f(x) to get a result for f(λ₀) and f(µ₀).

        Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(\lambda _{0})= -(1,91 ^{2})+ 4 * 1,91  + 2 

        f(λ0) = 5,9919

        Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(\mu _{0})= -(3,09 ^{2})+ 4 * 3,09  + 2

        f(µ0) = 4,8119