Nonlinear Opt.: Gold section search 3
Inhaltsverzeichnis
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 (a0,b0), 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 a0 := a, b0:= 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 bk – ak < ε, 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:
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 ϵ on interval [0, 5], termination tolerance ε = 0,8
Step 0:
a0 and b0 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 µ0 with the formula:
µk := ak + δ * (bk – ak)
µ0 := 0 + 0,618 * (5 – 0)
=> µ0 = 3,09
After having computed λk and µ0 we insert, in succession, λ0 and µ0 in the start function f(x) to get a result for f(λ0) and f(µ0).
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
Step 1:
We compare the difference between our interval values and our termination tolerance. If the difference is smaller, we stop our computation since the optimal output is reached, otherwise we start with the first iteration.
5 – 0 > 0,8 => no stop
Step 2:
Iteration k = 0:
Depending on whether f(λ0) < f(µ0) or f(λ0) > f(µ0), we use case a) or b) which are shown above in the mathematical formulation. In our example, we have f(λ0) > f(µ0), so we use case b). This means that our interval will be diminished from the right side. Our new b1 := b0 – λ0
a1 := 0
b1 := 3,09
µ1 := 1,91
λ1 := 0 + (1 – 0,618) * (3,09 – 0)
=> λ1 = 1,18038
f(µ1) := 5,9919
f(λ1) := 5,3282230556
go to Step 1
The other values will be computed with the formula: µ1 = λ0 and the remaining ones as shown above in the mathematical formulation for case b). Then we go to Step 1 and repeat as much iterations on the basis of the formulas above until our interval difference is smaller than our termination tolerance. Not until then, we have reached our optimal output.
Step 1:
3,09 – 0 > 0,8 => no stop
Step 2:
Iteration k=1:
f(λ1) < f(µ1) -> use case a)
a2 := 1,18038
b2 := b1 = 3,09
λ2 := µ1 = 1,91
µ2 := 1,18038 + 0,618 * (3,09 – 1,18038)
=> µ2 = 2,36052516
f(λ2) := 5,9919
f(µ2) := 5,870021609
Because of f(λ1) < f(µ1), we use case a) this time. We diminish our interval from the left side. So the value of a0 will change this time (a2 = λ1). Other values will be computed as usual.
Step 1:
3,09 – 1,18038 = 1,90962 > 0,8 => no stop
Because our termination tolerance is still bigger than our interval, we continue with the next iteration.
Step 2:
Iteration k=2:
f(λ2) > f(µ2) -> use case b)
a3 := a2 = 1,18038
b3 := µ2 =2,36052516
µ3 := λ2 = 1,91
λ3 := 1,18038 + (1 – 0,618) * (2,36052516 – 1,18038)
=> λ3 = 1,6311954511
f(µ3) := 5,9919
f(λ3) := 5,8639832047
Step 1:
2,36052516 – 1,18038 = 1,18014516 > 0,8 => no stop
Because our termination tolerance is still bigger than our interval, we continue with the next iteration.
Step 2:
Iteration k=3:
f(λ3) < f(µ3) -> use case a)
a4 := λ3 = 1,6311954511
b4 := b3 = 2,36052516
λ4 := µ3 = 1,91
µ4 := 1,6311954511 + 0,618 * (2,36052516 – 1,6311954511)
=> µ4 = 2,0819212112
f(λ4) := 5,9919
f(µ4) := 5,9932889152
Step 1:
2,36052516 - 1,6311954511 = 0,7293297089 < 0,8 => STOP
After the fourth iteration we have finally reached our optimal result/output because our termination tolerance is smaller than our interval.
OUTPUT: λ*=λ4=1,91
f(λ*)= 5,9919
Sources
- "http://www.cs.hs-rm.de/~weber/or/weber/orfolien5.pdf" / Aufruf 26. Juni 2013
- "http://mathforcollege.com/nm/mws/gen/09opt/mws_gen_opt_txt_goldensearch.pdf" / Aufruf 26. Juni 2013
- Prof. Dr. Oliver Wendt: Skript: Nonlinear Optimization - Operations Research SS13
Authors
362187
374701
377763
