Golden Search Algorithm in F#
Juan C LR May 18
I wrote the code for the Golden Search algorithm in python for one of my university classes, I really found this method interesting, so I decided to replicate this method in a functional programming language (F#). You may not be familiarized with this method, so let me give you a little introduction.
Lets start by defining what's a numerical method? A numerical method is a numerical method is a procedure by which you get, almost always the approximate solution of certain problems by performing purely arithmetic and logical calculations.
Now you may be asking yourself where does the Golden Search algorithm comes from? It's very interesting actually, since it comes from the Golden Ratio, you may have heard from the Golden Ratio but for those who haven't here it's a little background.
The golden ratio is a special number approximately equal to 1.618, it appears many times in geometry, art, architecture, even nature and it appears also in other areas.
With that being said the Golden Search algorithm is an algorithm used for finding the extremum (minimum or maximum, in this case minimum) for unimodal functions by successively narrowing the range of values inside which the extremum is known to exist.
So the Goal is to program the method in F# for a unimodal function "f" which range is [a,b], with x1<x2.
We want to simplify the algorithm, so we evaluate in this intervals:
- [a,x1) and (x2,b]
After that we evaluate x1 and x2 in our function f(x) which will give us the next to conditions:
- If f(x1) < f(x2), the new interval will be [a,x2]
- If f(x1) > f(x2), the new interval will be [x1,b]
To get our x1 and x2 we use R and (1 - R) (R=golden ratio value), to get the same relative position in the interval.
The equations to get x1 and x2 are:
- x1 = a + (1 - R)(b - a)
- x2 = a + R(b - a)
Generating the code
First of all we have to understand that this function is recursive, which means we will be doing some part of the process repeatedly.
This is how we begin:
- First we create a function for the f(x) that we will be using (in this case we will be using f(x) = 0.5 − xe−x2 ):
let funcion (x) :float = (0.5 - (x*(System.Math.E))**(((-1.0)*x)**(2.0)))
Define our variables in this case a = 0, b = 2 and R = (-1 + sqrt(5))/2, also x1 = a and x2 = b. We also create a variable for the counter which will keep track of how many iterations it will take to find the minimum.
Create the loop and the rest of the code will be within the loop. We create a variable Break which will start as true and when we turn this variable true the loop will break. In this case when a and b are the same the loop will stop.
while (Break=true) do if ((System.Math.Round(a,6)) = (System.Math.Round(b,6))) then Break <- false
Create two new variables which will contain f(x1) and f(x2).
- f1 = f(x1)
- f2 = f(x2)
Check f1 and f2 in the conditions that we define on the process.
if (f1>f2) then a <- a b <- x2 elif (f1<f2) then a <- x1 b <- b else Break <- false
- Recalculate the values for x1 and x2 with the formulas we provided in the process.
x1 <- a + (1.0 - R)*(b-a) x2 <- a + R*(b-a)
- Finally we print our results, the results will be shown on each iteration, but if you want to show only the final results take the print out of the loop.
You can get the whole code with instructions on how to run it here.
Real life applications
The Golden Search it's an optimization method mostly used in solving mathematical and real life problems. Problems that can be solved by optimization are very common, here are some examples:
- How should we optimize wealth and resources to promote sustainable development?
- How do we optimize our national budget so that every dollar is put to good use?
There are even some startups based on optimization algorithms:
Also you can use this specific method (Golden Search) in real life as a business man, when you want to find the point in which your costs are minimized or the point in which you maximize production, if your cost function is unimodal.
Finally I want to end with my opinion on functional programming. It was very interesting learning the basics but it was a little hard to get used to, here are some cons I found:
- It was hard to combine pure functions into a complete application.
- In my case recursion didn't feel natural.
- You may have performance problems like RAM use and speed.
But I also found some pros:
- Debugging is easier.
- Testing was easier.
- Concurrent programming is easier to implement.
To conclude I really liked this experience but I'll probably not use functional programming again, because I like more object-oriented programming and have more experience with it.