Fibonacci Search in Optimization of Unimodal Functionsby Dr. William P. Fox, Department of Mathematics Francis Marion University, Florence, SC 29501, wfox@fmarion.edu (c) 2002 William P. FoxThis program performs the Fibonacci Line Search algorithm to find the maximum of a unimodal function, f(x), over an interval, a< x < b. The program calculates the number of iterations required to insure the final interval is within the user-specified tolerance. This is found by solving for the smallest value of n that makes this inequality true: Fn >(b-a)/tolerance, where n is the Fibonacci number from the sequence {F0,F1, F2, ...}. The Fibonacci search concept involves placing two experiments between [a,b] using the ratios of Fibonacci numbers. (The limit of the ratio of Fibonacci numbers is the golden section 0.618 but the Fibonacci method converges quicker.) One experiment is placed at position, NiMsJiUiYUciIiIqKC0lIkZHNiMsKCUibkdGJSUia0chIiIiIiNGLUYlLUYoNiMsJkYrRiVGLEYtRi0sJiUiYkdGJUYkRi1GJUYl, and the other at position, NiMsJiUiYUciIiIqKC0lIkZHNiMsKCUibkdGJSUia0chIiJGJUYtRiUtRig2IywmRitGJUYsRi1GLSwmJSJiR0YlRiRGLUYlRiU=. The function, to be maximized, is evaluated at these two points and the functional values are compared. We want to keep the larger functional value (in our maximization problem) and its corresponding opposite end -point. At the end of the required iterations, the final interval is the answer. At times when the final answer must be a single point and not an interval, the convention of selecting the midpoint is provided. This program works when the function is not differentiable and we are looking for a solution. If you need to minimize a function, then multiple the function by (-1) and find the maximum. To find a maximum solution to given a function, f(x), on the interval [a, b] where the function, f(x), is unimodal.

INPUT: endpoints a, b; tolerance, t, Fibonacci sequence OUTPUT: final interval [ai, bi], f(midpoint) Step 1. Initialize the tolerance, t >0. Step 2. Set Fn > (b-a)/t as the smallest Fn and define the test points NiMvJSN4MUcsJiUiYUciIiIqJiwmJSNGbkdGJyomIiIjRidGKiEiIkYtRicsJiUiYkdGJ0YmRi1GJ0Yn NiMvJSN4MkcsJiUiYUciIiIqJiwmJSNGbkdGJyomRidGJ0YqISIiRixGJyUiYkdGJ0Yn Step 3. Calculate f(x1) and f(x2) Step 4. Compare f(x1) and f(x2) (a.) If f(x1) < f(x2), then the new interval is [x1, b]: a becomes the previous x1 b does not change x1 becomes the previous x2 n = n-1 Find the new x2 using the formula in Step 2. (b.) If f(x1) > f(x2), then the new interval is [a, x2]: a does not change b becomes the previous x2 x2 becomes the previous x1 n = n-1 Find the new x1 using the formula in Step 2. Step 5. If the length of the new interval from Step 4 is less than the tolerance specified, the stop. Otherwise go back to Step 3. Step 6. Estimate x* as the midpoint of the final interval and compute, f(x*), the estimated maximum of the function. STOP To utilize the Fibonacci routine you need the following:User inputs are: The user enters the function f usingf:=x-><enter the expression in x>Type FIBSearch(f, a, b, tolerance) for specific values of a, b, and the tolerance.The output is the iterative process (each step).The last output provided is the midpoint of the final interval and the value of f(x) at that point.

