Category: One Dimensional Search Methods

In the past couple of posts we have gone over three different search methods. We started with the Golden Section Search (GSS) as the most basic and intuitive way to find a minimum. We then optimized GSS with varying reduction step sizes and came up with the Fibonacci search method. Finally, we looked at the properties of functions and their derivatives to create our last search method, Newton’s Method.  Each method had its own shortcomings and benefits, but the question remains which method should we be focusing on? Is there a best method?

Well i have some follow up questions. What makes a method the best? The two obvious choices are speed and accuracy (and to an extent precision). So which of our methods came out on top? Well if you remember, we used the same example function throughout our journey through ODSM. This function was a simple quadratic function. Gss took 6 iterations, FS took five and NM only took 1. To be honest this was not the best example as NM will always find the exact answer to all quadratic equations in one step. So for this recap we will use a new function and see how they all stack up. I have chosen an interesting function paper, but a rather boring one graphically. The function is f(x)=x^4 -(x)^3+cos(x)-12 and is plotted below (taken from wolfram alpha).

Using this new function with our three methods. I capped each at 5 iterations so we could see the graphs and the methods without getting to cluttered. running the three methods produces the following plot.

Each method was able to get decently close to our minimum. However, as you can see each method goes about it at a different way. Newton’s method quickly converges to our minimum. Really only taking 4 iterations, Newton’s method converges fastest. GSS and FS both come decently close in our 5 iteration limit. But what about accuracy?

The true minimum of this solution is  at x ≈ 0.969366 with f(x)  = 11.4621. Newton’s method after 5 iterations produced a minimum of 0.9694. GSS produced a minimum of 0.8754, and FS produced a min of 0.7077. As you can see there is no competition between the three in regards to this function. Newton’s method is the fastest and the most accurate at 5 iterations. However, this is not to say this is the best method. It is time I introduced the no free lunch theorem of optimization.

TheNO Free Lunch theorem introduced by David Wolpert and WIlliam G Macready, says “that for certain types of mathematical problems, the computational cost of finding a solution, averaged over all problems in the class, is the same for any solution method”(from wikipedia). How does that apply here? Well it says that even though Newton’s method is the clear winner with regards to this function, when we consider all possible functions and limitations Newton’s method is no better that GSS or FS. This is not to say that we should just choose our method without regard or rationale.

For example if we have a function who has a terrible derivative or awful second derivative, we might favor FS or Gss. On the other hand if evaluating the derivatives are easy we would choose Newton’s Method. This all depends on whether or not you believe in such a thing as a free lunch

Marcello

Unlike GSS and FS, Newton’s method has different limitations and restrictions. However, before we jump in lets look at a harder more elaborate function. Part2 goes over a too simple function for the sake of consistency, but lets take a function say: f(x) = x^4+6x^3+x^2-2x +cos(x) . This function is plotted below.

As you can see we have two minimums so we can see how our method behaves. I am going to skip the step by step and just show the results of the method. We will choose our fist point at -8. This produces the following graph with the points different colors.

I had to make this graph a little bigger so you can see whats going on. Each point represents a step in our method. This method took 5 steps to get to our minimum (not including the starting point). Newton’s Method produced a minimum of -4.3462 which is close to the actual minimum, -4.34613. With only 5 iterations this is impressive method. Lets try a new initial point,5. This produces the following.

Uh oh. It looks like our method converged to the wrong point. Like FS and GSS, Netwon’s will find a minimum on the interval you choose however, this minimum might not be a global minimum. Local vs global minimum is a major issue with all three ODSM. In this case, Newton’s method got caught in a saddle-like point.

Another more obvious limitation stems from the method itself. We need to be able to find the second derivative of our function. If there is no second derivative, there is no method. Well mathematicians don’t exactly take no for an answer. The Secant method was developed to remedy this. The Secant method is basically a modified Newton’s method that does not require a second derivative, only the first.

The last limitation involves our initial conditions like with GSS and FS. Our initial value for Newton’s method greatly determines the effectiveness. This is evidenced by the two above graphs which show how sensitive the method is.

