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