org.spaceroots.mantissa.optimization

Class DirectSearchOptimizer

java.lang.Object

org.spaceroots.mantissa.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.

Version:

$Id: DirectSearchOptimizer.java 1709 2006-12-03 21:16:50Z luc $

Author:

Luc Maisonobe

See Also:

CostFunction, NelderMead, MultiDirectional

Field Summary

Fields

Modifier and Type	Field and Description
protected PointCostPair[]	simplex Simplex.

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	DirectSearchOptimizer() Simple constructor.

Method Summary

Modifier and Type	Method and Description
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