I hope you understand Newtons method a little better. You can experiment more if you like i have copied the code below.

%array to get values of our function
z = -8:.001:5;</code>

% our function x^4+8x^3-2x +cos(x)
l = z.^4+6*z.^3+z.^2-2*z+cos(z);

tol = 1;
%initialize arrays to store step values
x = zeros(1,10);
y = zeros(1,10);
%initial guess
x(1)=5;
y(1) = x(1).^4+6*x(1).^3+x(1).^2-2*x(1)+cos(x(1));
i=2;
while tol &gt;0.005 %tolerance stop condition
     %first derivative
     dx = 4*x(i-1).^3+18*x(i-1).^2+2*x(i-1)-2-sin(x(i-1));
     %second derivative
     d2x = 12*x(i-1).^2+36*x(i-1)+2-cos(x(i-1));
     %newtons method step
     x(i) = x(i-1)-(dx/d2x);
     y(i)= x(i).^4+6*x(i).^3+x(i).^2-2*x(i)+cos(x(i));

     tol = abs(x(i)-x(i-1));
     i= i +1;
end

x
%plot our results
plot(z,l,x(1),y(1),'g*',x(4),y(4),'g*',x(2),y(2),'c*',x(3),y(3),'r*',x(5),y(5),'c*',x(6),y(6),'r*',x(7),y(7),'g*',x(8),y(8),'g*',x(9),y(9),'c*',x(10),y(10),'r*')

title('Newtons Method example 2 ')
xlabel('x')
ylabel('y')

-Marcello

Last post we went over how Newton’s method works and derived the iterative step. This post we will go through our example step by step through the search method. We are going to use the same function from GSS and FS, f(x) = x^2 +3x+7 over the interval [-3,1]. However this time we do no need to concern ourself with the interval. We simply need an initial guess. Here’s the graph again (from -5 to 5).

Noticed the little dot. This will be our starting point. I chose the left side of our old interval at x=-3. With Newton’s method we have to use this point to evaluate two functions, the first derivative as well as the second derivative. Hopefully this increase in function evaluations will mean a reduction in iteration or at least a more accurate and precise answer.

Before we go any further we need to find the first and second derivative. Using our function above I am sure you can find the first and second derivative, but I have listed them below for your convenience.

Now we need to evaluate the first and second derivative at our initial point. This gives us -3 and 2. using these values we plug them into our iterative equation from last post (x(i+1)=x(i) -f’/f”). This produces a x(2) of -1.5. Like GSS, Newton’s Method stops at a tolerance condition. Remember tolerance is defined here as the absolute value of the difference between two consecutive x values. Because this hasn’t been reached we run our method again.

Using -1.5 as our x we evaluate f’ and f ”. This produces 0 and 2 respectively. Plugging these values in gives us a new x of -1.5, the same value we started with. Thus the tolerance condition is met and our search stops. The graph is below, but rather uninteresting first point in green second/third in red.

Now why did Newton’s work so well? It found the exact minimum in only two iterations. If you remember from part 2, Newton’s method approximates the function with a quadratic equation. Well if our function is already quadratic Newton’s method can approximate it perfectly. Because of this Newton’s method finds the minimum for quadratic equations very fast.

Well that lame example was Newton’s method. Next post we will go over hopefully a more interesting problem as well as the limitations.

-Marcello

We have one more one dimensional search method to go over, and this one is important. I am sure you are familiar with Isaac Newton Well this method is named after him. Newton’s method like both GSS and FS Newton’s method helps us find the minimum of our function, but Newton’s method varies greatly from these two.

The first and most important thing when thinking about using Newton’s method is to ensure that the function is twice differentiable.  Newton’s method uses a truncated taylor series to estimate where the minimum lies. But we are getting ahead of ourselves. Let’s start from the beginning.

Newton’s method uses a single point to begin, unlike the GSS and FS. This point is used as a basis for our Taylor expansion. We need to take a brief detour to go over why we want to construct a Taylor Expansion. Just a quick reminder, a Taylor series (or expansion) is an approximation of a function as a sum of terms that are determined by the functions derivatives at a single point.  This is described by the equation below (from wikipedia):

