org.jscience.mathematics.analysis.optimization
Class DirectSearchOptimizer

java.lang.Object
  extended by org.jscience.mathematics.analysis.optimization.DirectSearchOptimizer
Direct Known Subclasses:
MultiDirectional, NelderMead

public abstract class DirectSearchOptimizer
extends java.lang.Object

This class implements simplex-based direct search optimization algorithms.

Direct search method only use cost function values, they don't need derivatives and don't either try to compute approximation of the derivatives. According to a 1996 paper by Margaret H. Wright (Direct Search Methods: Once Scorned, Now Respectable), they are used when either the computation of the derivative is impossible (noisy functions, unpredictable dicontinuities) or difficult (complexity, computation cost). In the first cases, rather than an optimum, a not too bad point is desired. In the latter cases, an optimum is desired but cannot be reasonably found. In all cases direct search methods can be useful.

Simplex-based direct search methods are based on comparison of the cost function values at the vertices of a simplex (which is a set of n+1 points in dimension n) that is updated by the algorithms steps.

The instances can be built either in single-start or in multi-start mode. Multi-start is a traditional way to try to avoid beeing trapped in a local minimum and miss the global minimum of a function. It can also be used to verify the convergence of an algorithm. In multi-start mode, the minimizes method returns the best minimum found after all starts, and the getMinima method can be used to retrieve all minima from all starts (including the one already provided by the minimizes method).

This class is the base class performing the boilerplate simplex initialization and handling. The simplex update by itself is performed by the derived classes according to the implemented algorithms.

See Also:
CostFunction, NelderMead, MultiDirectional

Field Summary
protected  PointCostPair[] simplex
          Simplex.
 
Constructor Summary
protected DirectSearchOptimizer()
          Simple constructor.
 
Method Summary
protected  double evaluateCost(double[] x)
          Evaluate the cost on one point.
protected  void evaluateSimplex()
          Evaluate all the non-evaluated points of the simplex.
 PointCostPair[] getMinima()
          Get all the minima found during the last call to minimizes.
protected abstract  void iterateSimplex()
          Compute the next simplex of the algorithm.
 PointCostPair minimizes(CostFunction f, int maxEvaluations, ConvergenceChecker checker, double[][] vertices)
          Minimizes a cost function.
 PointCostPair minimizes(CostFunction f, int maxEvaluations, ConvergenceChecker checker, double[][] vertices, int starts, int[] seed)
          Minimizes a cost function.
 PointCostPair minimizes(CostFunction f, int maxEvaluations, ConvergenceChecker checker, double[] vertexA, double[] vertexB)
          Minimizes a cost function.
 PointCostPair minimizes(CostFunction f, int maxEvaluations, ConvergenceChecker checker, double[] vertexA, double[] vertexB, int starts, int[] seed)
          Minimizes a cost function.
 PointCostPair minimizes(CostFunction f, int maxEvaluations, ConvergenceChecker checker, RandomVectorGenerator generator)
          Minimizes a cost function.
 PointCostPair minimizes(CostFunction f, int maxEvaluations, ConvergenceChecker checker, RandomVectorGenerator generator, int starts)
          Minimizes a cost function.
protected  void replaceWorstPoint(PointCostPair pointCostPair)
          Replace the worst point of the simplex by a new point.
 void setMultiStart(int starts, RandomVectorGenerator generator)
          Set up multi-start mode.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

simplex

protected PointCostPair[] simplex
Simplex.

Constructor Detail

DirectSearchOptimizer

protected DirectSearchOptimizer()
Simple constructor.

Method Detail

minimizes

public PointCostPair minimizes(CostFunction f,
                               int maxEvaluations,
                               ConvergenceChecker checker,
                               double[] vertexA,
                               double[] vertexB)
                        throws CostException,
                               NoConvergenceException
Minimizes a cost function.

The initial simplex is built from two vertices that are considered to represent two opposite vertices of a box parallel to the canonical axes of the space. The simplex is the subset of vertices encountered while going from vertexA to vertexB travelling along the box edges only. This can be seen as a scaled regular simplex using the projected separation between the given points as the scaling factor along each coordinate axis.

The optimization is performed in single-start mode.

Parameters:
f - cost function
maxEvaluations - maximal number of function calls for each start (note that the number will be checked after complete simplices have been evaluated, this means that in some cases this number will be exceeded by a few units, depending on the dimension of the problem)
checker - object to use to check for convergence
vertexA - first vertex
vertexB - last vertex
Returns:
the point/cost pairs giving the minimal cost
Throws:
CostException - if the cost function throws one during the search
NoConvergenceException - if none of the starts did converge (it is not thrown if at least one start did converge)

minimizes

public PointCostPair minimizes(CostFunction f,
                               int maxEvaluations,
                               ConvergenceChecker checker,
                               double[] vertexA,
                               double[] vertexB,
                               int starts,
                               int[] seed)
                        throws CostException,
                               NoConvergenceException
Minimizes a cost function.

The initial simplex is built from two vertices that are considered to represent two opposite vertices of a box parallel to the canonical axes of the space. The simplex is the subset of vertices encountered while going from vertexA to vertexB travelling along the box edges only. This can be seen as a scaled regular simplex using the projected separation between the given points as the scaling factor along each coordinate axis.

The optimization is performed in multi-start mode.

Parameters:
f - cost function
maxEvaluations - maximal number of function calls for each start (note that the number will be checked after complete simplices have been evaluated, this means that in some cases this number will be exceeded by a few units, depending on the dimension of the problem)
checker - object to use to check for convergence
vertexA - first vertex
vertexB - last vertex
starts - number of starts to perform (including the first one), multi-start is disabled if value is less than or equal to 1
seed - seed for the random vector generator (32 bits integers array). If null, the current time will be used for the generator initialization.
Returns:
the point/cost pairs giving the minimal cost
Throws:
CostException - if the cost function throws one during the search
NoConvergenceException - if none of the starts did converge (it is not thrown if at least one start did converge)

