NMath - 27.1 Minimizing Functions Without Calculating the Derivative (.NET, C#, CSharp, VB, Visual Basic, F#)

27.1 Minimizing Functions Without Calculating the Derivative (.NET, C#, CSharp, VB, Visual Basic, F#)

NMath provides two classes that implement the IMultiVariableMinimizer interface, and minimize a MultiVariableFunction using only function evaluations (derivative calculations are not required):

● Class DownhillSimplexMinimizer minimizes a multivariate function using the downhill simplex method of Nelder and Mead.¹ A simplex in n-dimensions consists of n+1 distinct vertices. The method involves moving the simplex downhill, or if that is not possible, shrinking its size. The method is not highly efficient, and is appropriate only for small numbers of variables (usually fewer than 6), but is very robust. Powell's Method is faster in most applications (see below).

● Class PowellMinimizer minimizes a multivariate function using Powell's Method. Powell's Method is a member of the family of direction set optimization methods, each of which is based on a series of one-dimensional line minimizations. The methods differ in how they choose the next dimension at each stage from among a current set of candidates. Powell's Method begins with a set of N linearly independent, mutually conjugate directions, and at each stage discards the direction in which the function made its largest decrease, to avoid a buildup of linear dependence. Brent's Method (Section 26.2) is used for the successive line minimizations.

Instances of DownhillSimplexMinimizer and PowellMinimizer are constructed by specifying an error tolerance and a maximum number of iterations, or by accepting the defaults for these values. For example, this code constructs a PowellMinimizer using the default tolerance and a maximum of 20 iterations:

Code Example – C# minimization

int maxIter = 20;

var minimizer = new PowellMinimizer( maxIter );

Code Example – VB minimization

Dim MaxIter As Integer = 20

Dim Minimizer As New PowellMinimizer(MaxIter)

Class DownhillSimplexMinimizer and PowellMinimizer implement the IMultiVariableMinimizer interface, which provides a single Minimize() method that takes a MultiVariableFunction to minimize, and a starting point. For instance, if f is an encapsulated multivariate function (Chapter 25) of three variables, this code minimizes the function using the downhill simplex method, starting at the origin:

Code Example – C# minimization

var minimizer = new DownhillSimplexMinimizer();

var start = new DoubleVector( 0.0, 0.0, 0.0 );

DoubleVector min = minimizer.Minimize( f, start );

Code Example – VB minimization

Dim Minimizer As New DownhillSimplexMinimizer()

Dim Start As New DoubleVector(0.0, 0.0, 0.0)

Dim Min As DoubleVector = Minimizer.Minimize(F, Start)

Both DownhillSimplexMinimizer and PowellMinimizer provide additional overloads of Minimize() that allow you more control over the initial conditions. The downhill simplex method, for example, begins with an initial simplex consisting of n+1 distinct vertices. If you provide only a starting point, as illustrated above, a starting simplex is constructed by adding 1.0 in each dimension. For example, in two dimensions the simplex is a triangle. If the starting point is (x₀, x₁), the remaining vertices of the starting simplex will be (x₀+1, x₁) and (x₀, x₁+1). Overloads of the Minimize() method allow you to specify the amount added in each dimension from the starting point when constructing the initial simplex, or simply to specify the initial simplex itself.

Similarly, Powell's Method begins with an initial direction set, a set of N linearly independent, mutually conjugate directions. An overload of Minimize() enables you to specify the initial direction set. If you provide only a starting point to the Minimize() method, as illustrated above, the starting direction set is simply the unit vectors.

J. A. Nelder and R. Mead (1965), "A Simplex Method for Function Minimization," Computer Journal, Vol. 7, p. 308-313.

Top