# Scripts and Functions: Using R to Implement the Golden Section Search Method for Numerical Optimization

April 22, 2013 4 Comments

In an earlier post, I introduced the golden section search method – a modification of the bisection method for numerical optimization that saves computation time by using the golden ratio to set its test points. This post contains the R function that implements this method, the R functions that contain the 3 functions that were minimized by this method, and the R script that ran the minimization.

I learned some new R functions while learning this new algorithm.

– the curve() function for plotting curves

– the cat() function for concatenating strings and variables and, hence, for printing debugging statements

As usual, I used the setwd() function to change the working directory in R to the folder that contains all of these files, and I used the source() function to call the relevant functions in my script for running everything.

Here is the function that I minimized in my earlier blog post; I titled it “f.R”.

```
f = function(x)
{
abs(x - 2) + (x - 1)^2
}
```

Here is the function that implemented the golden section search method; I called it “golden.section.search.R”.

##### Implementing the golden section search method ##### a modification of the bisection method with the golden ratio ##### By Eric Cai - The Chemical Statistician golden.section.search = function(f, lower.bound, upper.bound, tolerance) { golden.ratio = 2/(sqrt(5) + 1) ### Use the golden ratio to set the initial test points x1 = upper.bound - golden.ratio*(upper.bound - lower.bound) x2 = lower.bound + golden.ratio*(upper.bound - lower.bound) ### Evaluate the function at the test points f1 = f(x1) f2 = f(x2) iteration = 0 while (abs(upper.bound - lower.bound) > tolerance) { iteration = iteration + 1 cat('', '\n') cat('Iteration #', iteration, '\n') cat('f1 =', f1, '\n') cat('f2 =', f2, '\n') if (f2 > f1) # then the minimum is to the left of x2 # let x2 be the new upper bound # let x1 be the new upper test point { cat('f2 > f1', '\n') ### Set the new upper bound upper.bound = x2 cat('New Upper Bound =', upper.bound, '\n') cat('New Lower Bound =', lower.bound, '\n') ### Set the new upper test point ### Use the special result of the golden ratio x2 = x1 cat('New Upper Test Point = ', x2, '\n') f2 = f1 ### Set the new lower test point x1 = upper.bound - golden.ratio*(upper.bound - lower.bound) cat('New Lower Test Point = ', x1, '\n') f1 = f(x1) } else { cat('f2 < f1', '\n') # the minimum is to the right of x1 # let x1 be the new lower bound # let x2 be the new lower test point ### Set the new lower bound lower.bound = x1 cat('New Upper Bound =', upper.bound, '\n') cat('New Lower Bound =', lower.bound, '\n') ### Set the new lower test point x1 = x2 cat('New Lower Test Point = ', x1, '\n') f1 = f2 ### Set the new upper test point x2 = lower.bound + golden.ratio*(upper.bound - lower.bound) cat('New Upper Test Point = ', x2, '\n') f2 = f(x2) } } ### Use the mid-point of the final interval as the estimate of the optimzer cat('', '\n') cat('Final Lower Bound =', lower.bound, '\n') cat('Final Upper Bound =', upper.bound, '\n') estimated.minimizer = (lower.bound + upper.bound)/2 cat('Estimated Minimizer =', estimated.minimizer, '\n') }

Here is the script that ran everything; I called it “minimization.R”.

##### Finding the minimizers of functions using the bisection method with the golden ratio ##### By Eric Cai - The Chemical Statistician # setwd(INSERT YOUR DIRECTORY PATH HERE) # Calling the user-defined functions in the working directory source('golden.section.search.R') source('f.R') # printing the PNG images into your desired folder png('INSERT YOUR DIRECTORY PATH HERE/cusped function.png') # plotting the curve of my user-defined function curve(f, from = 1, to = 3, main = expression(paste('f(x) = |x - 2| + (x - 1)'^'2'))) dev.off() # finding the minimizer of my user-defined function using my golden bisection method golden.section.search(f, 1, 3, 1e-5)

Reblogged this on nishant@analyst.

Nice, thanks for sharing the code!

I think the golden ratio is inverted here?

oops sorry no