In this post I develop the code for the golden section region elimination class.
The golden section region elimination algorithm is another region elimination algorithm that is more efficient than interval halving.
The golden section region elimination algorithm starts with two boundary points, which I will denote x0 and x3. It then computes two other points that are both a distance τ from the left and right bracket, where τ is equal to (3 – Sqrt(5))/2. For these two points, I will denote the one closest to the left edge x1 and the one closest to the right edge x2.
At each of the four points, the function at that point is evaluated. Two different cases can then result.
In the first case, the function at x1 is greater than the function at x2. In this event, x1 becomes the new left bracket, x3 remains the new right bracket, x2 becomes the new x1 point, and a new x2 point is evaluated.
If the first case does not occur, then the reverse happens and x2 becomes the new right bracket, x0 remains the new left bracket, x1 becomes the new x2, and a new x1 point is calculated.
The source code for the golden section region elimination class is given below. The code for the region elimination base class was posted previously.
public class GoldenSectionRegionElimination : RegionEliminationBase
{
private readonly double _sectionRatio;
public GoldenSectionRegionElimination()
: base()
{
_sectionRatio = (3.0 - Math.Sqrt(5.0)) / 2.0;
}
public override RegionEliminationResults RegionEliminate(Func<double, double> function, SearchPointCollection startPoint, double eliminationFraction)
{
Debug.Assert(startPoint.Count >= 2);
Cancel = false;
double result = 0.0;
CalculateMissingValues(startPoint, function);
SearchPointCollection searchPoints = new SearchPointCollection();
searchPoints.MaxSize = 4;
SearchPoint leftBracket = startPoint[0];
SearchPoint rightBracket = startPoint[startPoint.Count - 1];
searchPoints.Add(new SearchPoint(leftBracket.X, leftBracket.Y));
double length = rightBracket.X - leftBracket.X;
double stopRegionSize = length * eliminationFraction;
SearchPoint newPoint;
newPoint = new SearchPoint();
newPoint.X = leftBracket.X + _sectionRatio * length;
newPoint.Y = function(newPoint.X);
searchPoints.Add(newPoint);
newPoint = new SearchPoint();
newPoint.X = leftBracket.X + (1.0 - _sectionRatio) * length;
newPoint.Y = function(newPoint.X);
searchPoints.Add(newPoint);
searchPoints.Add(new SearchPoint(rightBracket.X, rightBracket.Y));
while (!Cancel)
{
if (searchPoints[1].Y > searchPoints[2].Y)
{
searchPoints[0] = searchPoints[1];
length = searchPoints[3].X - searchPoints[0].X;
searchPoints[1] = searchPoints[2];
searchPoints[2] = new SearchPoint();
searchPoints[2].X = searchPoints[0].X + (1.0 - _sectionRatio) * length;
searchPoints[2].Y = function(searchPoints[2].X);
}
else
{
searchPoints[3] = searchPoints[2];
length = searchPoints[3].X - searchPoints[0].X;
searchPoints[2] = searchPoints[1];
searchPoints[1] = new SearchPoint();
searchPoints[1].X = searchPoints[0].X + _sectionRatio * length;
searchPoints[1].Y = function(searchPoints[1].X);
}
if (length < stopRegionSize)
{
Cancel = true;
}
}
result = (searchPoints[0].X + searchPoints[3].X) / 2.0;
return new RegionEliminationResults(result, function(result));
}
}
Subscribe