2
$\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$
6
  • 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$
    – ktm
    Oct 16, 2018 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$ Oct 16, 2018 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$
    – ktm
    Oct 16, 2018 at 1:40
  • 1
    $\begingroup$ The bulk of Mathematica's core is written in C, so you'll notice a lot of similarities :) $\endgroup$
    – ktm
    Oct 16, 2018 at 1:57
  • 1
    $\begingroup$ The value of phi is built in as GoldenRatio $\endgroup$
    – Bob Hanlon
    Oct 16, 2018 at 4:55

1 Answer 1

4
$\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$
1
  • $\begingroup$ Very neat and easily understandable! The plots would be a neat addition. $\endgroup$ Nov 1, 2018 at 4:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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