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