MultiDimensionalSolver Class

The MultiDimensionalSolver class offers methods for finding the location of the extremum (i.e. minimum or maximum) of a function of many real variables (or equivalently, a function defined on a multi dimensional real space) with or without linear constraints.

For a list of all members of this type, see MultiDimensionalSolver Members.

System.Object
MultiDimensionalSolver

public class MultiDimensionalSolver

Remarks

Application of the class

Each of the procedures provided within this class proceeds by first being passed the object function of the optimization problem for which the location of the extremum is to be found. We then call one of the optimization procedures giving various parameters used to define procedure specific information such as the tolerance used and in the case of constrained optimization the constraints which must be satisfied. In most instances we are also required to provide an initial point from where the given optimization procedure will start its iterative search of the (local or global) extremum.

Overview of the Optimization

The aim of the theory of optimization is to find the location of the extremum (i.e. maximum or minimum) of a (possibly constrained) function defined over one or more (real) dimensions. An extremum point can be either local or global. A local extremum is a point such that the object function is known to obtain its highest (in the case of maximization) or lowest (in the case of minimization) value within a given sub-region of the entire domain over which the optimization problem is considered. A global extremum is the point at which the (object) function takes its maximum or minimum value over the entire domain for which the optimization problem is considered. Here we offer procedures which are designed for finding the local and global extremum.

Selecting an Algorithm for your Problem

You should select an optimization procedure to use in accordance with the properties of the optimization problem you are considering. In particular, you should take into account the following criteria when selecting the particular optimization procedure to use:

Object Function - Nature of the object function namely whether it is linear, continuous or continuously differentiable over the domain for which the optimization problem is considered.
Constraints - Whether the object function is constrained to satisfy inequality or equality constraints.
Local or Global - Whether a local or global extremum is sort.

By using this information and taking into account your particular applications needs you will able to select the most appropriate procedure to use.

Object Function Properties and the Selection of an Algorithm

Depending on the nature of the object function at hand will determine which of the algorithms firstly can be used and secondly which algorithm(s) are most appropriate. Below we give the algorithms which you should use in the case of optimization problems with a general or differentiable (multidimensional) object function:

In case of General Functions which are not necessarily even continuous. The Optimization Algorithms which should be considered in this case are:
1. NelderMead - Uses the downhill simplex method of Nelder and Mead to find a local minimum for the generic multidimensional function.
2. Powell - Seeks a local minimum of a generic multidimensional function using Powell's direction set method.
3. GlobalAnnealing - Finds the Global extremum of a general multidimensional function.
Though these algorithms deal with this general (i.e. possibly non-continuous) case even these algorithms will become more efficient as the object function considered gets more well-behaved (i.e. has properties such as is bounded, continuous, and so on).
Differentiable functions where the differential is not necessarily continuous. Through general algorithms can be applied in nearly all cases the specialized procedures described below which have been developed for problems with differentiable object functions will be much more effective and hence should be preferred:
1. DerivSteepestDescent - Applies the method of Steepest Descent to a differentiable function.
2. DerivFletcherPowell - Applies the method of Fletcher-Powell to a differentiable function.
3. DerivBFGS - Applies the Broyden-Fletcher-Goldfarb-Shanno algorithm to a differentiable function.
4. DerivPolakRiviere - Applies the Polak-Riviere algorithm to a differentiable function. The Polak-Riviere algorithm is generally much more efficient than the Steepest Descent algorithm (i.e. DerivSteepestDescent).
5. DerivFletcherReeves - Applies the Fletcher-Reeves algorithm to a differentiable function. The Fletcher-Reeves algorithm is generally much more efficient than the Steepest Descent algorithm (i.e. DerivSteepestDescent).
6. LinearConstraintRosen - Rosen's gradient projection algorithm which seeks a local minimum for the differentiable multidimensional real function under a set of linear constraints. Note that, this algorithm should only be used if your optimization problem is constrained.

Remark: If your object function is Linear then you should use the Simplex Algorithm found in the LinearProgramming class.

Optimization Constraints and the Selection of an Algorithm

At present we only offer algorithms which can treat problems with linear constraints. In instances where you have non-linear boundaries (i.e. boundaries which are not flat hyperplanes) you will need to linearize the boundaries in order to apply these algorithms. For optimization problems with linear constraints we offer:

LinearConstraintRosen for non-linear differentiable object function - Rosen's gradient projection. algorithm which seeks a local minimum for the differentiable multidimensional real function under a set of linear constraints.
For Linear Object functions - The Simplex algorithm MultiLinearSimplex, from the LinearProgramming class should be applied.

Local & Global Optimization and the Selection of an Algorithm