As you can see, each term of the expansion has a derivative of the function evaluated at the same point. For our method, we are only going to concern ourselves with the first three terms. This is why we need our function to be twice differentiable. This allows us to create a taylor expansion based off our initial guess (and our following guesses). But why would we want to do this? What is the benefit? Making a Taylor expansion allows us to create a quadratic function through our initial point which has the same first and second derivatives as our function.  Our quadratic function (k(x)) is listed below:

We then try to minimize our new function. Using the first order necessary condition for a minimizer (the first derivative must equal zero at the minimizer), we take the derivative of the above equation and set it equal to zero. This produces the following:In order to find the minimum we need to solve for x.  We do this in hopes that the x we solve for is closer to the minimum of our true function. This is shown below:

This looks awfully like our iterative steps from GSS and FS. Replace x0 with xi and x with xi+1 and we have a search method. Like GSS and FS, we then repeat our method in hopes of getting closer to our minimum.  As we get closer to our minimum the first derivative of our function moves toward 0 which makes xi ≈ xi+1. This is when we know our method has found a minimum (hopefully). Like GSS, we use a tolerance termination condition rather than certain number of iterations like FS.

Hopefully you followed me on this brief overview of our third ODSM. Next post we use a real example.

-Marcello

This is gonna be a brief post as most of the limitations of Fibonacci search were covered in my post on GSS. This makes sense because Fibonacci search is just a GSS with a different reduction at each step. So if follows that the limitations for GSS will also apply to the Fibonacci search. If you weren’t here for the GSS part 3 post I will go over the basic limitations.

Fibonacci search will find a minimum on the interval you choose however, this minimum might not be a global minimum. Local vs global minimum is a major issue with Fibonacci. One of the main requirements for Fibonacci, like GSS, is that a function must be unimodal. Now what does unimodal mean?  IF you remember, this basically means that the function has a single local extremum. This makes it so the search method does not get stuck in an “incorrect” local minimum. This also depends on the interval you choose If you choose an interval that does not contain a minimum, Fibonacci search won’t (can’t) find it.

One thing unique to the Fibonacci search is that it has a set amount of iterations chosen at the beginning of the method. If the user does not choose enough iterations the error surrounding the minimum can be large. However, if too many iterations are chosen then the method becomes arduous and expensive calculation wise. Having an idea of the tolerance you need for your minimum and the relative location is invaluable when using the fibonacci search method.

To review, when should be use GSS or Fibonacci search : Function has one minimum (unimodal), you have an idea of the interval that contains the minimum, the function is of one variable.

Here is the code i used to create the graphs from Part 2. This is written in matlab code. I will post a python version later.

Code Starts here

%array to get values of our function
z = -5:.001:5;

% our function y=x^2 + 3x + 7
y = z.^2+3*z+7;

%number of iterations, feel free to change
iter = 5;
epsilon=0.05; %epislon to prevent double value at last iteration

% Fibonacci calculation sequence
fib = zeros(1,iter+2);
fib(1)=1;
fib(2)=1;
for i =3:iter+2
fib(i) = fib(i-1)+fib(i-2) ;
end
rho = zeros(1,iter);

%calculate z values from above Fibonacci Sequence
for i=0:iter
rho(i+1) = 1-(fib(end-i-1)/fib(end-i)) ;
end

%our search interval
x1=-3;
x2=1;

%finding our first two internal points
x3 = x1+rho(1)*(x2-x1);
x4 = x1 +(1-rho(1))*(x2-x1);

x30 = x1+rho(1)*(x2-x1);
x40 = x1 +(1-rho(1))*(x2-x1);
for i = 1:iter-1
% evaluate our function at the two internal points
fx3 = x3.^2+3*x3+7;
fx4 = x4.^2+3*x4+7;
%check if we are at the last iteration
if rho(i+1)==0.5
rho(i+1)= 0.5-epsilon;
end
%determine which interval we want to keep
if fx3>fx4
x1=x3;
x3=x4;
x4 = x1 +(1-rho(i+1))*(x2-x1); %find new x4 point
else
x2=x4;
x4=x3;
x3 = x1+rho(i+1)*(x2-x1); %find new x3
end

