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.optimization.PointValuePair;
23  import org.apache.commons.math3.analysis.MultivariateFunction;
24  
25  /**
26   * This class implements the Nelder-Mead simplex algorithm.
27   *
28   * @deprecated As of 3.1 (to be removed in 4.0).
29   * @since 3.0
30   */
31  @Deprecated
32  public class NelderMeadSimplex extends AbstractSimplex {
33      /** Default value for {@link #rho}: {@value}. */
34      private static final double DEFAULT_RHO = 1;
35      /** Default value for {@link #khi}: {@value}. */
36      private static final double DEFAULT_KHI = 2;
37      /** Default value for {@link #gamma}: {@value}. */
38      private static final double DEFAULT_GAMMA = 0.5;
39      /** Default value for {@link #sigma}: {@value}. */
40      private static final double DEFAULT_SIGMA = 0.5;
41      /** Reflection coefficient. */
42      private final double rho;
43      /** Expansion coefficient. */
44      private final double khi;
45      /** Contraction coefficient. */
46      private final double gamma;
47      /** Shrinkage coefficient. */
48      private final double sigma;
49  
50      /**
51       * Build a Nelder-Mead simplex with default coefficients.
52       * The default coefficients are 1.0 for rho, 2.0 for khi and 0.5
53       * for both gamma and sigma.
54       *
55       * @param n Dimension of the simplex.
56       */
57      public NelderMeadSimplex(final int n) {
58          this(n, 1d);
59      }
60  
61      /**
62       * Build a Nelder-Mead simplex with default coefficients.
63       * The default coefficients are 1.0 for rho, 2.0 for khi and 0.5
64       * for both gamma and sigma.
65       *
66       * @param n Dimension of the simplex.
67       * @param sideLength Length of the sides of the default (hypercube)
68       * simplex. See {@link AbstractSimplex#AbstractSimplex(int,double)}.
69       */
70      public NelderMeadSimplex(final int n, double sideLength) {
71          this(n, sideLength,
72               DEFAULT_RHO, DEFAULT_KHI, DEFAULT_GAMMA, DEFAULT_SIGMA);
73      }
74  
75      /**
76       * Build a Nelder-Mead simplex with specified coefficients.
77       *
78       * @param n Dimension of the simplex. See
79       * {@link AbstractSimplex#AbstractSimplex(int,double)}.
80       * @param sideLength Length of the sides of the default (hypercube)
81       * simplex. See {@link AbstractSimplex#AbstractSimplex(int,double)}.
82       * @param rho Reflection coefficient.
83       * @param khi Expansion coefficient.
84       * @param gamma Contraction coefficient.
85       * @param sigma Shrinkage coefficient.
86       */
87      public NelderMeadSimplex(final int n, double sideLength,
88                               final double rho, final double khi,
89                               final double gamma, final double sigma) {
90          super(n, sideLength);
91  
92          this.rho = rho;
93          this.khi = khi;
94          this.gamma = gamma;
95          this.sigma = sigma;
96      }
97  
98      /**
99       * Build a Nelder-Mead simplex with specified coefficients.
100      *
101      * @param n Dimension of the simplex. See
102      * {@link AbstractSimplex#AbstractSimplex(int)}.
103      * @param rho Reflection coefficient.
104      * @param khi Expansion coefficient.
105      * @param gamma Contraction coefficient.
106      * @param sigma Shrinkage coefficient.
107      */
108     public NelderMeadSimplex(final int n,
109                              final double rho, final double khi,
110                              final double gamma, final double sigma) {
111         this(n, 1d, rho, khi, gamma, sigma);
112     }
113 
114     /**
115      * Build a Nelder-Mead simplex with default coefficients.
116      * The default coefficients are 1.0 for rho, 2.0 for khi and 0.5
117      * for both gamma and sigma.
118      *
119      * @param steps Steps along the canonical axes representing box edges.
120      * They may be negative but not zero. See
121      */
122     public NelderMeadSimplex(final double[] steps) {
123         this(steps, DEFAULT_RHO, DEFAULT_KHI, DEFAULT_GAMMA, DEFAULT_SIGMA);
124     }
125 
126     /**
127      * Build a Nelder-Mead simplex with specified coefficients.
128      *
129      * @param steps Steps along the canonical axes representing box edges.
130      * They may be negative but not zero. See
131      * {@link AbstractSimplex#AbstractSimplex(double[])}.
132      * @param rho Reflection coefficient.
133      * @param khi Expansion coefficient.
134      * @param gamma Contraction coefficient.
135      * @param sigma Shrinkage coefficient.
136      * @throws IllegalArgumentException if one of the steps is zero.
137      */
138     public NelderMeadSimplex(final double[] steps,
139                              final double rho, final double khi,
140                              final double gamma, final double sigma) {
141         super(steps);
142 
143         this.rho = rho;
144         this.khi = khi;
145         this.gamma = gamma;
146         this.sigma = sigma;
147     }
148 
149     /**
150      * Build a Nelder-Mead simplex with default coefficients.
151      * The default coefficients are 1.0 for rho, 2.0 for khi and 0.5
152      * for both gamma and sigma.
153      *
154      * @param referenceSimplex Reference simplex. See
155      * {@link AbstractSimplex#AbstractSimplex(double[][])}.
156      */
157     public NelderMeadSimplex(final double[][] referenceSimplex) {
158         this(referenceSimplex, DEFAULT_RHO, DEFAULT_KHI, DEFAULT_GAMMA, DEFAULT_SIGMA);
159     }
160 
161     /**
162      * Build a Nelder-Mead simplex with specified coefficients.
163      *
164      * @param referenceSimplex Reference simplex. See
165      * {@link AbstractSimplex#AbstractSimplex(double[][])}.
166      * @param rho Reflection coefficient.
167      * @param khi Expansion coefficient.
168      * @param gamma Contraction coefficient.
169      * @param sigma Shrinkage coefficient.
170      * @throws org.apache.commons.math3.exception.NotStrictlyPositiveException
171      * if the reference simplex does not contain at least one point.
172      * @throws org.apache.commons.math3.exception.DimensionMismatchException
173      * if there is a dimension mismatch in the reference simplex.
174      */
175     public NelderMeadSimplex(final double[][] referenceSimplex,
176                              final double rho, final double khi,
177                              final double gamma, final double sigma) {
178         super(referenceSimplex);
179 
180         this.rho = rho;
181         this.khi = khi;
182         this.gamma = gamma;
183         this.sigma = sigma;
184     }
185 
186     /** {@inheritDoc} */
187     @Override
188     public void iterate(final MultivariateFunction evaluationFunction,
189                         final Comparator<PointValuePair> comparator) {
190         // The simplex has n + 1 points if dimension is n.
191         final int n = getDimension();
192 
193         // Interesting values.
194         final PointValuePair best = getPoint(0);
195         final PointValuePair secondBest = getPoint(n - 1);
196         final PointValuePair worst = getPoint(n);
197         final double[] xWorst = worst.getPointRef();
198 
199         // Compute the centroid of the best vertices (dismissing the worst
200         // point at index n).
201         final double[] centroid = new double[n];
202         for (int i = 0; i < n; i++) {
203             final double[] x = getPoint(i).getPointRef();
204             for (int j = 0; j < n; j++) {
205                 centroid[j] += x[j];
206             }
207         }
208         final double scaling = 1.0 / n;
209         for (int j = 0; j < n; j++) {
210             centroid[j] *= scaling;
211         }
212 
213         // compute the reflection point
214         final double[] xR = new double[n];
215         for (int j = 0; j < n; j++) {
216             xR[j] = centroid[j] + rho * (centroid[j] - xWorst[j]);
217         }
218         final PointValuePair reflected
219             = new PointValuePair(xR, evaluationFunction.value(xR), false);
220 
221         if (comparator.compare(best, reflected) <= 0 &&
222             comparator.compare(reflected, secondBest) < 0) {
223             // Accept the reflected point.
224             replaceWorstPoint(reflected, comparator);
225         } else if (comparator.compare(reflected, best) < 0) {
226             // Compute the expansion point.
227             final double[] xE = new double[n];
228             for (int j = 0; j < n; j++) {
229                 xE[j] = centroid[j] + khi * (xR[j] - centroid[j]);
230             }
231             final PointValuePair expanded
232                 = new PointValuePair(xE, evaluationFunction.value(xE), false);
233 
234             if (comparator.compare(expanded, reflected) < 0) {
235                 // Accept the expansion point.
236                 replaceWorstPoint(expanded, comparator);
237             } else {
238                 // Accept the reflected point.
239                 replaceWorstPoint(reflected, comparator);
240             }
241         } else {
242             if (comparator.compare(reflected, worst) < 0) {
243                 // Perform an outside contraction.
244                 final double[] xC = new double[n];
245                 for (int j = 0; j < n; j++) {
246                     xC[j] = centroid[j] + gamma * (xR[j] - centroid[j]);
247                 }
248                 final PointValuePair outContracted
249                     = new PointValuePair(xC, evaluationFunction.value(xC), false);
250                 if (comparator.compare(outContracted, reflected) <= 0) {
251                     // Accept the contraction point.
252                     replaceWorstPoint(outContracted, comparator);
253                     return;
254                 }
255             } else {
256                 // Perform an inside contraction.
257                 final double[] xC = new double[n];
258                 for (int j = 0; j < n; j++) {
259                     xC[j] = centroid[j] - gamma * (centroid[j] - xWorst[j]);
260                 }
261                 final PointValuePair inContracted
262                     = new PointValuePair(xC, evaluationFunction.value(xC), false);
263 
264                 if (comparator.compare(inContracted, worst) < 0) {
265                     // Accept the contraction point.
266                     replaceWorstPoint(inContracted, comparator);
267                     return;
268                 }
269             }
270 
271             // Perform a shrink.
272             final double[] xSmallest = getPoint(0).getPointRef();
273             for (int i = 1; i <= n; i++) {
274                 final double[] x = getPoint(i).getPoint();
275                 for (int j = 0; j < n; j++) {
276                     x[j] = xSmallest[j] + sigma * (x[j] - xSmallest[j]);
277                 }
278                 setPoint(i, new PointValuePair(x, Double.NaN, false));
279             }
280             evaluate(evaluationFunction, comparator);
281         }
282     }
283 }