minimizes

public PointCostPair minimizes(CostFunction f,
                               int maxEvaluations,
                               ConvergenceChecker checker,
                               double[][] vertices)
                        throws CostException,
                               NoConvergenceException
Minimizes a cost function.

The simplex is built from all its vertices.

The optimization is performed in single-start mode.

Parameters:
f - cost function
maxEvaluations - maximal number of function calls for each start (note that the number will be checked after complete simplices have been evaluated, this means that in some cases this number will be exceeded by a few units, depending on the dimension of the problem)
checker - object to use to check for convergence
vertices - array containing all vertices of the simplex
Returns:
the point/cost pairs giving the minimal cost
Throws:
CostException - if the cost function throws one during the search
NoConvergenceException - if none of the starts did converge (it is not thrown if at least one start did converge)

minimizes

public PointCostPair minimizes(CostFunction f,
                               int maxEvaluations,
                               ConvergenceChecker checker,
                               double[][] vertices,
                               int starts,
                               int[] seed)
                        throws NotPositiveDefiniteMatrixException,
                               CostException,
                               NoConvergenceException
Minimizes a cost function.

The simplex is built from all its vertices.

The optimization is performed in multi-start mode.

Parameters:
f - cost function
maxEvaluations - maximal number of function calls for each start (note that the number will be checked after complete simplices have been evaluated, this means that in some cases this number will be exceeded by a few units, depending on the dimension of the problem)
checker - object to use to check for convergence
vertices - array containing all vertices of the simplex
starts - number of starts to perform (including the first one), multi-start is disabled if value is less than or equal to 1
seed - seed for the random vector generator (32 bits integers array). If null, the current time will be used for the generator initialization.
Returns:
the point/cost pairs giving the minimal cost
Throws:
NotPositiveDefiniteMatrixException - if the vertices array is degenerated
CostException - if the cost function throws one during the search
NoConvergenceException - if none of the starts did converge (it is not thrown if at least one start did converge)

minimizes

public PointCostPair minimizes(CostFunction f,
                               int maxEvaluations,
                               ConvergenceChecker checker,
                               RandomVectorGenerator generator)
                        throws CostException,
                               NoConvergenceException
Minimizes a cost function.

The simplex is built randomly.

The optimization is performed in single-start mode.

Parameters:
f - cost function
maxEvaluations - maximal number of function calls for each start (note that the number will be checked after complete simplices have been evaluated, this means that in some cases this number will be exceeded by a few units, depending on the dimension of the problem)
checker - object to use to check for convergence
generator - random vector generator
Returns:
the point/cost pairs giving the minimal cost
Throws:
CostException - if the cost function throws one during the search
NoConvergenceException - if none of the starts did converge (it is not thrown if at least one start did converge)

minimizes

public PointCostPair minimizes(CostFunction f,
                               int maxEvaluations,
                               ConvergenceChecker checker,
                               RandomVectorGenerator generator,
                               int starts)
                        throws CostException,
                               NoConvergenceException
Minimizes a cost function.

The simplex is built randomly.

The optimization is performed in multi-start mode.

Parameters:
f - cost function
maxEvaluations - maximal number of function calls for each start (note that the number will be checked after complete simplices have been evaluated, this means that in some cases this number will be exceeded by a few units, depending on the dimension of the problem)
checker - object to use to check for convergence
generator - random vector generator
starts - number of starts to perform (including the first one), multi-start is disabled if value is less than or equal to 1
Returns:
the point/cost pairs giving the minimal cost
Throws:
CostException - if the cost function throws one during the search
NoConvergenceException - if none of the starts did converge (it is not thrown if at least one start did converge)

setMultiStart

public void setMultiStart(int starts,
                          RandomVectorGenerator generator)
Set up multi-start mode.

Parameters:
starts - number of starts to perform (including the first one), multi-start is disabled if value is less than or equal to 1
generator - random vector generator to use for restarts

getMinima

public PointCostPair[] getMinima()
Get all the minima found during the last call to minimizes.

The optimizer stores all the minima found during a set of restarts when multi-start mode is enabled. The minimizes method returns the best point only. This method returns all the points found at the end of each starts, including the best one already returned by the minimizes method. The array as one element for each start as specified in the constructor (it has one element only if optimizer has been set up for single-start).

The array containing the minima is ordered with the results from the runs that did converge first, sorted from lowest to highest minimum cost, and null elements corresponding to the runs that did not converge (all elements will be null if the minimizes method throwed a NoConvergenceException).

Returns:
array containing the minima, or null if minimizes has not been called

iterateSimplex

protected abstract void iterateSimplex()
                                throws CostException
Compute the next simplex of the algorithm.

Throws:
CostException

evaluateCost

protected double evaluateCost(double[] x)
                       throws CostException
Evaluate the cost on one point.

A side effect of this method is to count the number of function evaluations

Parameters:
x - point on which the cost function should be evaluated
Returns:
cost at the given point
Throws:
CostException - if no cost can be computed for the parameters

evaluateSimplex

protected void evaluateSimplex()
                        throws CostException
Evaluate all the non-evaluated points of the simplex.

Throws:
CostException - if no cost can be computed for the parameters

replaceWorstPoint

protected void replaceWorstPoint(PointCostPair pointCostPair)
Replace the worst point of the simplex by a new point.

Parameters:
pointCostPair - point to insert