x3a(i) = x3;
x4a(i)=x4;
end

min = (x3+x4)/2 %our "boxed in" min
minf = min.^2+3*min+7 % our function evaluated at our min

%plot our results
plot(z,y,-3,y,3,y,x30,y,'g',x40,y,'g',x3a(1),y,'r',x4a(1),y,'r',x3a(2),y,'c',x4a(2),y,'c',x3a(3),y,'y',x4a(3),y,'y',x3a(4),y,'m',x4a(4),y,'m')
title('Fibonacci example')
xlabel('x')
ylabel('y')

-Marcello

Last post we went over how Fibonacci Search works and how it got its name just like GSS. This post we will go through our example step by step through the search method. We are going to use the same function from GSS f(x) = x^2 +3x+7 over the interval [-3,1]. Here’s the graph again (from -5 to 5).

So before we start anything we need to choose how many iterations we want and calculate our fibonacci sequence. To match with the GSS, we will start with 5 iterations. this means we need 6 numbers of the fibonacci sequence (N+1). This does not include F0 and F-1. Using the recursive formula this gives us 1,2,3,5,8,13 as the numbers we need. From this we can calculate all of our necessary z values. Our next step is to find our next two points. From part 1, x3 = x1+z*(x2-x1) and x4 = x1 +(1-z)*(x2-x1), where z is equal to 1 minus the ratio of two sequential fibonacci numbers starting at N+1 and working down to 1 (check back one post for formula) . Substituting -3 for x1 and 1 for x2. This gives us an initial x3 = -1.4615 and x4 = -0.5385.  I added these values as lines to our graph below.

Just like with GSS (actually even more so), our new interval as already drastically decreased from our original interval.  Again, 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. Also we can evaluate our function at the two points and see which one gives us a lower y value. Doing this confirms our guess of the left line. We want to keep this line as it contains our minimum.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. Using the formula above for x3, we find x3b = -2.0769, which is plotted below. 

The two “new” boundaries are shown in red. As you can see one of the green lines before is now red.  As before,If we had chosen the other line we would need to calculate a new x4. This cold be found by the equation for x4 above. 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 no longer getting smaller and smaller proportionally. This is where Fibonacci differs from GSS, we are allowed to change the reduction factor at every iteration. Unlike with GSS, Fibonacci does not terminate with a tolerance condition, but with a number of iterations (we chose 5 at the beginning). Lets jump ahead to 5 total iterations.
I ran the search 2 more times. First the yellow line, then magenta. Graphically it looks like the Fibonacci search pretty much narrowed down to exactly the point we are looking for. At this scale the magenta lines seem to be right on top of each other. However, remember that this is in the design of the search method. The z value for the last step is 1/2 – epsilon, so naturally, since epsilon is so low (i chose 0.05), these last two lines should be very close to each other. So what value did the search close in on? Fibonacci search produced a min of -1.4462.  The actual minimum of this function is -1.5, which is kinda close to the minimum we calculated. With more iterations and a stricter tolerance we can get closer to the actual minimum. However with only 5 iterations we are within 4% of the actual value.

Now you got another search method under your belt. But! There is more that we need to go over (just like with GSS). Next post we will program a simple program for it in matlab and python. Also we will go over the limitations of Fibonacci.

-Marcello

Our next one dimensional search method or line search method is the Fibonacci Search method. Like the golden section search method, the Fibonacci search method is a method of finding an  extrema of a unimodal function. Also like the GSS, Fibonacci search’s name directly describes how the search method reduces its search space. In GSS, we use the golden ratio to reduce our space. In Fibonacci search, we use, you guessed it, the fibonacci sequence.

Just a brief refresher, the Fibonacci sequence is defined by the following recursive equation:

Each number in the sequence is the sum of the two numbers in the sequence before it. By convention, when k=-1 F=0 and when k = 0 F=1. This allows us to calculate values for all k>0.

