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 }