# Fibonacci Line Search Method

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.

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

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)$,

• 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_]. Commented Apr 23, 2015 at 8:58
• 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 Commented Apr 23, 2015 at 10:27
• What's the right answer? Is f(b) max/min of the function? Commented Apr 23, 2015 at 19:11
• Not exactly, I rewritting it right now, I believe it will with some minor adjustments. The program over shoots the minimuim Commented Apr 25, 2015 at 21:18
• Here is the revision though, it still doesnt bracket the minimizer though, I ope you can see my logic though Commented Apr 25, 2015 at 21:58