How to find the minimum (or maximum) of a very complicated real-valued function $F(x)$ at the interval $A < x < B$ ,
that's the question (I think).
First select two points $(1)$ and $(2)$ at this interval in such a way that
$\,x_1 = A + L_1 (B-A)\,$ and $\,x_2 = A + L_2 (B-A)\,$ , with $\,0 < L_1 , L_2 < 1$ .
If $\,F(x_1) < F(x_2)\,$ then next search must be between $(A)$ and $(2)$
If $\,F(x_1) > F(x_2)\,$ then next search must be between $(1)$ and $(B)$
It is demanded that none of the points $(1,2)$ is to be preferred.
$$ x_2 = B + L_1 (A-B) = A + (1-L_1) (B-A) = A + L_2 (B-A)\\
\Longrightarrow \quad L_2 = 1-L_1$$
Also, in order to save work, points must be reusable.
Arrange for iteration $k$ in such a way that (two possibilities):
$$A(k+1) = A(k) \quad , \quad B(k+1) = x_2(k) \quad , \quad x_2(k+1) = x_1(k) \\
A(k+1) = x_1(k) \quad , \quad B(k+1) = B(k) \quad , \quad x_1(k+1) = x_2(k)$$
Take the first of these equations (the other gives same result):
$$ x_2(k+1) = x_1(k)\\
A(k+1) + L_2.[B(k+1) - A(k+1)] = A(k) + L_1.[B(k) - A(k)]\\
A(k) + L_2.[x_2(k) - A(k)] = A(k) + L_1.[B(k) - A(k)]\\
L_2.[A(k) + L_2.[B(k) - A(k)] - A(k)] = L_1.[B(k) - A(k)]\\
L_2.L_2.[B(k) - A(k)] = L_1.[B(k) - A(k)] \\
\Longrightarrow \quad L_2.L_2 = L_1$$
With $L_2 = 1-L_1$ and $L_1 < 1$ giving:
$$(1-L_1)^2 = L_1 \quad \Longrightarrow \quad L_1^2 - 3.L_1 + 1 = 0\\
\Longrightarrow \quad L_1 = (3 - \sqrt{5})/2
\quad \Longrightarrow \quad L_2 = (\sqrt{5} - 1)/2$$
Hence the name: Golden Rule Search.
Convergence behaviour is determined by:
$$B(k+1) - A(k+1) = x_2(k) - A(k) = A(k) + L_2 [B(k) - A(k)] - A(k)$$
Hence: $B(k+1) - A(k+1) = L_2.[B(k) - A(k)] = 0.618$ times smaller.
The biggest of the two roots determines convergence behavior.
Here is the algorithm (in Delphi Pascal) that implements the above theory.
The function returns the position $x$ of the minimum with an error $\pm \epsilon/2$ .
function Dal(A,B,eps : double; welke : funktie) : double;
{
(A,B) = interval to start with
eps = acceptable interval error
welke = your difficult function
}
var
een, twee, ga, gb, weg, eerste, tweede : double;
begin
{ The two Fibonacci numbers }
een := (3 - sqrt(5))/2; { = 0.381966... }
twee := (sqrt(5) - 1)/2; { = 0.618034... }
weg := B-A;
ga := A + een\*weg; gb := A + twee\*weg;
eerste := welke(ga); tweede := welke(gb);
while weg > eps do
begin
if eerste < tweede then
begin
B := gb; gb := ga;
tweede := eerste;
weg := B-A;
ga := A + een\*weg;
eerste := welke(ga);
Writeln(B);
end else begin
A := ga; ga := gb;
eerste := tweede;
weg := B-A;
gb := A + twee\*weg;
tweede := welke(gb);
Writeln(A);
end;
Readln;
end;
Dal := (A + B)/2;
end;
Disclaimer. My eyes are not good. Please pinpoint to any typos in the above, if necessary.