# 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.
**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.

## The OneDimensionalOptimizer 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:

Item | Description |
---|---|

Maximum | A maximum is to be found. |

Minimum | A minimum is to be found. |

The following example defines the cubic function *x*^{3}-2*x*-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;
```

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

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

## 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.