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

1 Answer 1

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$
9
  • $\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, 2015 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$ Apr 23, 2015 at 10:27
  • $\begingroup$ What's the right answer? Is f(b) max/min of the function? $\endgroup$
    – Mahdi
    Apr 23, 2015 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$ Apr 25, 2015 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$ Apr 25, 2015 at 21:58

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.