Golden Search Algorithm in F#
Tags: goldensearch, numericalmethods, f
Published: 2018-05-18 22:40:58

---
title: Golden Search Algorithm in F#
published: true
description: 
tags: 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.
![Golden ratio in nature](https://thepracticaldev.s3.amazonaws.com/i/pxvsits0nh491c1zqybm.png)
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](https://en.wikipedia.org/wiki/Unimodality) 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](https://github.com/juanclr/FPNumMethods).

#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:
- [INFORM](https://www.inform-software.com/).
- [AntOptima](http://www.antoptima.com/site/en/index.php/)
- [Dynadec](http://dynadec.com/).

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.