All the algorithms listed within this class will yield a local extremum for any compatible optimization problem. However, in practice it is often the global extremum which is sort and often a (local) extremum found will not turn out to be a global extremum for the given optimization problem at hand. In order to address this need the technique known as Simulated Annealing which can be applied `on top' of any of the optimization algorithms for finding the local extremum. This will greatly increase the chance of the global extremum. At present we offer the following Simulating Annealing enable (local) optimization procedures:

GlobalAnnealing - Nelder and Mead's downhill simplex algorithm is used together with a simple annealing schedule.

Remark: If the object function is linear then the Simplex algorithm should be used from the LinearProgramming class which will always yield a global extremum.

Further Remarks on Multi-Dimensional Optimization Problems

Constrained Optimization

An Optimization problem may also have constraints, such problems are referred to as constrained optimization. In the case of Linear Programming (see LinearProgramming) where the object function and constraints are linear there exists efficient and refined algorithms. However, for general multi-dimensional constrained optimization problems there are no known efficient general algorithms. Therefore in practice specific algorithms are developed to address particular instances of the general problem. We have implemented one such algorithm, known as Rosen's algorithm (see LinearConstraintRosen) which deals with the case when the constraints are linear and the object function is differentiable.

Continuous and Differentiable Object Functions

As mentioned above the algorithms implemented within this class work most efficiently when the functions are `well behaved'. Generally speaking what we mean by `well behaved' is that the smoother the function more `well behaved' the function is. The more `well behaved the function the more efficient and stable the optimization algorithms contained within the class will be when applied to the given function at hand. This principle is true whether we are dealing within general or differentiable functions. The reason for this is that the `greedy type' algorithms implemented here (excluding simulated annealing) have as there basis that at each iterative step we move to the extremum point within a given neighborhood lying in one of a number of chosen directions. Such `greedy type' or calculus inspired arguments work more effectively as the function which it is applied to gets smoother.

Remark: In practice, the requirement that the majority of the procedures within this class require that the object function is continuous or even differentiable is not restrictive since in most practical applications. The reason being that processes generated from real world systems such as economic systems are in nearly all cases continuous and even differentiable.

Object Functions which take NaN values

It is also important to point out that though we may consider non-continuous functions with some of the algorithms these functions must never return a NaN (Not a number). In order to guarantee this we must ensure that for all points within the domain over which the optimization problem is considered the object function does not return such as value. If such an value is returned, the algorithms will exit and throw an InvalidMultiDimensionalFunctionException exception. If this exception is thrown then you will be able to call methods within the Exception class which provide the point where the function evaluates to Double.NaN. By modifying your given function at points where it returns a NaN you should be able to modify the optimization problem so that the essential features of the underlying problem are preserved but the optimization algorithm can be successfully applied.

Local and Global Extremum

As mentioned before the local extremum (i.e. minimum or maximum) is just the extremum in a neighborhood of a point, where as the global extremum is the extremum on the whole domain over which the optimization problem is considered. In practice it is generally the global extremum which is desired but this problem in general is very difficult. The difficulty lies in the fact that `greedy type' optimization methods used here are an abstraction of methods based on differential calculus and hence use the local differentiable information about function in order to move closer to the extremum. The problem with such local methods is that even if they find a (local) extremum they have no way of knowing whether that (local) extremum is in fact the global extremum.

In the case of uni-dimensional optimization there are effective algorithms for finding the global extremum; for example UniDimensionalSolver.globalExtremeDeriv, GlobalExtreme. However, in the multi-dimensional case we are required to use one of the three approaches:

Find local extrema starting from widely varying starting values of the independent variables (perhaps chosen pseudo-randomly), and then pick the most extreme of these.
Perturb a local extremum by taking a finite-amplitude step away from it, and then see if the local method returns a "better" point or "always" the same one.
A totally different approach is taken by simulated annealing methods, which use an analogy with thermodynamics: the idea is to vibrate the surface on which the iterative search is performed and slowly reduce the vibration. In the language of thermodynamics this would mean heat up the physical system and allow it to slowly cool as the particle moves around the surface until to finds its equilibrium in the state of minimum energy. We have implement simulated annealing for the Nelder-Mead algorithm within GlobalAnnealing.

The first two approaches listed above are heuristic in nature and should be applied with particular insight into the problem at hand. The third approach simulated annealing is a general technique which can be applied to any of the standard local multi-dimensional optimization algorithms in order to transform them from an algorithm design to find local extremum to an algorithm which is much more likely to find a global extremum (see GlobalAnnealing or the PDF documentation for more details).

Setting the Optimization Problems Object Function

Before any of the optimization procedures offered within this class are called the multi-dimensional object function must be set using either SetFunction, or by passing the object function with the constructor of this MultiDimensionalSolver class.

Remark: It your clients uses threads then it should be pointed out that the procedure using SetFunction is not thread safe.

MultiDimensionalException and setting the Object Function

The MultiDimensionalException is thrown if a function is not set in the case of application of methods which require (general) functions, or if the differentiable function is not set, that is you do not also supply the derivative.

List of Algorithms Available

Detailed Overview of the Multi-Dimensional Optimization Functionality Available

Within this class we offer eight algorithms aimed at unconstrained optimization with object functions will differing qualitative properties and one algorithm for constrained optimization.

Multi-dimensional Unconstrained Optimization Algorithms Available

NelderMead - Uses the downhill simplex method of Nelder and Mead to find a local minimum for the generic multidimensional function.
Powell - Seeks a local minimum of a generic multidimensional function using Powell's direction set method.
DerivSteepestDescent - Requires differentiable function.
DerivFletcherPowell - Requires differentiable function.
DerivBFGS - Uses Broyden-Fletcher-Goldfarb-Shanno algorithm which requires differentiable function.
DerivPolakRiviere - Uses Polak-Riviere algorithm which is much more efficient than Steepest Descent.
DerivFletcherReeves - Uses Fletcher-Reeves algorithm which is much more efficient than Steepest Descent.
GlobalAnnealing - This is the only global multidimensional algorithm which can be applied to optimization problems where the object function is non-differentiable.

Multi-dimensional Constrained Optimization Algorithms Available

LinearConstraintRosen - Rosen's gradient projection algorithm which seeks a local minimum for the differentiable multidimensional real function under linear a set of linear constraints.

Requirements

Namespace: WebCab.COM.Math.Optimization.MultiDimensional

Assembly: WebCab.COM.Optimization (in WebCab.COM.Optimization.dll)