OK back to the search method. With the GSS method we were limited on the reduction of our search interval. Each interval would reduce proportionally by 0.618 (remember (1-z) from the previous pots). This limits the speed convergence and how close our search method can get to our minimum. Fibonacci search remedies this. Fibonacci search allow us to vary our z values so that the space we search decreases much faster and gets closer to our target. The follow up question is obvious, how do we determine how z changes? Well that is an optimization problem in itself.

Quickly going back to the GSS, we know that with every iteration our uncertainty range reduces by 0.618 or (1-z). So it follows that for N iterations, we have a total reduction factor of (0.618)^N or (1-z)^N. Now if we are allowed to vary z we get the following reduction factor:The objective is to minimize the above. Minimizing this function results in a smaller final uncertainty range. However, we cannot just pick  any z values for this equations. The are subject to certain requirements or constraints. The first is that for any z it must be greater or equal to 0 and less than or equal to 1/2. 1/2 is chosen as un upper limit to ensure that only one new testing point is needed for each iteration. If we have a reduction of 1/2 the two test points coincide in the middle of the interval. This prevents the method from continuing. The new z values must also satisfy the condition that the distance between our two test points must be equal to the distance from the selected test point to the nearest boundary point. With these constraints we can form the optimization problem and find our minimum.

How does the Fibonacci sequence fit into all this? It happens to be that the optimal solution to our minimization problem involves the ratio of two sequential numbers in the sequence. The optimal z values are as follows:

This leads is to our first limitation. Fibonacci search, unlike GSS, requires a finite number of predetermined iterations. As seen by Zn, the end of the search is the beginning of the Fibonacci sequence. We need to take a quick pause at the last Z. When we plug in F1 and F2 of the FS we get Zn = 1/2. Earlier i warned of the dangers of a 1/2 reduction. To avoid falling into that pit, we introduce an ε (epsilon) which gently moves our Zn away from 1/2. In order for the epsilon fix to work, ε must be small.  Now that we have our step reduction we can find our test points.

We find our test points just like in GSS. X1 and X2 are the initial boundaries, X3 and X4 are calculated by the following equations:

With all this information we can form our search. The method takes on the same form of GSS, where the range is split into sections and one section is chosen and the other rejected. The accepted section is then further split and the method repeats. Now that we have the basics down and a rough outline of how to proceed we can try our method. Thats for part 2.

-Marcello

Weve been over what GSS is in part 1 and how exactly to use GSS in part 2. Now we need to know when we can use GSS and explore a real world example. So if you noticed our example was pretty simple. The minimum could be found by simple inspection or some derivative tests. Another thing to notice is that the function had exactly one minimum, which ended up being the global minimum of the function. However, lets look what happens to our search method when we have two minimum in our interval.

Lets take a look at the function: y=x^4-6x^2+3x+7. This function has two local minimums very close to each other, one of which is the global minimum of the function. The function is plotted below.

Here you can clearly tell there are two minimum one around -2 and other other around 2. However, the minimum at -2 seems to be lower than that at 2. Lets see how our GSS tackles this problem. I am going to expand our interval to [-3,5]. This produces the following plot with each step a different color.
As you can see the GSS seems to be closing in on one of our minimum. This is one limitation of the GSS it is not a global minimum search. GSS can find a minimum but there is no guarantee that that minimum is not just a local minimum. What happens if we change our interval. I will reduce our interval to [-3.3] and run the gss again. This produces the following plot with each step a different color. This interval produces a very different search. Simply changing the interval we search over switches which minimum the gss converges on. This is not exactly something we want to look for in a search method. However, in both intervals the method did converge to a minimum which is something we want to look for in a search method.

Local vs global minimum explains a major issue with GSS. One of the main requirements for GSS is that a function must be unimodal. Now what does unimodal mean? This basically means that the function has a single local extremum. As we saw above this becomes important in terms of converging to the correct (and if unimodal, only) minimum.

To review, when should be use GSS: Function has one minimum (unimodal), you have an idea of the interval that contains the minimum, the function is of one variable.

