View Javadoc

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   */
17  
18  package org.apache.commons.math3.optimization.direct;
19  
20  import java.util.Comparator;
21  
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;
30  
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   * @version $Id: SimplexOptimizer.java 1504724 2013-07-18 23:41:20Z sebb $
85   * @deprecated As of 3.1 (to be removed in 4.0).
86   * @since 3.0
87   */
88  @SuppressWarnings("boxing") // deprecated anyway
89  @Deprecated
90  public class SimplexOptimizer
91      extends BaseAbstractMultivariateOptimizer<MultivariateFunction>
92      implements MultivariateOptimizer {
93      /** Simplex. */
94      private AbstractSimplex simplex;
95  
96      /**
97       * Constructor using a default {@link SimpleValueChecker convergence
98       * checker}.
99       * @deprecated See {@link SimpleValueChecker#SimpleValueChecker()}
100      */
101     @Deprecated
102     public SimplexOptimizer() {
103         this(new SimpleValueChecker());
104     }
105 
106     /**
107      * @param checker Convergence checker.
108      */
109     public SimplexOptimizer(ConvergenceChecker<PointValuePair> checker) {
110         super(checker);
111     }
112 
113     /**
114      * @param rel Relative threshold.
115      * @param abs Absolute threshold.
116      */
117     public SimplexOptimizer(double rel, double abs) {
118         this(new SimpleValueChecker(rel, abs));
119     }
120 
121     /**
122      * Set the simplex algorithm.
123      *
124      * @param simplex Simplex.
125      * @deprecated As of 3.1. The initial simplex can now be passed as an
126      * argument of the {@link #optimize(int,MultivariateFunction,GoalType,OptimizationData[])}
127      * method.
128      */
129     @Deprecated
130     public void setSimplex(AbstractSimplex simplex) {
131         parseOptimizationData(simplex);
132     }
133 
134     /**
135      * Optimize an objective function.
136      *
137      * @param maxEval Allowed number of evaluations of the objective function.
138      * @param f Objective function.
139      * @param goalType Optimization type.
140      * @param optData Optimization data. The following data will be looked for:
141      * <ul>
142      *  <li>{@link org.apache.commons.math3.optimization.InitialGuess InitialGuess}</li>
143      *  <li>{@link AbstractSimplex}</li>
144      * </ul>
145      * @return the point/value pair giving the optimal value for objective
146      * function.
147      */
148     @Override
149     protected PointValuePair optimizeInternal(int maxEval, MultivariateFunction f,
150                                               GoalType goalType,
151                                               OptimizationData... optData) {
152         // Scan "optData" for the input specific to this optimizer.
153         parseOptimizationData(optData);
154 
155         // The parent's method will retrieve the common parameters from
156         // "optData" and call "doOptimize".
157         return super.optimizeInternal(maxEval, f, goalType, optData);
158     }
159 
160     /**
161      * Scans the list of (required and optional) optimization data that
162      * characterize the problem.
163      *
164      * @param optData Optimization data. The following data will be looked for:
165      * <ul>
166      *  <li>{@link AbstractSimplex}</li>
167      * </ul>
168      */
169     private void parseOptimizationData(OptimizationData... optData) {
170         // The existing values (as set by the previous call) are reused if
171         // not provided in the argument list.
172         for (OptimizationData data : optData) {
173             if (data instanceof AbstractSimplex) {
174                 simplex = (AbstractSimplex) data;
175                 continue;
176             }
177         }
178     }
179 
180     /** {@inheritDoc} */
181     @Override
182     protected PointValuePair doOptimize() {
183         if (simplex == null) {
184             throw new NullArgumentException();
185         }
186 
187         // Indirect call to "computeObjectiveValue" in order to update the
188         // evaluations counter.
189         final MultivariateFunction evalFunc
190             = new MultivariateFunction() {
191                 public double value(double[] point) {
192                     return computeObjectiveValue(point);
193                 }
194             };
195 
196         final boolean isMinim = getGoalType() == GoalType.MINIMIZE;
197         final Comparator<PointValuePair> comparator
198             = new Comparator<PointValuePair>() {
199             public int compare(final PointValuePair o1,
200                                final PointValuePair o2) {
201                 final double v1 = o1.getValue();
202                 final double v2 = o2.getValue();
203                 return isMinim ? Double.compare(v1, v2) : Double.compare(v2, v1);
204             }
205         };
206 
207         // Initialize search.
208         simplex.build(getStartPoint());
209         simplex.evaluate(evalFunc, comparator);
210 
211         PointValuePair[] previous = null;
212         int iteration = 0;
213         final ConvergenceChecker<PointValuePair> checker = getConvergenceChecker();
214         while (true) {
215             if (iteration > 0) {
216                 boolean converged = true;
217                 for (int i = 0; i < simplex.getSize(); i++) {
218                     PointValuePair prev = previous[i];
219                     converged = converged &&
220                         checker.converged(iteration, prev, simplex.getPoint(i));
221                 }
222                 if (converged) {
223                     // We have found an optimum.
224                     return simplex.getPoint(0);
225                 }
226             }
227 
228             // We still need to search.
229             previous = simplex.getPoints();
230             simplex.iterate(evalFunc, comparator);
231             ++iteration;
232         }
233     }
234 }