org.apache.commons.math.optimization.direct

## Class DirectSearchOptimizer

- java.lang.Object
- - org.apache.commons.math.optimization.direct.DirectSearchOptimizer

- All Implemented Interfaces:
    MultivariateRealOptimizer
  Direct Known Subclasses:
    MultiDirectional, NelderMead

      public abstract class DirectSearchOptimizer
      extends java.lang.Object
      implements MultivariateRealOptimizer

  This class implements simplex-based direct search optimization algorithms.

  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:
    `MultivariateRealFunction`, `NelderMead`, `MultiDirectional`

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `private RealConvergenceChecker` | `checker` Convergence checker.
    `private int` | `evaluations` Number of evaluations already performed.
    `private MultivariateRealFunction` | `f` Objective function.
    `private int` | `iterations` Number of iterations already performed.
    `private int` | `maxEvaluations` Maximal number of evaluations allowed.
    `private int` | `maxIterations` Maximal number of iterations allowed.
    `protected RealPointValuePair[]` | `simplex` Simplex.
    `private double[][]` | `startConfiguration` Start simplex configuration.

  - ### Constructor Summary

    Constructors
    Modifier | Constructor and Description
    --- | ---
    `protected` | `DirectSearchOptimizer()` Simple constructor.

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `private void` | `buildSimplex(double[] startPoint)` Build an initial simplex.
    `protected double` | `evaluate(double[] x)` Evaluate the objective function on one point.
    `protected void` | `evaluateSimplex(java.util.Comparator<RealPointValuePair> comparator)` Evaluate all the non-evaluated points of the simplex.
    `RealConvergenceChecker` | `getConvergenceChecker()` Get the convergence checker.
    `int` | `getEvaluations()` Get the number of evaluations of the objective function.
    `int` | `getIterations()` Get the number of iterations realized by the algorithm.
    `int` | `getMaxEvaluations()` Get the maximal number of functions evaluations.
    `int` | `getMaxIterations()` Get the maximal number of iterations of the algorithm.
    `protected void` | `incrementIterationsCounter()` Increment the iterations counter by 1.
    `protected abstract void` | `iterateSimplex(java.util.Comparator<RealPointValuePair> comparator)` Compute the next simplex of the algorithm.
    `RealPointValuePair` | `optimize(MultivariateRealFunction function, GoalType goalType, double[] startPoint)` Optimizes an objective function.
    `protected void` | `replaceWorstPoint(RealPointValuePair pointValuePair, java.util.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.

    - ### Methods inherited from class java.lang.Object

      `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- - ### Field Detail

    - #### simplex

          protected RealPointValuePair[] simplex

      Simplex.

    - #### f

          private MultivariateRealFunction f

      Objective function.

    - #### checker

          private RealConvergenceChecker checker

      Convergence checker.

    - #### maxIterations

          private int maxIterations

      Maximal number of iterations allowed.

    - #### iterations

          private int iterations

      Number of iterations already performed.

    - #### maxEvaluations

          private int maxEvaluations

      Maximal number of evaluations allowed.

    - #### evaluations

          private int evaluations

      Number of evaluations already performed.

    - #### startConfiguration

          private double[][] startConfiguration

      Start simplex configuration.

  - ### Constructor Detail

    - #### DirectSearchOptimizer

          protected DirectSearchOptimizer()

      Simple constructor.

  - ### Method Detail

    - #### setStartConfiguration

          public void setStartConfiguration(double[] steps)
                                     throws java.lang.IllegalArgumentException

      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:
        `java.lang.IllegalArgumentException` - if one step is null

    - #### setStartConfiguration

          public void setStartConfiguration(double[][] referenceSimplex)
                                     throws java.lang.IllegalArgumentException

      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:
        `java.lang.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 interface `MultivariateRealOptimizer`
      Parameters:
        `maxIterations` - maximal number of algorithm iterations

    - #### getMaxIterations

          public int getMaxIterations()

      Get the maximal number of iterations of the algorithm.
      Specified by:
        `getMaxIterations` in interface `MultivariateRealOptimizer`
      Returns:
        maximal number of iterations

    - #### setMaxEvaluations

          public void setMaxEvaluations(int maxEvaluations)

      Set the maximal number of functions evaluations.
      Specified by:
        `setMaxEvaluations` in interface `MultivariateRealOptimizer`
      Parameters:
        `maxEvaluations` - maximal number of function evaluations

    - #### getMaxEvaluations

          public int getMaxEvaluations()

      Get the maximal number of functions evaluations.
      Specified by:
        `getMaxEvaluations` in interface `MultivariateRealOptimizer`
      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 interface `MultivariateRealOptimizer`
      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 interface `MultivariateRealOptimizer`
      Returns:
        number of evaluations of the objective function

    - #### setConvergenceChecker

          public void setConvergenceChecker(RealConvergenceChecker convergenceChecker)

      Set the convergence checker.
      Specified by:
        `setConvergenceChecker` in interface `MultivariateRealOptimizer`
      Parameters:
        `convergenceChecker` - object to use to check for convergence

    - #### getConvergenceChecker

          public RealConvergenceChecker getConvergenceChecker()

      Get the convergence checker.
      Specified by:
        `getConvergenceChecker` in interface `MultivariateRealOptimizer`
      Returns:
        object used to check for convergence

    - #### optimize

          public RealPointValuePair optimize(MultivariateRealFunction function,
                                    GoalType goalType,
                                    double[] startPoint)
                                      throws FunctionEvaluationException,
                                             OptimizationException,
                                             java.lang.IllegalArgumentException

      Optimizes an objective function.
      Specified by:
        `optimize` in interface `MultivariateRealOptimizer`
      Parameters:
        `function` - objective function
        `goalType` - type of optimization goal: either `GoalType.MAXIMIZE` or `GoalType.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 search
        `OptimizationException` - if the algorithm failed to converge
        `java.lang.IllegalArgumentException` - if the start point dimension is wrong

    - #### incrementIterationsCounter

          protected void incrementIterationsCounter()
                                             throws OptimizationException

      Increment the iterations counter by 1.
      Throws:
        `OptimizationException` - if the maximal number of iterations is exceeded

    - #### iterateSimplex

          protected abstract void iterateSimplex(java.util.Comparator<RealPointValuePair> comparator)
                                          throws FunctionEvaluationException,
                                                 OptimizationException,
                                                 java.lang.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 point
        `OptimizationException` - if the algorithm fails to converge
        `java.lang.IllegalArgumentException` - if the start point dimension is wrong

    - #### evaluate

          protected double evaluate(double[] x)
                             throws FunctionEvaluationException,
                                    java.lang.IllegalArgumentException

      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 exceeded
        `java.lang.IllegalArgumentException` - if the start point dimension is wrong

    - #### buildSimplex

          private void buildSimplex(double[] startPoint)
                             throws java.lang.IllegalArgumentException

      Build an initial simplex.
      Parameters:
        `startPoint` - the start point for optimization
      Throws:
        `java.lang.IllegalArgumentException` - if the start point does not match simplex dimension

    - #### evaluateSimplex

          protected void evaluateSimplex(java.util.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 parameters
        `OptimizationException` - if the maximal number of evaluations is exceeded

    - #### replaceWorstPoint

          protected void replaceWorstPoint(RealPointValuePair pointValuePair,
                               java.util.Comparator<RealPointValuePair> comparator)

      Replace the worst point of the simplex by a new point.
      Parameters:
        `pointValuePair` - point to insert
        `comparator` - comparator to use to sort simplex vertices from best to worst

Copyright (c) 2003-2013 Apache Software Foundation