Last post we went over how Golden Section Search works and how it got its name. This post we will go through our example step by step through the search method. Now if you remember from last time our function was f(x) = x^2 +3x+7 over the interval [-3,1]. Here’s the graph again below (this time made with matlab).
This time I have included our interval. So our next step is to find our next two points. From part 1, x3 = x2 + (1-gr)*(x1-x2) and x4 = x1 + (1-gr)*(x2-x1). Substituting -3 for x1 and 1 for x2. This gives us an initial x3 = -1.4721 and x4 = -0.5279. I have plotted the new lines on our graph below.
As you can see our new interval as already drastically decreased from our original interval. However, we need to determine which interval we keep. Graphically we can see that the green line on the left is the one we want to keep. So we create a new interval ensuring the green line is within the interval. This time we only have to evaluate one additional point. That point will lie between our left most boundary (black line) and the left green line. We first re evaluate our interval, x1 is still x1, x4 is now our right most boundary (x2). Now we need our two interior points. Well we already have one, the left green line, so we need to calculate the other one.
The two new boundaries are shown in red. As you can see one of the green lines before is now red and the other boundary is found by the formula x3 = x2 + (1-gr)*(x1-x2). If we had chosen the other line we would need to calculate a new x4. This cold be found by x4 = x1 +(1-gr)*(x2-x1). But in this case we only need x3. We are narrowing down to the minimum, but we are still not there yet. This means we need to do another iteration.
As before one of our lines changed color and we have a new line and this a new interval. Notice that our interval is getting smaller and smaller proportionally though. This brings us to a good point. When do we decide when to stop? We have to set a tolerance condition. For the sake of brevity lets set our tolerance to be 0.1, which isn’t a great interval, but it will get us pretty close to our minimum. Our tolerance is defined by the absolute value of the difference between x3 and x4 our interior points. Lets run it a few more times till we pass our threshold.
I ran the search 3 more times. First the yellow line, then magenta, and finally blue. The blue lines give us a tolerance of 0.08453 with our minimum in the middle of this interval at -1.5147. The actual minimum of this function is -1.5, which is close to the minimum we calculated. With more iterations and a stricter tolerance we can get closer to the actual minimum. However with only 6 iterations we are within 1% of the actual value.Hopefully this shed a little light on how golden section search converges on our minimum. But! There is more that we need to go over. Next post we will program a simple program for it in matlab and python. Also we will go over the limitations of GSS.-Marcello