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   * @version $Id: SimplexOptimizer.java 1458323 2013-03-19 14:51:30Z erans $
87   * @since 3.0
88   */
89  public class SimplexOptimizer extends MultivariateOptimizer {
90      /** Simplex update rule. */
91      private AbstractSimplex simplex;
92  
93      /**
94       * @param checker Convergence checker.
95       */
96      public SimplexOptimizer(ConvergenceChecker<PointValuePair> checker) {
97          super(checker);
98      }
99  
100     /**
101      * @param rel Relative threshold.
102      * @param abs Absolute threshold.
103      */
104     public SimplexOptimizer(double rel, double abs) {
105         this(new SimpleValueChecker(rel, abs));
106     }
107 
108     /**
109      * {@inheritDoc}
110      *
111      * @param optData Optimization data. In addition to those documented in
112      * {@link MultivariateOptimizer#parseOptimizationData(OptimizationData[])
113      * MultivariateOptimizer}, this method will register the following data:
114      * <ul>
115      *  <li>{@link AbstractSimplex}</li>
116      * </ul>
117      * @return {@inheritDoc}
118      */
119     @Override
120     public PointValuePair optimize(OptimizationData... optData) {
121         // Set up base class and perform computation.
122         return super.optimize(optData);
123     }
124 
125     /** {@inheritDoc} */
126     @Override
127     protected PointValuePair doOptimize() {
128         checkParameters();
129 
130         // Indirect call to "computeObjectiveValue" in order to update the
131         // evaluations counter.
132         final MultivariateFunction evalFunc
133             = new MultivariateFunction() {
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             public int compare(final PointValuePair o1,
143                                final PointValuePair o2) {
144                 final double v1 = o1.getValue();
145                 final double v2 = o2.getValue();
146                 return isMinim ? Double.compare(v1, v2) : Double.compare(v2, v1);
147             }
148         };
149 
150         // Initialize search.
151         simplex.build(getStartPoint());
152         simplex.evaluate(evalFunc, comparator);
153 
154         PointValuePair[] previous = null;
155         int iteration = 0;
156         final ConvergenceChecker<PointValuePair> checker = getConvergenceChecker();
157         while (true) {
158             if (getIterations() > 0) {
159                 boolean converged = true;
160                 for (int i = 0; i < simplex.getSize(); i++) {
161                     PointValuePair prev = previous[i];
162                     converged = converged &&
163                         checker.converged(iteration, prev, simplex.getPoint(i));
164                 }
165                 if (converged) {
166                     // We have found an optimum.
167                     return simplex.getPoint(0);
168                 }
169             }
170 
171             // We still need to search.
172             previous = simplex.getPoints();
173             simplex.iterate(evalFunc, comparator);
174 
175             incrementIterationCount();
176         }
177     }
178 
179     /**
180      * Scans the list of (required and optional) optimization data that
181      * characterize the problem.
182      *
183      * @param optData Optimization data.
184      * The following data will be looked for:
185      * <ul>
186      *  <li>{@link AbstractSimplex}</li>
187      * </ul>
188      */
189     @Override
190     protected void parseOptimizationData(OptimizationData... optData) {
191         // Allow base class to register its own data.
192         super.parseOptimizationData(optData);
193 
194         // The existing values (as set by the previous call) are reused if
195         // not provided in the argument list.
196         for (OptimizationData data : optData) {
197             if (data instanceof AbstractSimplex) {
198                 simplex = (AbstractSimplex) data;
199                 // If more data must be parsed, this statement _must_ be
200                 // changed to "continue".
201                 break;
202             }
203         }
204     }
205 
206     /**
207      * @throws MathUnsupportedOperationException if bounds were passed to the
208      * {@link #optimize(OptimizationData[]) optimize} method.
209      * @throws NullArgumentException if no initial simplex was passed to the
210      * {@link #optimize(OptimizationData[]) optimize} method.
211      */
212     private void checkParameters() {
213         if (simplex == null) {
214             throw new NullArgumentException();
215         }
216         if (getLowerBound() != null ||
217             getUpperBound() != null) {
218             throw new MathUnsupportedOperationException(LocalizedFormats.CONSTRAINT);
219         }
220     }
221 }