SimplexOptimizer.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */

  18. package org.apache.commons.math3.optimization.direct;

  20. import java.util.Comparator;

  22. import org.apache.commons.math3.analysis.MultivariateFunction;
  23. import org.apache.commons.math3.exception.NullArgumentException;
  24. import org.apache.commons.math3.optimization.GoalType;
  25. import org.apache.commons.math3.optimization.ConvergenceChecker;
  26. import org.apache.commons.math3.optimization.PointValuePair;
  27. import org.apache.commons.math3.optimization.SimpleValueChecker;
  28. import org.apache.commons.math3.optimization.MultivariateOptimizer;
  29. import org.apache.commons.math3.optimization.OptimizationData;

  31. /**
  32.  * This class implements simplex-based direct search optimization.
  33.  *
  34.  * <p>
  35.  *  Direct search methods only use objective function values, they do
  36.  *  not need derivatives and don't either try to compute approximation
  37.  *  of the derivatives. According to a 1996 paper by Margaret H. Wright
  38.  *  (<a href="http://cm.bell-labs.com/cm/cs/doc/96/4-02.ps.gz">Direct
  39.  *  Search Methods: Once Scorned, Now Respectable</a>), they are used
  40.  *  when either the computation of the derivative is impossible (noisy
  41.  *  functions, unpredictable discontinuities) or difficult (complexity,
  42.  *  computation cost). In the first cases, rather than an optimum, a
  43.  *  <em>not too bad</em> point is desired. In the latter cases, an
  44.  *  optimum is desired but cannot be reasonably found. In all cases
  45.  *  direct search methods can be useful.
  46.  * </p>
  47.  * <p>
  48.  *  Simplex-based direct search methods are based on comparison of
  49.  *  the objective function values at the vertices of a simplex (which is a
  50.  *  set of n+1 points in dimension n) that is updated by the algorithms
  51.  *  steps.
  52.  * <p>
  53.  * <p>
  54.  *  The {@link #setSimplex(AbstractSimplex) setSimplex} method <em>must</em>
  55.  *  be called prior to calling the {@code optimize} method.
  56.  * </p>
  57.  * <p>
  58.  *  Each call to {@link #optimize(int,MultivariateFunction,GoalType,double[])
  59.  *  optimize} will re-use the start configuration of the current simplex and
  60.  *  move it such that its first vertex is at the provided start point of the
  61.  *  optimization. If the {@code optimize} method is called to solve a different
  62.  *  problem and the number of parameters change, the simplex must be
  63.  *  re-initialized to one with the appropriate dimensions.
  64.  * </p>
  65.  * <p>
  66.  *  Convergence is checked by providing the <em>worst</em> points of
  67.  *  previous and current simplex to the convergence checker, not the best
  68.  *  ones.
  69.  * </p>
  70.  * <p>
  71.  * This simplex optimizer implementation does not directly support constrained
  72.  * optimization with simple bounds, so for such optimizations, either a more
  73.  * dedicated method must be used like {@link CMAESOptimizer} or {@link
  74.  * BOBYQAOptimizer}, or the optimized method must be wrapped in an adapter like
  75.  * {@link MultivariateFunctionMappingAdapter} or {@link
  76.  * MultivariateFunctionPenaltyAdapter}.
  77.  * </p>
  78.  *
  79.  * @see AbstractSimplex
  80.  * @see MultivariateFunctionMappingAdapter
  81.  * @see MultivariateFunctionPenaltyAdapter
  82.  * @see CMAESOptimizer
  83.  * @see BOBYQAOptimizer
  84.  * @deprecated As of 3.1 (to be removed in 4.0).
  85.  * @since 3.0
  86.  */
  87. @SuppressWarnings("boxing") // deprecated anyway
  88. @Deprecated
  89. public class SimplexOptimizer
  90.     extends BaseAbstractMultivariateOptimizer<MultivariateFunction>
  91.     implements MultivariateOptimizer {
  92.     /** Simplex. */
  93.     private AbstractSimplex simplex;

  95.     /**
  96.      * Constructor using a default {@link SimpleValueChecker convergence
  97.      * checker}.
  98.      * @deprecated See {@link SimpleValueChecker#SimpleValueChecker()}
  99.      */
  100.     @Deprecated
  101.     public SimplexOptimizer() {
  102.         this(new SimpleValueChecker());
  103.     }

  105.     /**
  106.      * @param checker Convergence checker.
  107.      */
  108.     public SimplexOptimizer(ConvergenceChecker<PointValuePair> checker) {
  109.         super(checker);
  110.     }

  112.     /**
  113.      * @param rel Relative threshold.
  114.      * @param abs Absolute threshold.
  115.      */
  116.     public SimplexOptimizer(double rel, double abs) {
  117.         this(new SimpleValueChecker(rel, abs));
  118.     }

  120.     /**
  121.      * Set the simplex algorithm.
  122.      *
  123.      * @param simplex Simplex.
  124.      * @deprecated As of 3.1. The initial simplex can now be passed as an
  125.      * argument of the {@link #optimize(int,MultivariateFunction,GoalType,OptimizationData[])}
  126.      * method.
  127.      */
  128.     @Deprecated
  129.     public void setSimplex(AbstractSimplex simplex) {
  130.         parseOptimizationData(simplex);
  131.     }

  133.     /**
  134.      * Optimize an objective function.
  135.      *
  136.      * @param maxEval Allowed number of evaluations of the objective function.
  137.      * @param f Objective function.
  138.      * @param goalType Optimization type.
  139.      * @param optData Optimization data. The following data will be looked for:
  140.      * <ul>
  141.      *  <li>{@link org.apache.commons.math3.optimization.InitialGuess InitialGuess}</li>
  142.      *  <li>{@link AbstractSimplex}</li>
  143.      * </ul>
  144.      * @return the point/value pair giving the optimal value for objective
  145.      * function.
  146.      */
  147.     @Override
  148.     protected PointValuePair optimizeInternal(int maxEval, MultivariateFunction f,
  149.                                               GoalType goalType,
  150.                                               OptimizationData... optData) {
  151.         // Scan "optData" for the input specific to this optimizer.
  152.         parseOptimizationData(optData);

  154.         // The parent's method will retrieve the common parameters from
  155.         // "optData" and call "doOptimize".
  156.         return super.optimizeInternal(maxEval, f, goalType, optData);
  157.     }

  159.     /**
  160.      * Scans the list of (required and optional) optimization data that
  161.      * characterize the problem.
  162.      *
  163.      * @param optData Optimization data. The following data will be looked for:
  164.      * <ul>
  165.      *  <li>{@link AbstractSimplex}</li>
  166.      * </ul>
  167.      */
  168.     private void parseOptimizationData(OptimizationData... optData) {
  169.         // The existing values (as set by the previous call) are reused if
  170.         // not provided in the argument list.
  171.         for (OptimizationData data : optData) {
  172.             if (data instanceof AbstractSimplex) {
  173.                 simplex = (AbstractSimplex) data;
  174.                 continue;
  175.             }
  176.         }
  177.     }

  179.     /** {@inheritDoc} */
  180.     @Override
  181.     protected PointValuePair doOptimize() {
  182.         if (simplex == null) {
  183.             throw new NullArgumentException();
  184.         }

  186.         // Indirect call to "computeObjectiveValue" in order to update the
  187.         // evaluations counter.
  188.         final MultivariateFunction evalFunc
  189.             = new MultivariateFunction() {
  190.                 public double value(double[] point) {
  191.                     return computeObjectiveValue(point);
  192.                 }
  193.             };

  195.         final boolean isMinim = getGoalType() == GoalType.MINIMIZE;
  196.         final Comparator<PointValuePair> comparator
  197.             = new Comparator<PointValuePair>() {
  198.             public int compare(final PointValuePair o1,
  199.                                final PointValuePair o2) {
  200.                 final double v1 = o1.getValue();
  201.                 final double v2 = o2.getValue();
  202.                 return isMinim ? Double.compare(v1, v2) : Double.compare(v2, v1);
  203.             }
  204.         };

  206.         // Initialize search.
  207.         simplex.build(getStartPoint());
  208.         simplex.evaluate(evalFunc, comparator);

  210.         PointValuePair[] previous = null;
  211.         int iteration = 0;
  212.         final ConvergenceChecker<PointValuePair> checker = getConvergenceChecker();
  213.         while (true) {
  214.             if (iteration > 0) {
  215.                 boolean converged = true;
  216.                 for (int i = 0; i < simplex.getSize(); i++) {
  217.                     PointValuePair prev = previous[i];
  218.                     converged = converged &&
  219.                         checker.converged(iteration, prev, simplex.getPoint(i));
  220.                 }
  221.                 if (converged) {
  222.                     // We have found an optimum.
  223.                     return simplex.getPoint(0);
  224.                 }
  225.             }

  227.             // We still need to search.
  228.             previous = simplex.getPoints();
  229.             simplex.iterate(evalFunc, comparator);
  230.             ++iteration;
  231.         }
  232.     }
  233. }
Created with JaCoCo 0.7.2.201409121644