org.apache.commons.math.optimization
Class DirectSearchOptimizer

java.lang.Object
  extended by org.apache.commons.math.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 methods 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.

Minimization can be attempted either in single-start or in multi-start mode. Multi-start is a traditional way to try to avoid being 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. The various multi-start-enabled minimize methods return 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 minimize 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.

Since:
1.2
Version:
$Revision: 628000 $ $Date: 2008-02-15 03:31:48 -0700 (Fri, 15 Feb 2008) $
See Also:
CostFunction, NelderMead, MultiDirectional

Field Summary
private  int evaluations
          Number of evaluations already performed.
private  CostFunction f
          Cost function.
private  RandomVectorGenerator generator
          Random generator for multi-start.
private  PointCostPair[] minima
          Found minima.
private static java.util.Comparator pointCostPairComparator
          Comparator for PointCostPair objects.
protected  PointCostPair[] simplex
          Simplex.
private  int starts
          Number of starts to go.
 
Constructor Summary
protected DirectSearchOptimizer()
          Simple constructor.
 
Method Summary
private  void buildSimplex(double[][] vertices)
          Build a simplex from all its points.
private  void buildSimplex(double[] vertexA, double[] vertexB)
          Build a simplex from two extreme vertices.
private  void buildSimplex(RandomVectorGenerator generator)
          Build a simplex randomly.
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 minimize.
protected abstract  void iterateSimplex()
          Compute the next simplex of the algorithm.
private  PointCostPair minimize(CostFunction f, int maxEvaluations, ConvergenceChecker checker)
          Minimizes a cost function.
 PointCostPair minimize(CostFunction f, int maxEvaluations, ConvergenceChecker checker, double[][] vertices)
          Minimizes a cost function.
 PointCostPair minimize(CostFunction f, int maxEvaluations, ConvergenceChecker checker, double[][] vertices, int starts, long seed)
          Minimizes a cost function.
 PointCostPair minimize(CostFunction f, int maxEvaluations, ConvergenceChecker checker, double[] vertexA, double[] vertexB)
          Minimizes a cost function.
 PointCostPair minimize(CostFunction f, int maxEvaluations, ConvergenceChecker checker, double[] vertexA, double[] vertexB, int starts, long seed)
          Minimizes a cost function.
 PointCostPair minimize(CostFunction f, int maxEvaluations, ConvergenceChecker checker, RandomVectorGenerator generator)
          Minimizes a cost function.
 PointCostPair minimize(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.
private  void setMultiStart(int starts, RandomVectorGenerator generator)
          Set up multi-start mode.
private  void setSingleStart()
          Set up single-start mode.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

pointCostPairComparator

private static java.util.Comparator pointCostPairComparator
Comparator for PointCostPair objects.


simplex

protected PointCostPair[] simplex
Simplex.


f

private CostFunction f
Cost function.


evaluations

private int evaluations
Number of evaluations already performed.


starts

private int starts
Number of starts to go.


generator

private RandomVectorGenerator generator
Random generator for multi-start.


minima

private PointCostPair[] minima
Found minima.

Constructor Detail

DirectSearchOptimizer

protected DirectSearchOptimizer()
Simple constructor.

Method Detail

minimize

public PointCostPair minimize(CostFunction f,
                              int maxEvaluations,
                              ConvergenceChecker checker,
                              double[] vertexA,
                              double[] vertexB)
                       throws CostException,
                              ConvergenceException
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 traveling 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
ConvergenceException - if none of the starts did converge (it is not thrown if at least one start did converge)

minimize

public PointCostPair minimize(CostFunction f,
                              int maxEvaluations,
                              ConvergenceChecker checker,
                              double[] vertexA,
                              double[] vertexB,
                              int starts,
                              long seed)
                       throws CostException,
                              ConvergenceException
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 traveling 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
Returns:
the point/cost pairs giving the minimal cost
Throws:
CostException - if the cost function throws one during the search
ConvergenceException - if none of the starts did converge (it is not thrown if at least one start did converge)

minimize

public PointCostPair minimize(CostFunction f,
                              int maxEvaluations,
                              ConvergenceChecker checker,
                              double[][] vertices)
                       throws CostException,
                              ConvergenceException
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
ConvergenceException - if none of the starts did converge (it is not thrown if at least one start did converge)

minimize

public PointCostPair minimize(CostFunction f,
                              int maxEvaluations,
                              ConvergenceChecker checker,
                              double[][] vertices,
                              int starts,
                              long seed)
                       throws NotPositiveDefiniteMatrixException,
                              CostException,
                              ConvergenceException
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
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
ConvergenceException - if none of the starts did converge (it is not thrown if at least one start did converge)

minimize

public PointCostPair minimize(CostFunction f,
                              int maxEvaluations,
                              ConvergenceChecker checker,
                              RandomVectorGenerator generator)
                       throws CostException,
                              ConvergenceException
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
ConvergenceException - if none of the starts did converge (it is not thrown if at least one start did converge)

minimize

public PointCostPair minimize(CostFunction f,
                              int maxEvaluations,
                              ConvergenceChecker checker,
                              RandomVectorGenerator generator,
                              int starts)
                       throws CostException,
                              ConvergenceException
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
ConvergenceException - if none of the starts did converge (it is not thrown if at least one start did converge)

buildSimplex

private void buildSimplex(double[] vertexA,
                          double[] vertexB)
Build a simplex from two extreme vertices.

The two vertices 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 traveling 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.

Parameters:
vertexA - first vertex
vertexB - last vertex

buildSimplex

private void buildSimplex(double[][] vertices)
Build a simplex from all its points.

Parameters:
vertices - array containing all vertices of the simplex

buildSimplex

private void buildSimplex(RandomVectorGenerator generator)
Build a simplex randomly.

Parameters:
generator - random vector generator

setSingleStart

private void setSingleStart()
Set up single-start mode.


setMultiStart

private 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 minimize.

The optimizer stores all the minima found during a set of restarts when multi-start mode is enabled. The minimize 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 minimize 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 minimize method did throw a ConvergenceException).

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

minimize

private PointCostPair minimize(CostFunction f,
                               int maxEvaluations,
                               ConvergenceChecker checker)
                        throws CostException,
                               ConvergenceException
Minimizes a cost function.

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
Returns:
the point/cost pairs giving the minimal cost
Throws:
CostException - if the cost function throws one during the search
ConvergenceException - if none of the starts did converge (it is not thrown if at least one start did converge)

iterateSimplex

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

Throws:
CostException - if the function cannot be evaluated at some point

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