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  
21  import org.apache.commons.math3.analysis.MultivariateFunction;
22  import org.apache.commons.math3.optim.PointValuePair;
23  
24  /**
25   * This class implements the multi-directional direct search method.
26   *
27   * @since 3.0
28   */
29  public class MultiDirectionalSimplex extends AbstractSimplex {
30      /** Default value for {@link #khi}: {@value}. */
31      private static final double DEFAULT_KHI = 2;
32      /** Default value for {@link #gamma}: {@value}. */
33      private static final double DEFAULT_GAMMA = 0.5;
34      /** Expansion coefficient. */
35      private final double khi;
36      /** Contraction coefficient. */
37      private final double gamma;
38  
39      /**
40       * Build a multi-directional simplex with default coefficients.
41       * The default values are 2.0 for khi and 0.5 for gamma.
42       *
43       * @param n Dimension of the simplex.
44       */
45      public MultiDirectionalSimplex(final int n) {
46          this(n, 1d);
47      }
48  
49      /**
50       * Build a multi-directional simplex with default coefficients.
51       * The default values are 2.0 for khi and 0.5 for gamma.
52       *
53       * @param n Dimension of the simplex.
54       * @param sideLength Length of the sides of the default (hypercube)
55       * simplex. See {@link AbstractSimplex#AbstractSimplex(int,double)}.
56       */
57      public MultiDirectionalSimplex(final int n, double sideLength) {
58          this(n, sideLength, DEFAULT_KHI, DEFAULT_GAMMA);
59      }
60  
61      /**
62       * Build a multi-directional simplex with specified coefficients.
63       *
64       * @param n Dimension of the simplex. See
65       * {@link AbstractSimplex#AbstractSimplex(int,double)}.
66       * @param khi Expansion coefficient.
67       * @param gamma Contraction coefficient.
68       */
69      public MultiDirectionalSimplex(final int n,
70                                     final double khi, final double gamma) {
71          this(n, 1d, khi, gamma);
72      }
73  
74      /**
75       * Build a multi-directional simplex with specified coefficients.
76       *
77       * @param n Dimension of the simplex. See
78       * {@link AbstractSimplex#AbstractSimplex(int,double)}.
79       * @param sideLength Length of the sides of the default (hypercube)
80       * simplex. See {@link AbstractSimplex#AbstractSimplex(int,double)}.
81       * @param khi Expansion coefficient.
82       * @param gamma Contraction coefficient.
83       */
84      public MultiDirectionalSimplex(final int n, double sideLength,
85                                     final double khi, final double gamma) {
86          super(n, sideLength);
87  
88          this.khi   = khi;
89          this.gamma = gamma;
90      }
91  
92      /**
93       * Build a multi-directional simplex with default coefficients.
94       * The default values are 2.0 for khi and 0.5 for gamma.
95       *
96       * @param steps Steps along the canonical axes representing box edges.
97       * They may be negative but not zero. See
98       */
99      public MultiDirectionalSimplex(final double[] steps) {
100         this(steps, DEFAULT_KHI, DEFAULT_GAMMA);
101     }
102 
103     /**
104      * Build a multi-directional simplex with specified coefficients.
105      *
106      * @param steps Steps along the canonical axes representing box edges.
107      * They may be negative but not zero. See
108      * {@link AbstractSimplex#AbstractSimplex(double[])}.
109      * @param khi Expansion coefficient.
110      * @param gamma Contraction coefficient.
111      */
112     public MultiDirectionalSimplex(final double[] steps,
113                                    final double khi, final double gamma) {
114         super(steps);
115 
116         this.khi   = khi;
117         this.gamma = gamma;
118     }
119 
120     /**
121      * Build a multi-directional simplex with default coefficients.
122      * The default values are 2.0 for khi and 0.5 for gamma.
123      *
124      * @param referenceSimplex Reference simplex. See
125      * {@link AbstractSimplex#AbstractSimplex(double[][])}.
126      */
127     public MultiDirectionalSimplex(final double[][] referenceSimplex) {
128         this(referenceSimplex, DEFAULT_KHI, DEFAULT_GAMMA);
129     }
130 
131     /**
132      * Build a multi-directional simplex with specified coefficients.
133      *
134      * @param referenceSimplex Reference simplex. See
135      * {@link AbstractSimplex#AbstractSimplex(double[][])}.
136      * @param khi Expansion coefficient.
137      * @param gamma Contraction coefficient.
138      * @throws org.apache.commons.math3.exception.NotStrictlyPositiveException
139      * if the reference simplex does not contain at least one point.
140      * @throws org.apache.commons.math3.exception.DimensionMismatchException
141      * if there is a dimension mismatch in the reference simplex.
142      */
143     public MultiDirectionalSimplex(final double[][] referenceSimplex,
144                                    final double khi, final double gamma) {
145         super(referenceSimplex);
146 
147         this.khi   = khi;
148         this.gamma = gamma;
149     }
150 
151     /** {@inheritDoc} */
152     @Override
153     public void iterate(final MultivariateFunction evaluationFunction,
154                         final Comparator<PointValuePair> comparator) {
155         // Save the original simplex.
156         final PointValuePair[] original = getPoints();
157         final PointValuePair best = original[0];
158 
159         // Perform a reflection step.
160         final PointValuePair reflected = evaluateNewSimplex(evaluationFunction,
161                                                                 original, 1, comparator);
162         if (comparator.compare(reflected, best) < 0) {
163             // Compute the expanded simplex.
164             final PointValuePair[] reflectedSimplex = getPoints();
165             final PointValuePair expanded = evaluateNewSimplex(evaluationFunction,
166                                                                    original, khi, comparator);
167             if (comparator.compare(reflected, expanded) <= 0) {
168                 // Keep the reflected simplex.
169                 setPoints(reflectedSimplex);
170             }
171             // Keep the expanded simplex.
172             return;
173         }
174 
175         // Compute the contracted simplex.
176         evaluateNewSimplex(evaluationFunction, original, gamma, comparator);
177 
178     }
179 
180     /**
181      * Compute and evaluate a new simplex.
182      *
183      * @param evaluationFunction Evaluation function.
184      * @param original Original simplex (to be preserved).
185      * @param coeff Linear coefficient.
186      * @param comparator Comparator to use to sort simplex vertices from best
187      * to poorest.
188      * @return the best point in the transformed simplex.
189      * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
190      * if the maximal number of evaluations is exceeded.
191      */
192     private PointValuePair evaluateNewSimplex(final MultivariateFunction evaluationFunction,
193                                                   final PointValuePair[] original,
194                                                   final double coeff,
195                                                   final Comparator<PointValuePair> comparator) {
196         final double[] xSmallest = original[0].getPointRef();
197         // Perform a linear transformation on all the simplex points,
198         // except the first one.
199         setPoint(0, original[0]);
200         final int dim = getDimension();
201         for (int i = 1; i < getSize(); i++) {
202             final double[] xOriginal = original[i].getPointRef();
203             final double[] xTransformed = new double[dim];
204             for (int j = 0; j < dim; j++) {
205                 xTransformed[j] = xSmallest[j] + coeff * (xSmallest[j] - xOriginal[j]);
206             }
207             setPoint(i, new PointValuePair(xTransformed, Double.NaN, false));
208         }
209 
210         // Evaluate the simplex.
211         evaluate(evaluationFunction, comparator);
212 
213         return getPoint(0);
214     }
215 }