1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user6014 Oct 16 '18 at 1:10
  • $\begingroup$ 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. $\endgroup$ – Hypergeometry Oct 16 '18 at 1:39
  • 1
    $\begingroup$ I believe you'd want While[Abs[(b - (b - a)/phi) - (a + (b - a)/phi)] > Res && k < n, ...]. (didn't test it myself) $\endgroup$ – user6014 Oct 16 '18 at 1:40
  • 1
    $\begingroup$ The bulk of Mathematica's core is written in C, so you'll notice a lot of similarities :) $\endgroup$ – user6014 Oct 16 '18 at 1:57
  • 1
    $\begingroup$ The value of phi is built in as GoldenRatio $\endgroup$ – Bob Hanlon Oct 16 '18 at 4:55
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.