

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object org.jscience.mathematics.analysis.optimization.DirectSearchOptimizer
public abstract class DirectSearchOptimizer
This class implements simplexbased 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.
Simplexbased 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 singlestart or in
multistart mode. Multistart 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 multistart 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.
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 nonevaluated 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 multistart mode. 
Methods inherited from class java.lang.Object 

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Field Detail 

protected PointCostPair[] simplex
Constructor Detail 

protected DirectSearchOptimizer()
Method Detail 

public PointCostPair minimizes(CostFunction f, int maxEvaluations, ConvergenceChecker checker, double[] vertexA, double[] vertexB) throws CostException, NoConvergenceException
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 singlestart 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
NoConvergenceException
 if none of the starts did
converge (it is not thrown if at least one start did converge)public PointCostPair minimizes(CostFunction f, int maxEvaluations, ConvergenceChecker checker, double[] vertexA, double[] vertexB, int starts, int[] seed) throws CostException, NoConvergenceException
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 multistart 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), multistart is disabled if value is less than or
equal to 1seed
 seed for the random vector generator (32 bits
integers array). If null, the current time will be used for the
generator initialization.
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)public PointCostPair minimizes(CostFunction f, int maxEvaluations, ConvergenceChecker checker, double[][] vertices) throws CostException, NoConvergenceException
The simplex is built from all its vertices.
The optimization is performed in singlestart 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
NoConvergenceException
 if none of the starts did
converge (it is not thrown if at least one start did converge)public PointCostPair minimizes(CostFunction f, int maxEvaluations, ConvergenceChecker checker, double[][] vertices, int starts, int[] seed) throws NotPositiveDefiniteMatrixException, CostException, NoConvergenceException
The simplex is built from all its vertices.
The optimization is performed in multistart 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), multistart is disabled if value is less than or
equal to 1seed
 seed for the random vector generator (32 bits
integers array). If null, the current time will be used for the
generator initialization.
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)public PointCostPair minimizes(CostFunction f, int maxEvaluations, ConvergenceChecker checker, RandomVectorGenerator generator) throws CostException, NoConvergenceException
The simplex is built randomly.
The optimization is performed in singlestart 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
NoConvergenceException
 if none of the starts did
converge (it is not thrown if at least one start did converge)public PointCostPair minimizes(CostFunction f, int maxEvaluations, ConvergenceChecker checker, RandomVectorGenerator generator, int starts) throws CostException, NoConvergenceException
The simplex is built randomly.
The optimization is performed in multistart 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), multistart is disabled if value is less than or
equal to 1
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)public void setMultiStart(int starts, RandomVectorGenerator generator)
starts
 number of starts to perform (including the
first one), multistart is disabled if value is less than or
equal to 1generator
 random vector generator to use for restartspublic PointCostPair[] getMinima()
minimizes
.
The optimizer stores all the minima found during a set of
restarts when multistart 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 singlestart).
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
).
minimizes
has not been calledprotected abstract void iterateSimplex() throws CostException
CostException
protected 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 