# Golden section search method that terminate after $n$ iterations

I am attempting to code a program that executes the golden section search method and I would like to terminate the computations after $$n$$ iterations, where the user decides what $$n$$ is. My code works and finds the solution, it just refuses to terminate until the other termination condition is met.

Upon investigation, I discovered that unlike the Fibonacci Search method, this method is independent of $$n$$; in essence, $$n$$ did not matter.

Here is my code: (I appreciate edits to make it look better)

GoldenSearch[lower_, upper_, iterations_] :=
Module[{a = N[lower], b = N[upper], n = iterations}, k = 0;
Print["Iteration Results are:"];
While[Abs[(b - (b - a)/phi) - (a + (b - a)/phi)] > Res,
c = (b - (b - a)/phi);
d = (a + (b - a)/phi);
If[G[c] < G[d],(*Then*)b = d;(*Else*)k = k + 1;,
a = c;
Print[{"Lowerbound at iteration...", k, PaddedForm[a, {7, 6}]}];
Print[{"Upperbound at iteration...", k, PaddedForm[b, {7, 6}]}];
k++;]]];


It is clear that n does not appear anywhere else besides the Module function.

Here is some information on the variables and the function G:

• G[x_]: function being evaluated.
• phi: Golden Ratio = 1.61803...
• a & b: Lower and upper bounds
• Res: Resolution, I set it at 10^-4

Any help is appreciated.

• So you're concerned that it doesn't actually terminate after n iterations? If so, I don't see a k<=n in your While loop, for a start. – user6014 Oct 16 '18 at 1:10
• Yeah, I don't. Would it work if I just added ",<=n" after the absolute value stuff? I was thinking of putting in another IF statement. Sorry if this sounds silly, I am extremely bad at coding. – Hypergeometry Oct 16 '18 at 1:39
• I believe you'd want While[Abs[(b - (b - a)/phi) - (a + (b - a)/phi)] > Res && k < n, ...]. (didn't test it myself) – user6014 Oct 16 '18 at 1:40
• The bulk of Mathematica's core is written in C, so you'll notice a lot of similarities :) – user6014 Oct 16 '18 at 1:57
• The value of phi is built in as GoldenRatio – Bob Hanlon Oct 16 '18 at 4:55

Just for reference, I'll present a pretty traditional implementation of golden section search. I'll use Newton's cubic $$x^3-2x-5$$ as the example function, minimized over $$[-1,2]$$:

f[x_] := x^3 - 2 x - 5
a = N[-1]; b = N[2];


GoldenRatio is built-in, so let's use that for making the needed constants:

{ψ, ϕ} = {1 - 1/GoldenRatio, 1/GoldenRatio} // N;


Set up the tolerance and the maximum number of iterations:

tol = 1.*^-4; kmax = 10;


Starting conditions:

m1 = Rescale[ψ, {0, 1}, {a, b}];
m2 = Rescale[ϕ, {0, 1}, {a, b}];
f1 = f[m1]; f2 = f[m2]; k = 0;


Finally, the main search:

While[Abs[b - a] > tol (Abs[m1] + Abs[m2]) && k < kmax, k = k + 1;
If[f1 < f2,
b = m2; m2 = m1; m1 = ψ a + ϕ m2;
f2 = f1; f1 = f[m1],
a = m1; m1 = m2; m2 = ϕ m1 + ψ b;
f1 = f2; f2 = f[m2]];
Print[{k, a, m1, m2, b}]];


which should yield {a, m1, m2, b} = {0.805318, 0.814635, 0.820393, 0.82971} when it finishes, and print the values along the way. If you want to get even more fancy, you can use Plot[] with Epilog to see how these points move along. If you want to compare with the built-in minimizer, you can also do FindArgMin[f[x], {x, 1}][[1]].

I'll leave the encapsulation into a routine up to you.

• Very neat and easily understandable! The plots would be a neat addition. – Hypergeometry Nov 1 '18 at 4:46