# The Golden Section Search Method: Modifying the Bisection Method with the Golden Ratio for Numerical Optimization

April 22, 2013 4 Comments

#### Introduction

The first algorithm that I learned for root-finding in my undergraduate numerical analysis class (MACM 316 at Simon Fraser University) was the bisection method. It’s very intuitive and easy to implement in any programming language (I was using MATLAB at the time). The bisection method can be easily adapted for optimizing 1-dimensional functions with a slight but intuitive modification. As there are numerous books and web sites on the bisection method, I will not dwell on it in my blog post.

Instead, I will explain a clever and elegant way to modify the bisection method with the golden ratio that results in faster computation; I learned this method while reading “*A First Course in Statistical Programming with R*” by John Braun and Duncan Murdoch. Using a script in R to implement this special algorithm, I will illustrate how to minimize a non-differentiable function with the golden section search method. In a later post (for the sake of brevity), I will use the same method to show that the minimizer of the sum of the absolute deviations from a univariate data set is the median. The R functions and script for doing everything are in another post.

The Fibonacci spiral approximates the golden spiral, a logarithmic spiral whose growth factor is the golden ratio.

Source: Dicklyon via Wikimedia

#### Minimization with the Bisection Method

Assume that a single-variable continuous function has a unique minimum (and, thus, a unique minimizer) in a closed interval [a, b]. If this function is differentiable in [a, b], then calculus can be used easily to find the minimizer. However, if the function has a cusp or a kink, then it’s not differentiable at that point, and numerical methods are needed instead. For example, consider the following function.

Within the interval [1, 3], this function has a unique minimizer near x = 1.5, but it also has a cusp at x = 2. Thus, it is not differentiable at x = 2. A simple, stable, but slow numerical method to find the minimizer is the bisection method.

To use the bisection method to find the minimizer, we can

1) Pick 2 points, and , with and both points in [a, b].

2) Find and .

3)

a) If , then the minimizer must be to the right of , because this unique minimizer must be less than , and the function is decreasing from to .

b) Otherwise (i.e. ), the minimizer must be to the left of with logically analogous reasoning.

4)

i) If 3a is true, then the minimizer must be in the interval ; repeat the algorithm from Step 1 until the interval length is smaller than some pre-set tolerance.

ii) If 3b is true, then the minimizer must be in the interval ; repeat the algorithm from Step 1 until the interval length is smaller than some pre-set tolerance.

To summarize this algorithm, every iteration beings with

– the boundaries of the interval ,

– 2 test points for the argument, and .

The function is evaluated at and , and, based on whether or , a new set of boundaries and test points are set for the next iteration.

#### Using the Golden Ratio to Set the Test Points

Since the test points and are arbitrarily set, it comes as no surprise that the choice of the test points affects the speed of the computation. A clever way to save computation time is to set the test points to take advantage of some special properties of the golden ratio, which Braun and Murdoch denote with and has the value

This number has many special properties that you can easily find on the web. The one that will save computation time is

Let the lower and upper bounds of the interval of interest be and , respectively. Now, let’s set the test points as

The advantage of setting the test points as these above values comes when one of the new test points is updated. Suppose that

.

Then the minimizer must be to the right of . Thus, becomes the new lower bound, which I will denote as . The beauty of the golden ratio comes in calculating the new lower test point, which I will denote as .

Since , becomes the new lower bound.

Recall that

Substituting the right-hand side of this above equation for in the calculation of , some very simple algebraic manipulation yields

Now, taking advantage of that special property of the golden ratio, , some more simple algebraic manipulation yields

**Thus, the new lower test point is just the old upper test point.** **This saves computation time, because we don’t need to compute a new lower test point; we can just recycle the value that we knew from the old upper test point!**

Similar logic for the case will show that the new upper test point is simply the old lower test point. Notationally, if

,

then

.

#### Using the Script to Numerically Minimize a Function

In another post, you can find the function for implementing this special golden search method and the script for minimizing the above function with the cusp. This script is basically the same as the one written by Braun and Murdoch on Pages 134-135 in their book. My script used slightly more self-evident variable names and included debugging statements to help me to identify why my function was not working properly when I first wrote it. Debugging statements are statements that show the values of key variables being computed in the flow of a script (and often within loops or branches) to identify the point in the flow at which the script stopped working properly. My mathematical and statistical programming skills became much better when I began using debugging statements. They are good for debugging, but should generally be commented out when the script is corrected and working properly. Since the problems that I am solving are quite simple, I kept them in the script and will show part of the output to illustrate why they are useful.

Recall the function with a cusp that I plotted above.

Using my function, the initial boundaries 1 and 3, and an absolute tolerance of , here is what my function, golden.section.search(), returned in the first iteration.

> golden.section.search(f, 1, 3, 1e-5) Iteration # 1 f1 = 0.8196601 f2 = 1.763932 f2 > f1 New Upper Bound = 2.236068 New Lower Bound = 1 New Upper Test Point = 1.763932 New Lower Test Point = 1.472136

This function used 26 iterations to get the final answer.

Iteration # 26 f1 = 0.75 f2 = 0.75 f2 > f1 New Upper Bound = 1.500003 New Lower Bound = 1.499995 New Upper Test Point = 1.5 New Lower Test Point = 1.499998 Final Lower Bound = 1.499995 Final Upper Bound = 1.500003 Estimated Minimizer = 1.499999

This is consistent with the “eye-balled” answer of from the plot.

How do you show that the golden ratio method is better than the bisection method?

In the bisection each interval is half size of the previous. In the Golden ratio search

the new interval has the size of 2/(1+sqrt(5)) that is close to 2/3 of the previous interval.

So it is obvious that the size of the bisection goes as (1/2)^n, while the size of the

Golden ratio goes something as (2/3)^n, the bisection converges faster.

What is the point on choosing a method which is more complicated (the bisection is the

simplest, right?) and more expensive?

Thanks.

Hi Herman,

Thanks for your question, and you raise a very good point. The golden section search method needs to choose only 1 new test point at every step, whereas the bisection method needs to choose 2.

However, you still raise a good point – the interval of search is smaller for the bisection method. Thus, which one converges faster? I did some research on the weekend, but still could not find a definitive answer. Let me get back to you on this.

Thanks for your patience.

Eric

Great post!

The bisection method (from Wikipedia) isn’t exactly the right algorithm to compare this to, and the algorithm you sketch isn’t really bisection. The bisection only works when trying to bracket something that you can distinctly test for, such as a root (see Wikipedia image). You thus only need to save two points + the one at test.

When minimizing, it’s harder to know if you’ve really the bracketed the minimum and we thus need to save our two points plus TWO at test, which you have noted as x1 and x2 which are both in [a,b]. The ‘naive’ implementation thus isn’t binary search, but Ternary search (http://en.wikipedia.org/wiki/Ternary_search).

With regards to Herman’s question, Ternary Search and Golden Search both converge at the same rate (2/3)^N, but Golden Search requires 50% fewer function calls.

Reblogged this on nishant@analyst.