Hopefully this gave you a better understanding of a basic search method. This is only the beginning.  I will clean up my code and post it below, for both matlab and python. I will also post it to my github at github.com/mgric.

-Marcello

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

When approaching optimization problems it is essential to know what you are looking for. Whether we want a minimum or maximum, we need a direction to look or a way to search. One of the simplest search methods is the golden section search.

Golden Section Search (GSS) using a closing window to narrow down to our minimum or “boxing in”. By restriction the area with each step the minimum becomes trapped between the shrinking boundaries. To help visualize imagine the trash compactor scene from Star Wars IV.

Our minimum is Han Solo, the trash compactor is our function, and the space between our walls our search area. When the compactor walls are not activated, there is plenty of room for our heroes to occupy. However, as the walls start to come together, there is less room for our heroes to move around in. Eventually if allowed to progress, the walls will frame our hereos, making them very easy to spot amongst the garbage.

This is not exactly how GSS works as this would be terribly inefficient, as we would have to try every point starting from the left and the right till they meet at our minimum. This becomes very expensive in terms of time and calculations. This is the exact reason why we use and develop search methods.

GSS works a little different. In order to cut down on the number of iterations and function evaluations, GSS breaks our domain into sections. GSS then systematically eliminates sections which (hopefully) do not contain our minimum. The section that remains is then further divided and the method repeats. This happens until a termination condition is met or a tolerance is reached.  So know that we have a basic idea of how this works lets jump in.

First lets take a very easy function and run through all the steps. Below is a graph of the function y = x²+3x-7. (taken from wolfram alpha)

Now this problem can be solved simply by inspection, but lets use the GSS anyway. First we have to pick an interval on which we believe our minimum lies. Lets use an interval of [-3,1]. This interval contains our minimum as well as a good amount of extra so we can see the effects of the search. Now that we have an interval we need to make our sections.

We first choose the boundaries as the first two points to evaluate our function, lets call them x1 and x2. However, this doesn’t exactly break up our function into the sections we need. So we choose two more points. We first choose a general x3 which lies between x1 and x2. For x4, we need to insure that we have two equal intervals and that it also lies between x3 and x2. If we have unequal intervals our method might choose the wider interval which would cause our method to reach our minimum slower. Also if we choose a point outside this range, we will need to redefine the constrains we put on this equation. Because of that we need a formula to determine a fourth point that produces equal sections. GSS chooses the point x4 by the following function x4 =x1 + (x3-x2). This insures that the distance between  x1 and x2 is the same as x3 and x4.

But where exactly do we choose our x3? GSS has a procedure for this. GSS relies upon a constant proportional reduction of the interval we search. This means that uncertainty range is reduced by ρ at every iteration. This also means that our new evaluation points must maintain this proportion. At this point GSS starts to get a little confusing. We need to derive a way to keep a constant proportion throughout the points as well as between iterations.

So we need the ratio of x4-x3 to x3-x1 to be equal to the ratio of x3-x1to x2-x3. So it should look like this:

This equation is telling us that the proportions of the two sections of the first iteration is equal to the proportions of the two sections of the second iteration of our search. This is for the case that the interval between x4 and x1 brings us closer to the minimum. If it is the interval between x2 and x3 that brings us closer we have the following proportion:

Both of these equations must be true as either section should be viable even though our search should not pick it. So we use these two equations to find out what our proportion is. Eliminating (x4-x3) and substituting in for x4 with a bit of rearranging gives us:

Substituting rho for (x2-x3)/(x3-x1) and solving gives us rho = 1.61803…. or the Golden Ratio. This is where GSS gets its name from. So to come back to our main point each subsequent testing point is chosen so that the golden ratio is maintained with each new section. This allows the search range by a factor of 1-z or 0.61803 with each iteration.

But how does that give us our points? Well since we know that they have to be even intervals and they must be proportional by 0.618. This is enough along with a little algebra to determine our points. x3 = x2 + (1-z)*(x1-x2) and x4 = x1 + (1-z)*(x2-x1).

Now that we know how the method works we can solve our original problem. Ill save that for part two.

-Marcello