FIBSearch:=proc(f::procedure,a::numeric,b::numeric,T::numeric) local L, M, j, C, x1, x2, N, val; L:=(b-a)/T; M:=round(L); j:=0; label_2; C:=fib(j); if C<L then j:=j+1; goto(label_2); else N:=j; end if; x1:=evalf(a+(fib(N-2)/fib(N))*(b-a)); x2:=evalf(a+(fib(N-1)/fib(N))*(b-a)); printf("The interval [a,b] is [% 4.2f,% 4.2f]and user specified tolerance level is% 6.5f.\n",a,b,T); ### WARNING: %x or %X format should be %y or %Y if used with floating point argumentsprintf("The first 2 experimental endpoints are x1= % 6.3f and x2 = % 6.3f. \n",x1,x2); printf(" \n"); printf(" \n"); printf(" Iteration x(1) x(2) f(x1) f(x2) Interval \n"); iterate(f,a,b,N,x1,x2); val:=f(mdpt); printf(" \n"); printf(" \n"); printf("The midpoint of the final interval is% 9.6f and f(midpoint) = % 7.3f. \n",mdpt, val); printf(" \n"); printf(" \n"); ### WARNING: %x or %X format should be %y or %Y if used with floating point arguments printf("The maximum of the function is % 7.3f and the x value = % 9.6f \n",fkeep,xkeep); printf(" \n"); printf(" \n"); end: iterate:=proc(f::procedure,a::numeric,b::numeric, N::posint,x1::numeric,x2::numeric) local x1n,x2n,an,bn,i,fx1,fx2,j,f1,f2,fmid; global mdpt,fkeep,xkeep,fib; i:=1; x1n(1):=x1; x2n(1):=x2; an(1):=a; bn(1):=b; i:=1; for j from 1 to N do fx1(i):=evalf(f(x1n(i))); fx2(i):=evalf(f(x2n(i))); if fx1(i)<=fx2(i) then an(i+1):=x1n(i); bn(i+1):=bn(i); x1n(i+1):=x2n(i); x2n(i+1):=an(i+1)+(fib(N-i-1)/fib(N-i))*(bn(i+1)-an(i+1)); else an(i+1):=an(i); bn(i+1):=x2n(i); x2n(i+1):=x1n(i); x1n(i+1):=an(i+1)+(fib(N-i-2)/fib(N-i))*(bn(i+1)-an(i+1)); fi; i:=i+1; printf(" % 3.0f % 11.4f % 10.4f % 10.4f %10.4f [% 6.4f, % 6.4f]\n",i,x1n(i),x2n(i),fx1(i-1),fx2(i-1),an(i),bn(i)); mdpt := (an(i) + bn(i))/2; if ((i+2)=N) then if evalf(f(an(i))) > evalf(f(bn(i))) or evalf(f(an(i))) > evalf(f(mdpt)) then fkeep := f(an(i)); xkeep := an(i); else if evalf(f(bn(i))) > evalf(f(mdpt)) then fkeep := f(bn(i)); xkeep := bn(i); else fkeep := f(mdpt); xkeep := mdpt; end if; end if; end if; if(N-i-2)<0 then: goto(label_3):end if; end do; label_3; end:fib:=proc(n::numeric) option rememer; fib(0):=1:fib(1):=1; if n<2 then n; else fib(n-1)+fib(n-2); end if; end:

Example 1Maximize the function f(x)=-x^2+21.6*x+3 over the interval [0,20].. Via calculus the maximum is at 10.8. Let's see how the Fibonacci Search does.f:= x->-x^2+21.6*x+3;FIBSearch(f,0,20,.001);Example 2 Maximize a function whose derivative can not be solved explictly for 0.Maximize the function, f(x) = x-exp(x) over the interval [-1,3].f:= x->x^2-exp(x);FIBSearch(f,0,3,.1);Example 3.Maximizing a function that does not have a derivative.f:= x->-(abs(2-x)+abs(5-4*x)+abs(8-9*x));FIBSearch(f,0,3,.1);Example 5.Minimize the function, NiMsJiomIiIjIiIiKiQlInhHRiVGJkYmKiYiIiVGJkYoRiYhIiI=. To minimize NiMtJSJmRzYjJSJ4Rw==, we maximize NiMvLCQtJSJmRzYjJSJ4RyEiIiwmKiYiIiMiIiIqJEYoRixGLUYpKiYiIiVGLUYoRi1GLQ==. We keep the interval the same.f:= x->-2*x^2+4*x;FIBSearch(f,-1,2,.1);f:=(x)->1-exp(-x)+1/(1+x); FIBSearch(f,0,20,.1);