1
$\begingroup$

I am attempting to write a code to find to bracket the minimum of a function using the Fibonacci Line Search Method, I believe my code is well written but I am not receiving output values, could anyone help with this issue?

FibonacciSearch[a0_, b0_, eps_] :=
 Module[{a = N[a0], b = N[b0], c, d, k},
 n = 4;
 k = 0;
 F[1] = 1;
 F[2] = 1;
 F[3] = 2;
 F[4] = 3;
 F[5] = 5;
 F[6] = 8;
 F[7] = 13;
 F[8] = 21;
 F[9] = 34;
 F[10] = 55;
  While[(b[k] - a[k]) > eps,
   c[k_] := a[k] + (b[k] - a[k]) (1 - (F[n - k + 1])/(F[n - k + 2]));
   d[k_] := a[k] + (b[k] - a[k]) ((F[n - k + 1])/(F[n - k + 2]));
If[f[c[k_]] <= f[d[k_]],
    a[k + 1] = a[k];
    b[k + 1] = d[k];
    k = k + 1;,

    a[k + 1] = c[k];
    b[k + 1] = b[k];
    k = k + 1;
Print["f[", ToString[PaddedForm[{k, a[k], b[k]}, {7, 6}]], "]"]]]]

Example function to be evaluated:

 f[x_] := x^2 + 4*Cos[x]

Also, any tips to aide in my programming learning process will be appreciated.

$\endgroup$
  • 1
    $\begingroup$ Aren't a and b two numbers? If yes, a[k] and b[k] are wrong! $\endgroup$ – Mahdi Apr 23 '15 at 8:25
  • $\begingroup$ Also, my guess is Print should be done before k = k + 1. Am I right? $\endgroup$ – Mahdi Apr 23 '15 at 9:00
4
$\begingroup$

Your code has three major flaws:

  1. Since a, b , c , d are numbers you cannot pass the step k to them. This syntax is for functions.
  2. Print[k] should be used before changing the "the number of iterations" (k=k+1) .

  3. Your code does not allow enough iterations to bracket the minimum (n is small).

You may also use internal Fibonacci function, instead of manually enter values for F.

f[x_] := x^2 + 4*Cos[x];
FibonacciSearch[a0_, b0_, eps_] := Module[{a = N[a0], b = N[b0], n = 10}, 
k = 0;
While[(b - a) > eps,
     frac = (Fibonacci[n - k + 1])/(Fibonacci[n - k + 2]);
     c = a + (b - a) (1 - frac);
     d = a + (b - a)*frac;
       If[f[c] <= f[d], 
         b = d; k = k + 1;,
         a = c; Print[{k, PaddedForm[a, {7, 6}], PaddedForm[b, {7, 6}]}]; k = k + 1;]
 ]
];

Run it as:

FibonacciSearch[1, 2, 0.01]
(* {9, 1.893569, 1.901699} *)

Indeed f[x] has a minimum in the range $(1.893569, 1.901699)$,

enter image description here

$\endgroup$
  • $\begingroup$ I couldn't make it work, but it would be nice if we can pass f as a variable to the function to have FibonacciSearch[f, a0_, b0_, eps_]. $\endgroup$ – Mahdi Apr 23 '15 at 8:58
  • $\begingroup$ I used endpoints 1,2 with eps=0.05 and it came pretty close to being optimized, f[{ 5.000000, 1.750000, 1.875000}], I have a feeling it is wrong though $\endgroup$ – Rufus Mitchell Apr 23 '15 at 10:27
  • $\begingroup$ What's the right answer? Is f(b) max/min of the function? $\endgroup$ – Mahdi Apr 23 '15 at 19:11
  • $\begingroup$ Not exactly, I rewritting it right now, I believe it will with some minor adjustments. The program over shoots the minimuim $\endgroup$ – Rufus Mitchell Apr 25 '15 at 21:18
  • $\begingroup$ Here is the revision though, it still doesnt bracket the minimizer though, I ope you can see my logic though $\endgroup$ – Rufus Mitchell Apr 25 '15 at 21:58

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.