Juan C LR

Posted on May 18, 2018

Golden Search Algorithm in F#

#goldensearch #numericalmethods #f

Start

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.

Set

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.

Golden Ratio:

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.

The process

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^(−x)^2 ):

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.

Conclusion

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.

Latest comments (6)

amieres • Sep 3 '18 • Edited

Like someone already mentioned your code is imperative, not functional.
The first clue is that functional code does not use mutability.
Your implementation is not using recursion just a loop, that is the second clue. To use recursion in F# you need to add rec before the function name, like below where it says: let rec golden ...
A functional version could look like this:

let round   (f:float) = Math.Round(f, 6)
let funcion  x        =  0.5 - (x * Math.E) ** (-x ** 2.0)
let R                 = (5.0 ** 0.5 - 1.0) / 2.0

let goldenAlgorithm limits =
    let rec golden iter (a, b) = // <--- recursive function
        if round a = round b then (iter, a, funcion a) else // <--- solution
        if funcion a > funcion b 
            then   a                       , (a + R * (b - a))
            else  (a + (1.0 - R) * (b - a)),  b
        |> golden (iter + 1)     // <--- recursive call
    golden 1 limits              // <--- initial call

goldenAlgorithm (0.0, 2.0)
|||> printfn "iteraciones: %i\nvalor en x:  %f\nvalor en f(x):  %f"

// output:
// iteraciones: 32
// valor en x:  0.223130
// valor en f(x):  -0.475414

This code demonstrates several traits of F#:

How clean and uncluttered the code is. I removed extra parenthesis to make the code more clear.
The use of the pipe (|>) and even the triple pipe! (|||>) to avoid unnecessary names
Use of tuples (and triplets).
Pattern matching. Notice how limits becomes (a, b) when calling:
- golden 1 limits

Type inference. F# is a strongly typed language like C# but you do not need to specify the types of every function or parameter, the compiler can deduced them.

Inside goldenAlgorithm is the recursive function golden of type:
int -> float * float -> (int * float * float)

It receives the number of iteration (starting with 1) and the limits a & b.
It calls itself using tail recursion until it finds a solution and returns a triplet with the total number of iterations, the solution x and the value of f(x).

My suggestion to you is to not abandon functional programming. You are just starting and the more you learn the more you are going to like it, I promise.
Your reason for sticking with OOP is mainly because that is your comfort zone right now, real growth happens when you venture out of your comfort zone.

Christophe Riolo • May 22 '18

This is not functional programming, you are implementing a loop and modifying variables, so it's imperative. If it were functional, you would instead use a recursive function :)

Anthony Lloyd • May 21 '18

You are evaluating the function too often. You should only need to evaluate once for each iteration. You can see this if you put a printfn in the function and see the repeated same calls.