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.

Many one-dimensional optimization algorithms have been developed. Extreme Numerics.NET support the most popular ones.

Golden Section 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.

All one-dimensional optimization classes share a common interface defined by the OneDimensionalOptimizer class. The ObjectiveFunction property is a Func<T, TResult> delegate that specifies the objective function. Alternatively, when using .NET 4.0, you can use the SymbolicObjectiveFunction property to a lambda expression that represents the objective function. In this case, the derivative of the objective function is computed using Automatic Differentiation. The ExtremumType property specifies whether a minimum or a maximum is to be found. Its values are as follows:

The following example defines the cubic function x³-2x-5, and constructs a BrentOptimizer to find a local maximum of the function:

BrentOptimizer optimizer = new BrentOptimizer();
optimizer.ObjectiveFunction = x => x * x * x - 2 * x - 5;
optimizer.ExtremumType = ExtremumType.Maximum;

Dim optimizer As BrentOptimizer = New BrentOptimizer()
optimizer.ObjectiveFunction = Function(x) x * x * x - 2 * x - 5
optimizer.ExtremumType = ExtremumType.Maximum

No code example is currently available or this language may not be supported.

let optimizer = BrentOptimizer()
optimizer.ObjectiveFunction <- fun x -> x * x * x - 2.0 * x - 5.0
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 arguments: 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 arguments. 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:

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);

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)

No code example is currently available or this language may not be supported.

optimizer.FindBracket(0.0, 6.0)
if (not optimizer.IsBracketValid) then failwith "No bracket found."
let max = 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 arguments. The first is a Func<T, TResult> delegate that specifies the objective function. The second and third parameters are the boundaries of a suggested bracketing interval. The second overload takes two arguments. 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:

Func<double, double> f = x => x * x * x - 2 * x - 5;
double min = optimizer.FindMinimum(f, 0);
double max = optimizer.FindMaximum(f, 0);

Dim f As Func(Of Double, Double) = Function(x) x * x * x - 2 * x - 5
Dim min As Double = optimizer.FindMinimum(f, 0)
Dim max As Double = optimizer.FindMaximum(f, 0)

No code example is currently available or this language may not be supported.

let f = Func<_,_>(fun x -> x * x * x - 2.0 * x - 5.0)
let min = optimizer.FindMinimum(f, 0.0)
let max = optimizer.FindMaximum(f, 0.0)
//

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.

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.