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  package org.apache.commons.math3.optim.nonlinear.scalar.noderiv;
18  
19  import java.util.Comparator;
20  import org.apache.commons.math3.analysis.MultivariateFunction;
21  import org.apache.commons.math3.exception.NullArgumentException;
22  import org.apache.commons.math3.exception.MathUnsupportedOperationException;
23  import org.apache.commons.math3.exception.util.LocalizedFormats;
24  import org.apache.commons.math3.optim.nonlinear.scalar.GoalType;
25  import org.apache.commons.math3.optim.ConvergenceChecker;
26  import org.apache.commons.math3.optim.PointValuePair;
27  import org.apache.commons.math3.optim.SimpleValueChecker;
28  import org.apache.commons.math3.optim.OptimizationData;
29  import org.apache.commons.math3.optim.nonlinear.scalar.MultivariateOptimizer;
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 simplex update procedure ({@link NelderMeadSimplex} or
55   * {@link MultiDirectionalSimplex})  must be passed to the
56   * {@code optimize} method.
57   * </p>
58   * <p>
59   *  Each call to {@code optimize} will re-use the start configuration of
60   *  the current simplex and move it such that its first vertex is at the
61   *  provided start point of the optimization.
62   *  If the {@code optimize} method is called to solve a different problem
63   *  and the number of parameters change, the simplex must be re-initialized
64   *  to one with the appropriate dimensions.
65   * </p>
66   * <p>
67   *  Convergence is checked by providing the <em>worst</em> points of
68   *  previous and current simplex to the convergence checker, not the best
69   *  ones.
70   * </p>
71   * <p>
72   *  This simplex optimizer implementation does not directly support constrained
73   *  optimization with simple bounds; so, for such optimizations, either a more
74   *  dedicated algorithm must be used like
75   *  {@link CMAESOptimizer} or {@link BOBYQAOptimizer}, or the objective
76   *  function must be wrapped in an adapter like
77   *  {@link org.apache.commons.math3.optim.nonlinear.scalar.MultivariateFunctionMappingAdapter
78   *  MultivariateFunctionMappingAdapter} or
79   *  {@link org.apache.commons.math3.optim.nonlinear.scalar.MultivariateFunctionPenaltyAdapter
80   *  MultivariateFunctionPenaltyAdapter}.
81   *  <br/>
82   *  The call to {@link #optimize(OptimizationData[]) optimize} will throw
83   *  {@link MathUnsupportedOperationException} if bounds are passed to it.
84   * </p>
85   *
86   * @since 3.0
87   */
88  public class SimplexOptimizer extends MultivariateOptimizer {
89      /** Simplex update rule. */
90      private AbstractSimplex simplex;
91  
92      /**
93       * @param checker Convergence checker.
94       */
95      public SimplexOptimizer(ConvergenceChecker<PointValuePair> checker) {
96          super(checker);
97      }
98  
99      /**
100      * @param rel Relative threshold.
101      * @param abs Absolute threshold.
102      */
103     public SimplexOptimizer(double rel, double abs) {
104         this(new SimpleValueChecker(rel, abs));
105     }
106 
107     /**
108      * {@inheritDoc}
109      *
110      * @param optData Optimization data. In addition to those documented in
111      * {@link MultivariateOptimizer#parseOptimizationData(OptimizationData[])
112      * MultivariateOptimizer}, this method will register the following data:
113      * <ul>
114      *  <li>{@link AbstractSimplex}</li>
115      * </ul>
116      * @return {@inheritDoc}
117      */
118     @Override
119     public PointValuePair optimize(OptimizationData... optData) {
120         // Set up base class and perform computation.
121         return super.optimize(optData);
122     }
123 
124     /** {@inheritDoc} */
125     @Override
126     protected PointValuePair doOptimize() {
127         checkParameters();
128 
129         // Indirect call to "computeObjectiveValue" in order to update the
130         // evaluations counter.
131         final MultivariateFunction evalFunc
132             = new MultivariateFunction() {
133                 /** {@inheritDoc} */
134                 public double value(double[] point) {
135                     return computeObjectiveValue(point);
136                 }
137             };
138 
139         final boolean isMinim = getGoalType() == GoalType.MINIMIZE;
140         final Comparator<PointValuePair> comparator
141             = new Comparator<PointValuePair>() {
142             /** {@inheritDoc} */
143             public int compare(final PointValuePair o1,
144                                final PointValuePair o2) {
145                 final double v1 = o1.getValue();
146                 final double v2 = o2.getValue();
147                 return isMinim ? Double.compare(v1, v2) : Double.compare(v2, v1);
148             }
149         };
150 
151         // Initialize search.
152         simplex.build(getStartPoint());
153         simplex.evaluate(evalFunc, comparator);
154 
155         PointValuePair[] previous = null;
156         int iteration = 0;
157         final ConvergenceChecker<PointValuePair> checker = getConvergenceChecker();
158         while (true) {
159             if (getIterations() > 0) {
160                 boolean converged = true;
161                 for (int i = 0; i < simplex.getSize(); i++) {
162                     PointValuePair prev = previous[i];
163                     converged = converged &&
164                         checker.converged(iteration, prev, simplex.getPoint(i));
165                 }
166                 if (converged) {
167                     // We have found an optimum.
168                     return simplex.getPoint(0);
169                 }
170             }
171 
172             // We still need to search.
173             previous = simplex.getPoints();
174             simplex.iterate(evalFunc, comparator);
175 
176             incrementIterationCount();
177         }
178     }
179 
180     /**
181      * Scans the list of (required and optional) optimization data that
182      * characterize the problem.
183      *
184      * @param optData Optimization data.
185      * The following data will be looked for:
186      * <ul>
187      *  <li>{@link AbstractSimplex}</li>
188      * </ul>
189      */
190     @Override
191     protected void parseOptimizationData(OptimizationData... optData) {
192         // Allow base class to register its own data.
193         super.parseOptimizationData(optData);
194 
195         // The existing values (as set by the previous call) are reused if
196         // not provided in the argument list.
197         for (OptimizationData data : optData) {
198             if (data instanceof AbstractSimplex) {
199                 simplex = (AbstractSimplex) data;
200                 // If more data must be parsed, this statement _must_ be
201                 // changed to "continue".
202                 break;
203             }
204         }
205     }
206 
207     /**
208      * @throws MathUnsupportedOperationException if bounds were passed to the
209      * {@link #optimize(OptimizationData[]) optimize} method.
210      * @throws NullArgumentException if no initial simplex was passed to the
211      * {@link #optimize(OptimizationData[]) optimize} method.
212      */
213     private void checkParameters() {
214         if (simplex == null) {
215             throw new NullArgumentException();
216         }
217         if (getLowerBound() != null ||
218             getUpperBound() != null) {
219             throw new MathUnsupportedOperationException(LocalizedFormats.CONSTRAINT);
220         }
221     }
222 }