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

(This article was first published on The Chemical Statistician » R programming, and kindly contributed to R-bloggers)

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 made sure 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

# Calling the user-defined functions in the working directory
source('golden.section.search.R')
source('f.R')

# printing the PNG images into the working directory
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)

Filed under: Applied Mathematics, Numerical Analysis, Plots, R programming, Statistical Computing Tagged: applied mathematics, numerical analysis, numerical method, numerical methods, numerical optimization, optimization, R, R programming, statistical computing

To leave a comment for the author, please follow the link and comment on their blog: The Chemical Statistician » R programming.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.

Sponsors

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)