Extreme Optimization >
User's Guide >
Mathematics Library >
Optimization >
One-Dimensional Optimization
Extreme Optimization User's Guide
User's Guide
Up: Optimization Next: Multidimensional Optimization Previous: Optimization Contents
One-Dimensional Optimization
The OneDimensionalOptimizer class is
the abstract base class for all one-dimensional optimizing classes. Each algorithm is implemented by a different
class, derived from OneDimensionalOptimizer.
Optimization algorithms
Many one-dimensional optimization algorithms have been developed. The Extreme Optimization Mathematics Library
for .NET supports the most popular ones.
Golden Ratio Optimizer
The simplest optimization algorithm uses the special properties of the golden ratio to successively narrow down
the bracketing interval. This algorithm is very robust, but is on the slow slide compared to other methods. It
is implemented by the GoldenSectionOptimizer class.
Brent Optimizer
Richard Brent published his algorithm for function optimization in 1971. The algorithm does not use derivatives.
Instead, it uses either parabolic interpolation or the golden ratio method to narrow the bracketing
interval. Convergence is usually much faster than the Golden Section method. This algorithm is
implemented by the BrentOptimizer class.
Brent Optimizer with Derivatives
It is possible to modify Brent's algorithm when the derivative of the objective function is available. Unless the
derivative is much cheaper to evaluate than the objective function itself, there is usually little benefit to using
this method. Even though the number of iterations may be somewhat smaller, the total running time will likely be
longer. Still, it is meaningful in some scenarios, which is why it is included. The algorithm is implemented by the
BrentDerivativeOptimizer class.
The OneDimensionalOptimizer Class
All one-dimensional optimization classes share a common interface defined by the OneDimensionalOptimizer class. The ObjectiveFunction property is a
RealFunction delegate that specifies the objective function. The
ExtremumType property
specifies whether a minimum or a maximum is to be found. Its values are as follows:
| Item |
Description |
| Maximum |
A maximum is to be found. |
| Minimum |
A minimum is to be found. |
The following example defines the cubic function x3-2x-5, and constructs a
BrentOptimizer to find a local maximum of the function:
| C# | Copy Code |
|---|
static double TestFunction1(double x)
{
return x*x*x - 2*x - 5;
}
// ...
BrentOptimizer optimizer = new BrentOptimizer();
optimizer.ObjectiveFunction = new RealFunction(TestFunction1);
optimizer.ExtremumType = ExtremumType.Maximum; |
| Visual Basic | Copy Code |
|---|
Function TestFunction1(ByVal x As Double) As Double
Return x * x * x - 2 * x - 5
End Function
' ...
Dim optimizer As BrentOptimizer = New BrentOptimizer
optimizer.ObjectiveFunction = _
New RealFunction(AddressOf TestFunction1)
optimizer.ExtremumType = ExtremumType.Maximum |
Optimization in one dimension works in two phases. First, an interval is found that contains the extremum. This is
called bracketing. Second, the extremum is located within the bracket. The first phase is performed by the FindBracket method. This method
finds a set of three points, such that the middle point has a function value that is less than (for a minimum) or
greater than (for a maximum) that of either of the other points. This ensures that the interval spanned by the two
outer points contains a local extremum of the requested type. After calling this method, the IsBracketValid property verifies
that a bracket was found.
The FindBracket
method is overloaded. The first overload takes three parameters: the lower bound and the upper bound of an initial
interval, as well as an interior point. Use this overload to completely specify the bracket. If the points you supply
do not form a bracket, the values are adjusted until a valid bracket is found.
The second overload has only two parameters: the lower and upper bound of the bracketing interval. The third
overload takes only one value, which is taken to be the middle of a bracketing interval of unit width. The last
overload takes no parameters. It attempts to find a bracket starting with the interval [0,1].
The FindExtremum method
performs the actual optimization calculation. The Extremum property returns the value of
the calculated extremum. The following example illustrates these methods and properties:
| C# | Copy Code |
|---|
optimizer.FindBracket(0, 6);
if (!optimizer.IsBracketValid)
throw new Exception
("An interval containing a minimum was not found.");
optimizer.FindExtremum();
Console.WriteLine(" Maximum: {0}", optimizer.Extremum); |
| Visual Basic | Copy Code |
|---|
optimizer.FindBracket(0, 6)
If (Not optimizer.IsBracketValid) Then
Throw New Exception _
("An interval containing a minimum was not found.")
End If
optimizer.FindExtremum()
Console.WriteLine(" Maximum: {0}", optimizer.Extremum) |
The OneDimensionalOptimizer class defines two methods that perform most of the initialization, as
well as the two steps in the calculation in one operation. The FindMinimum method looks for a
minimum. The FindMaximum method looks for a
maximum. Both these methods are overloaded. The first overload takes three parameters. The first is a RealFunction delegate that specifies the objective function. The second
and third parameters are the boundaries of a suggested bracketing interval. The second overload takes two parameters.
The first once again specifies the objective function. The second is an initial guess for the extremum.
The example below directly calculates the maximum and minimum of the cubic polynomial we used earlier using these
methods:
| C# | Copy Code |
|---|
RealFunction f = new RealFunction(TestFunction1);
double min = optimizer.FindMinimum(f, 0);
double max = optimizer.FindMaximum(f, 0); |
| Visual Basic | Copy Code |
|---|
Dim f As RealFunction = New RealFunction(AddressOf TestFunction1)
Dim min As Double = optimizer.FindMinimum(f, 0);
Dim max As Double = optimizer.FindMaximum(f, 0); |
Results
The Result property always returns the best
value for the extremum.
If the ThrowExceptionOnFailure
property is set to true, an exception is thrown if the algorithm has failed to converge to a solution
within the desired accuracy. If false, the FindExtremum, FindMinimum, and
FindMaximum methods return the best approximation to the extremum, regardless of whether it is within
the requested tolerance.
The Status property indicates how the algorithm
terminated. Its possible values and their meaning are listed below.
| Value |
Description |
| NoResult
|
The algorithm has not been executed. |
| Normal
|
The algorithm ended normally. The desired accuracy has been achieved. |
| IterationLimitExceeded
|
The number of iterations needed to achieve the desired accuracy is greater than MaxIterations. |
| EvaluationLimitExceeded
|
The number of function evaluations needed to achieve the desired accuracy is greater than MaxEvaluations. |
| RoundOffError
|
Round-off prevented the algorithm from achieving the desired accuracy. |
| BadFunction
|
Bad behavior of the objective function prevented the algorithm from achieving the desired accuracy. |
| Divergent
|
The objective function appears to be unbounded. An extremum of the requested type could not be found. |
It is always prudent to verify the value of the Status property after the algorithm has run.
References
R. P. Brent, Algorithms for Minimization without Derivatives, Prentice-Hall, Englewood Cliffs, New
Jersey, 1973.
Up: Optimization Next: Multidimensional Optimization Previous: Optimization Contents
Copyright 2004-2008,
Extreme Optimization. All rights reserved.
Extreme Optimization, Complexity made simple, M#, and M
Sharp are trademarks of ExoAnalytics Inc.
Microsoft, Visual C#, Visual Basic, Visual Studio, Visual
Studio.NET, and the Visual Studio Logo are registered trademarks of Microsoft Corporation