MultiDimensionalSolver.GlobalAnnealing Method (ExtremumTypes, Double[], Int32, Double, Double, Double, Double, Int32)

Finds the location of the global extremum (i.e. minimum or maximum) of a general multidimensional function using the technique known as simulated annealing applied to a modified version of the Needler and Mead's downhill simplex algorithm.

public double[] GlobalAnnealing(
   ExtremumTypes extremumType,
   double[] initialPoint,
   int annealingSteps,
   double initialTemperature,
   double alpha,
   double radius,
   double fractionalTolerance,
   int stepIterations
);

Parameters

extremumType: Indicates the type of extreme searched: in the case of a minimum, extremumType == ExtremumTypes.MINIMUM; and in the case of a maximum, extremumType == ExtremumTypes.MAXIMUM.
initialPoint: The initial point about which the iterative optimization procedure starts. The initial point is given as an array where the n-th term of the array corresponds to the value of the n coordinate value.
annealingSteps: The number of steps for the Simulated Annealing which is performed before the algorithm exists. Note that the number of iterations used effects the level at which the surface is vibrated before the algorithm exits. A reasonable value to take for this parameter in most case is 2.
initialTemperature: The initial temperature which corresponds to the amount which the "surface" of shaken during the first iteration. After which the "surface" cools resulting in decreased shaking until the surface come to rest.
alpha: A constant indicating the non-linearity of the annealing process. The more non-linear (i.e. the worst) the object function is in terms of trying to find a global extremum the lower the value of alpha which should be given. Since the lower alpha, the slower the "shaking of the surface" will decrease, as explicit describe within the formula (*) given above.
radius: This parameter indicates the density of the randomly-chosen points of the initial simplex. Ideally this parameter should be large with a typical value being 1000.
fractionalTolerance: When the difference between the function values in two consecutive steps is less than fractionalTolerance, the point in the last step is considered a local extreme and returned. In most cases a reasonable value to take for this parameter is 0.0001, however if the object function in very oscillatory in a neighborhood of its extremum then a correspondingly larger value should be used. Note that here this parameter will correspond to the tolerance used by the Nelder and Mead algorithm since the Nelder and Mead Algorithm of the object function is treated like the underlying object function by the simulated annealing process.
stepIterations: The number of iterations used when the Nelder and Mead algorithm is used at each step of the annealing procedure. Naturally the higher the number of iterations used the greater the expected precision however the slower the algorithm will become. A reasonable value to take for this parameter is 300.

Return Value

The point in the N-dimensional space where the function has a global extremum.

Remarks

Overview of Approach

The general idea used here is that after each step within the selected algorithm for finding the local extremum, we perturb the point by a random jump corresponding to "temperature of the surface". The temperature of the surface starts from an initial value initialTemperature and is decreases by a constant ratio after each iteration (that is, the surface is allowed to cool). The rationale for this approach is that by "heating" the surface we vibrate it so that we are knocked out by the shaking of local extremum allow the continued search for the global extremum. When we are in the neighborhood of the global extremum (as long as the shaking is not to violent) we will stay within the vicinity of the global extremum as the surface is allowed to cool.

The exit conditions used within the implementation of Simulated Annealing is that if the previous 50 iterations is within the tolerance-neighborhood of the point found then the algorithm will exit the point found will be returned. Note that when using Simulated Annealing the jumps may force this condition to never be satisfied before the number of iterations performed has exceeded maxIterations, and am exception has been thrown.

Size of Jumps and the Rate of Cooling

The size of the random perturbations after each step and the rate at which the magnitude of these jumps decreases is explicitly given as follows. If the initial temperature (given as a parameter) is initialTemperature, then the initial size of the jump will be initialTemperature. After the k-th iteration of the Simulated Annealing the size of the random jump is given by:

(*)                 (1 - k / annealingSteps)^alpha

where annealingSteps is the maximum number of simulated annealing steps used and alpha is a parameters used in order to indicate the non-linearity, i.e how bad the object function is in terms of being able to find its global extremum.

When should this approach be used

This method is one of the two methods namely this method and general implementation, within this class which are specifically designed to find the global (rather than local) extremum of the given object function at hand. Both of these methods use the approach known as Simulated annealing, however this method in easier to use having many of the possible parameters such as the underlying algorithms used, the bracketing and location algorithms all being pre-set. Since this approach can be applied to general functions it is ideal for those who wish to get a solution up and running quickly for any global optimization problem. Having said this for problems where you have a differentiable object function for example you will find that by fine tuning general implementation you will be able to construct a more efficient algorithm.

Exceptions

Exception Type	Condition
MultiDimensionalException	Thrown if the delivered function does not implement MultiDimensionalFunction or an interface which extends MultiDimensionalFunction.