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