|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.apache.commons.math.optimization.DirectSearchOptimizer
public abstract class DirectSearchOptimizer
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.
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 |
---|
private static java.util.Comparator pointCostPairComparator
PointCostPair
objects.
protected PointCostPair[] simplex
private CostFunction f
private int evaluations
private int starts
private RandomVectorGenerator generator
private PointCostPair[] minima
Constructor Detail |
---|
protected DirectSearchOptimizer()
Method Detail |
---|
public PointCostPair minimize(CostFunction f, int maxEvaluations, ConvergenceChecker checker, double[] vertexA, double[] vertexB) throws CostException, ConvergenceException
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.
f
- cost functionmaxEvaluations
- 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 convergencevertexA
- first vertexvertexB
- last vertex
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)public PointCostPair minimize(CostFunction f, int maxEvaluations, ConvergenceChecker checker, double[] vertexA, double[] vertexB, int starts, long seed) throws CostException, ConvergenceException
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.
f
- cost functionmaxEvaluations
- 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 convergencevertexA
- first vertexvertexB
- last vertexstarts
- number of starts to perform (including the
first one), multi-start is disabled if value is less than or
equal to 1seed
- seed for the random vector generator
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)public PointCostPair minimize(CostFunction f, int maxEvaluations, ConvergenceChecker checker, double[][] vertices) throws CostException, ConvergenceException
The simplex is built from all its vertices.
The optimization is performed in single-start mode.
f
- cost functionmaxEvaluations
- 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 convergencevertices
- array containing all vertices of the simplex
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)public PointCostPair minimize(CostFunction f, int maxEvaluations, ConvergenceChecker checker, double[][] vertices, int starts, long seed) throws NotPositiveDefiniteMatrixException, CostException, ConvergenceException
The simplex is built from all its vertices.
The optimization is performed in multi-start mode.
f
- cost functionmaxEvaluations
- 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 convergencevertices
- array containing all vertices of the simplexstarts
- number of starts to perform (including the
first one), multi-start is disabled if value is less than or
equal to 1seed
- seed for the random vector generator
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)public PointCostPair minimize(CostFunction f, int maxEvaluations, ConvergenceChecker checker, RandomVectorGenerator generator) throws CostException, ConvergenceException
The simplex is built randomly.
The optimization is performed in single-start mode.
f
- cost functionmaxEvaluations
- 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 convergencegenerator
- random vector generator
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)public PointCostPair minimize(CostFunction f, int maxEvaluations, ConvergenceChecker checker, RandomVectorGenerator generator, int starts) throws CostException, ConvergenceException
The simplex is built randomly.
The optimization is performed in multi-start mode.
f
- cost functionmaxEvaluations
- 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 convergencegenerator
- random vector generatorstarts
- number of starts to perform (including the
first one), multi-start is disabled if value is less than or
equal to 1
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)private void buildSimplex(double[] vertexA, double[] vertexB)
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.
vertexA
- first vertexvertexB
- last vertexprivate void buildSimplex(double[][] vertices)
vertices
- array containing all vertices of the simplexprivate void buildSimplex(RandomVectorGenerator generator)
generator
- random vector generatorprivate void setSingleStart()
private void setMultiStart(int starts, RandomVectorGenerator generator)
starts
- number of starts to perform (including the
first one), multi-start is disabled if value is less than or
equal to 1generator
- random vector generator to use for restartspublic PointCostPair[] getMinima()
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
).
minimize
has not been calledprivate PointCostPair minimize(CostFunction f, int maxEvaluations, ConvergenceChecker checker) throws CostException, ConvergenceException
f
- cost functionmaxEvaluations
- 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
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)protected abstract void iterateSimplex() throws CostException
CostException
- if the function cannot be evaluated at
some pointprotected double evaluateCost(double[] x) throws CostException
A side effect of this method is to count the number of function evaluations
x
- point on which the cost function should be evaluated
CostException
- if no cost can be computed for the parametersprotected void evaluateSimplex() throws CostException
CostException
- if no cost can be computed for the parametersprotected void replaceWorstPoint(PointCostPair pointCostPair)
pointCostPair
- point to insert
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |