Class DirectSearchOptimizer
- All Implemented Interfaces:
MultivariateRealOptimizer
- Direct Known Subclasses:
MultiDirectional
,NelderMead
Direct search methods only use objective 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 discontinuities) 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 objective 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 initial configuration of the simplex can be set using either
setStartConfiguration(double[])
or setStartConfiguration(double[][])
. If neither method has been called
before optimization is attempted, an explicit call to the first method
with all steps set to +1 is triggered, thus building a default
configuration from a unit hypercube. Each call to optimize
will reuse
the current start configuration and move it such that its first vertex
is at the provided start point of the optimization. If the optimize
method is called to solve a different problem and the number of parameters
change, the start configuration will be reset to a default one with the
appropriate dimensions.
If setConvergenceChecker(RealConvergenceChecker)
is not called,
a default SimpleScalarValueChecker
is used.
Convergence is checked by providing the worst points of previous and current simplex to the convergence checker, not the best ones.
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.
implements MultivariateRealOptimizer since 2.0- Since:
- 1.2
- Version:
- $Revision: 1070725 $ $Date: 2011-02-15 02:31:12 +0100 (mar. 15 févr. 2011) $
- See Also:
-
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprotected double
evaluate
(double[] x) Evaluate the objective function on one point.protected void
evaluateSimplex
(Comparator<RealPointValuePair> comparator) Evaluate all the non-evaluated points of the simplex.Get the convergence checker.int
Get the number of evaluations of the objective function.int
Get the number of iterations realized by the algorithm.int
Get the maximal number of functions evaluations.int
Get the maximal number of iterations of the algorithm.protected void
Increment the iterations counter by 1.protected abstract void
iterateSimplex
(Comparator<RealPointValuePair> comparator) Compute the next simplex of the algorithm.optimize
(MultivariateRealFunction function, GoalType goalType, double[] startPoint) Optimizes an objective function.protected void
replaceWorstPoint
(RealPointValuePair pointValuePair, Comparator<RealPointValuePair> comparator) Replace the worst point of the simplex by a new point.void
setConvergenceChecker
(RealConvergenceChecker convergenceChecker) Set the convergence checker.void
setMaxEvaluations
(int maxEvaluations) Set the maximal number of functions evaluations.void
setMaxIterations
(int maxIterations) Set the maximal number of iterations of the algorithm.void
setStartConfiguration
(double[] steps) Set start configuration for simplex.void
setStartConfiguration
(double[][] referenceSimplex) Set start configuration for simplex.
-
Field Details
-
simplex
Simplex.
-
-
Constructor Details
-
DirectSearchOptimizer
protected DirectSearchOptimizer()Simple constructor.
-
-
Method Details
-
setStartConfiguration
Set start configuration for simplex.The start configuration for simplex is built from a box parallel to the canonical axes of the space. The simplex is the subset of vertices of a box parallel to the canonical axes. It is built as the path followed while traveling from one vertex of the box to the diagonally opposite vertex moving only along the box edges. The first vertex of the box will be located at the start point of the optimization.
As an example, in dimension 3 a simplex has 4 vertices. Setting the steps to (1, 10, 2) and the start point to (1, 1, 1) would imply the start simplex would be: { (1, 1, 1), (2, 1, 1), (2, 11, 1), (2, 11, 3) }. The first vertex would be set to the start point at (1, 1, 1) and the last vertex would be set to the diagonally opposite vertex at (2, 11, 3).
- Parameters:
steps
- steps along the canonical axes representing box edges, they may be negative but not null- Throws:
IllegalArgumentException
- if one step is null
-
setStartConfiguration
Set start configuration for simplex.The real initial simplex will be set up by moving the reference simplex such that its first point is located at the start point of the optimization.
- Parameters:
referenceSimplex
- reference simplex- Throws:
IllegalArgumentException
- if the reference simplex does not contain at least one point, or if there is a dimension mismatch in the reference simplex or if one of its vertices is duplicated
-
setMaxIterations
public void setMaxIterations(int maxIterations) Set the maximal number of iterations of the algorithm.- Specified by:
setMaxIterations
in interfaceMultivariateRealOptimizer
- Parameters:
maxIterations
- maximal number of algorithm iterations
-
getMaxIterations
public int getMaxIterations()Get the maximal number of iterations of the algorithm.- Specified by:
getMaxIterations
in interfaceMultivariateRealOptimizer
- Returns:
- maximal number of iterations
-
setMaxEvaluations
public void setMaxEvaluations(int maxEvaluations) Set the maximal number of functions evaluations.- Specified by:
setMaxEvaluations
in interfaceMultivariateRealOptimizer
- Parameters:
maxEvaluations
- maximal number of function evaluations
-
getMaxEvaluations
public int getMaxEvaluations()Get the maximal number of functions evaluations.- Specified by:
getMaxEvaluations
in interfaceMultivariateRealOptimizer
- Returns:
- maximal number of functions evaluations
-
getIterations
public int getIterations()Get the number of iterations realized by the algorithm.The number of evaluations corresponds to the last call to the
optimize
method. It is 0 if the method has not been called yet.- Specified by:
getIterations
in interfaceMultivariateRealOptimizer
- Returns:
- number of iterations
-
getEvaluations
public int getEvaluations()Get the number of evaluations of the objective function.The number of evaluations corresponds to the last call to the
optimize
method. It is 0 if the method has not been called yet.- Specified by:
getEvaluations
in interfaceMultivariateRealOptimizer
- Returns:
- number of evaluations of the objective function
-
setConvergenceChecker
Set the convergence checker.- Specified by:
setConvergenceChecker
in interfaceMultivariateRealOptimizer
- Parameters:
convergenceChecker
- object to use to check for convergence
-
getConvergenceChecker
Get the convergence checker.- Specified by:
getConvergenceChecker
in interfaceMultivariateRealOptimizer
- Returns:
- object used to check for convergence
-
optimize
public RealPointValuePair optimize(MultivariateRealFunction function, GoalType goalType, double[] startPoint) throws FunctionEvaluationException, OptimizationException, IllegalArgumentException Optimizes an objective function.- Specified by:
optimize
in interfaceMultivariateRealOptimizer
- Parameters:
function
- objective functiongoalType
- type of optimization goal: eitherGoalType.MAXIMIZE
orGoalType.MINIMIZE
startPoint
- the start point for optimization- Returns:
- the point/value pair giving the optimal value for objective function
- Throws:
FunctionEvaluationException
- if the objective function throws one during the searchOptimizationException
- if the algorithm failed to convergeIllegalArgumentException
- if the start point dimension is wrong
-
incrementIterationsCounter
Increment the iterations counter by 1.- Throws:
OptimizationException
- if the maximal number of iterations is exceeded
-
iterateSimplex
protected abstract void iterateSimplex(Comparator<RealPointValuePair> comparator) throws FunctionEvaluationException, OptimizationException, IllegalArgumentException Compute the next simplex of the algorithm.- Parameters:
comparator
- comparator to use to sort simplex vertices from best to worst- Throws:
FunctionEvaluationException
- if the function cannot be evaluated at some pointOptimizationException
- if the algorithm fails to convergeIllegalArgumentException
- if the start point dimension is wrong
-
evaluate
Evaluate the objective function on one point.A side effect of this method is to count the number of function evaluations
- Parameters:
x
- point on which the objective function should be evaluated- Returns:
- objective function value at the given point
- Throws:
FunctionEvaluationException
- if no value can be computed for the parameters or if the maximal number of evaluations is exceededIllegalArgumentException
- if the start point dimension is wrong
-
evaluateSimplex
protected void evaluateSimplex(Comparator<RealPointValuePair> comparator) throws FunctionEvaluationException, OptimizationException Evaluate all the non-evaluated points of the simplex.- Parameters:
comparator
- comparator to use to sort simplex vertices from best to worst- Throws:
FunctionEvaluationException
- if no value can be computed for the parametersOptimizationException
- if the maximal number of evaluations is exceeded
-
replaceWorstPoint
protected void replaceWorstPoint(RealPointValuePair pointValuePair, Comparator<RealPointValuePair> comparator) Replace the worst point of the simplex by a new point.- Parameters:
pointValuePair
- point to insertcomparator
- comparator to use to sort simplex vertices from best to worst
-