001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018 package org.apache.commons.math3.optimization.direct;
019
020 import java.util.Arrays;
021 import java.util.Comparator;
022
023 import org.apache.commons.math3.analysis.MultivariateFunction;
024 import org.apache.commons.math3.exception.NotStrictlyPositiveException;
025 import org.apache.commons.math3.exception.DimensionMismatchException;
026 import org.apache.commons.math3.exception.ZeroException;
027 import org.apache.commons.math3.exception.OutOfRangeException;
028 import org.apache.commons.math3.exception.NullArgumentException;
029 import org.apache.commons.math3.exception.MathIllegalArgumentException;
030 import org.apache.commons.math3.exception.util.LocalizedFormats;
031 import org.apache.commons.math3.optimization.PointValuePair;
032 import org.apache.commons.math3.optimization.OptimizationData;
033
034 /**
035 * This class implements the simplex concept.
036 * It is intended to be used in conjunction with {@link SimplexOptimizer}.
037 * <br/>
038 * The initial configuration of the simplex is set by the constructors
039 * {@link #AbstractSimplex(double[])} or {@link #AbstractSimplex(double[][])}.
040 * The other {@link #AbstractSimplex(int) constructor} will set all steps
041 * to 1, thus building a default configuration from a unit hypercube.
042 * <br/>
043 * Users <em>must</em> call the {@link #build(double[]) build} method in order
044 * to create the data structure that will be acted on by the other methods of
045 * this class.
046 *
047 * @see SimplexOptimizer
048 * @version $Id: AbstractSimplex.java 1422230 2012-12-15 12:11:13Z erans $
049 * @deprecated As of 3.1 (to be removed in 4.0).
050 * @since 3.0
051 */
052 @Deprecated
053 public abstract class AbstractSimplex implements OptimizationData {
054 /** Simplex. */
055 private PointValuePair[] simplex;
056 /** Start simplex configuration. */
057 private double[][] startConfiguration;
058 /** Simplex dimension (must be equal to {@code simplex.length - 1}). */
059 private final int dimension;
060
061 /**
062 * Build a unit hypercube simplex.
063 *
064 * @param n Dimension of the simplex.
065 */
066 protected AbstractSimplex(int n) {
067 this(n, 1d);
068 }
069
070 /**
071 * Build a hypercube simplex with the given side length.
072 *
073 * @param n Dimension of the simplex.
074 * @param sideLength Length of the sides of the hypercube.
075 */
076 protected AbstractSimplex(int n,
077 double sideLength) {
078 this(createHypercubeSteps(n, sideLength));
079 }
080
081 /**
082 * The start configuration for simplex is built from a box parallel to
083 * the canonical axes of the space. The simplex is the subset of vertices
084 * of a box parallel to the canonical axes. It is built as the path followed
085 * while traveling from one vertex of the box to the diagonally opposite
086 * vertex moving only along the box edges. The first vertex of the box will
087 * be located at the start point of the optimization.
088 * As an example, in dimension 3 a simplex has 4 vertices. Setting the
089 * steps to (1, 10, 2) and the start point to (1, 1, 1) would imply the
090 * start simplex would be: { (1, 1, 1), (2, 1, 1), (2, 11, 1), (2, 11, 3) }.
091 * The first vertex would be set to the start point at (1, 1, 1) and the
092 * last vertex would be set to the diagonally opposite vertex at (2, 11, 3).
093 *
094 * @param steps Steps along the canonical axes representing box edges. They
095 * may be negative but not zero.
096 * @throws NullArgumentException if {@code steps} is {@code null}.
097 * @throws ZeroException if one of the steps is zero.
098 */
099 protected AbstractSimplex(final double[] steps) {
100 if (steps == null) {
101 throw new NullArgumentException();
102 }
103 if (steps.length == 0) {
104 throw new ZeroException();
105 }
106 dimension = steps.length;
107
108 // Only the relative position of the n final vertices with respect
109 // to the first one are stored.
110 startConfiguration = new double[dimension][dimension];
111 for (int i = 0; i < dimension; i++) {
112 final double[] vertexI = startConfiguration[i];
113 for (int j = 0; j < i + 1; j++) {
114 if (steps[j] == 0) {
115 throw new ZeroException(LocalizedFormats.EQUAL_VERTICES_IN_SIMPLEX);
116 }
117 System.arraycopy(steps, 0, vertexI, 0, j + 1);
118 }
119 }
120 }
121
122 /**
123 * The real initial simplex will be set up by moving the reference
124 * simplex such that its first point is located at the start point of the
125 * optimization.
126 *
127 * @param referenceSimplex Reference simplex.
128 * @throws NotStrictlyPositiveException if the reference simplex does not
129 * contain at least one point.
130 * @throws DimensionMismatchException if there is a dimension mismatch
131 * in the reference simplex.
132 * @throws IllegalArgumentException if one of its vertices is duplicated.
133 */
134 protected AbstractSimplex(final double[][] referenceSimplex) {
135 if (referenceSimplex.length <= 0) {
136 throw new NotStrictlyPositiveException(LocalizedFormats.SIMPLEX_NEED_ONE_POINT,
137 referenceSimplex.length);
138 }
139 dimension = referenceSimplex.length - 1;
140
141 // Only the relative position of the n final vertices with respect
142 // to the first one are stored.
143 startConfiguration = new double[dimension][dimension];
144 final double[] ref0 = referenceSimplex[0];
145
146 // Loop over vertices.
147 for (int i = 0; i < referenceSimplex.length; i++) {
148 final double[] refI = referenceSimplex[i];
149
150 // Safety checks.
151 if (refI.length != dimension) {
152 throw new DimensionMismatchException(refI.length, dimension);
153 }
154 for (int j = 0; j < i; j++) {
155 final double[] refJ = referenceSimplex[j];
156 boolean allEquals = true;
157 for (int k = 0; k < dimension; k++) {
158 if (refI[k] != refJ[k]) {
159 allEquals = false;
160 break;
161 }
162 }
163 if (allEquals) {
164 throw new MathIllegalArgumentException(LocalizedFormats.EQUAL_VERTICES_IN_SIMPLEX,
165 i, j);
166 }
167 }
168
169 // Store vertex i position relative to vertex 0 position.
170 if (i > 0) {
171 final double[] confI = startConfiguration[i - 1];
172 for (int k = 0; k < dimension; k++) {
173 confI[k] = refI[k] - ref0[k];
174 }
175 }
176 }
177 }
178
179 /**
180 * Get simplex dimension.
181 *
182 * @return the dimension of the simplex.
183 */
184 public int getDimension() {
185 return dimension;
186 }
187
188 /**
189 * Get simplex size.
190 * After calling the {@link #build(double[]) build} method, this method will
191 * will be equivalent to {@code getDimension() + 1}.
192 *
193 * @return the size of the simplex.
194 */
195 public int getSize() {
196 return simplex.length;
197 }
198
199 /**
200 * Compute the next simplex of the algorithm.
201 *
202 * @param evaluationFunction Evaluation function.
203 * @param comparator Comparator to use to sort simplex vertices from best
204 * to worst.
205 * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
206 * if the algorithm fails to converge.
207 */
208 public abstract void iterate(final MultivariateFunction evaluationFunction,
209 final Comparator<PointValuePair> comparator);
210
211 /**
212 * Build an initial simplex.
213 *
214 * @param startPoint First point of the simplex.
215 * @throws DimensionMismatchException if the start point does not match
216 * simplex dimension.
217 */
218 public void build(final double[] startPoint) {
219 if (dimension != startPoint.length) {
220 throw new DimensionMismatchException(dimension, startPoint.length);
221 }
222
223 // Set first vertex.
224 simplex = new PointValuePair[dimension + 1];
225 simplex[0] = new PointValuePair(startPoint, Double.NaN);
226
227 // Set remaining vertices.
228 for (int i = 0; i < dimension; i++) {
229 final double[] confI = startConfiguration[i];
230 final double[] vertexI = new double[dimension];
231 for (int k = 0; k < dimension; k++) {
232 vertexI[k] = startPoint[k] + confI[k];
233 }
234 simplex[i + 1] = new PointValuePair(vertexI, Double.NaN);
235 }
236 }
237
238 /**
239 * Evaluate all the non-evaluated points of the simplex.
240 *
241 * @param evaluationFunction Evaluation function.
242 * @param comparator Comparator to use to sort simplex vertices from best to worst.
243 * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
244 * if the maximal number of evaluations is exceeded.
245 */
246 public void evaluate(final MultivariateFunction evaluationFunction,
247 final Comparator<PointValuePair> comparator) {
248 // Evaluate the objective function at all non-evaluated simplex points.
249 for (int i = 0; i < simplex.length; i++) {
250 final PointValuePair vertex = simplex[i];
251 final double[] point = vertex.getPointRef();
252 if (Double.isNaN(vertex.getValue())) {
253 simplex[i] = new PointValuePair(point, evaluationFunction.value(point), false);
254 }
255 }
256
257 // Sort the simplex from best to worst.
258 Arrays.sort(simplex, comparator);
259 }
260
261 /**
262 * Replace the worst point of the simplex by a new point.
263 *
264 * @param pointValuePair Point to insert.
265 * @param comparator Comparator to use for sorting the simplex vertices
266 * from best to worst.
267 */
268 protected void replaceWorstPoint(PointValuePair pointValuePair,
269 final Comparator<PointValuePair> comparator) {
270 for (int i = 0; i < dimension; i++) {
271 if (comparator.compare(simplex[i], pointValuePair) > 0) {
272 PointValuePair tmp = simplex[i];
273 simplex[i] = pointValuePair;
274 pointValuePair = tmp;
275 }
276 }
277 simplex[dimension] = pointValuePair;
278 }
279
280 /**
281 * Get the points of the simplex.
282 *
283 * @return all the simplex points.
284 */
285 public PointValuePair[] getPoints() {
286 final PointValuePair[] copy = new PointValuePair[simplex.length];
287 System.arraycopy(simplex, 0, copy, 0, simplex.length);
288 return copy;
289 }
290
291 /**
292 * Get the simplex point stored at the requested {@code index}.
293 *
294 * @param index Location.
295 * @return the point at location {@code index}.
296 */
297 public PointValuePair getPoint(int index) {
298 if (index < 0 ||
299 index >= simplex.length) {
300 throw new OutOfRangeException(index, 0, simplex.length - 1);
301 }
302 return simplex[index];
303 }
304
305 /**
306 * Store a new point at location {@code index}.
307 * Note that no deep-copy of {@code point} is performed.
308 *
309 * @param index Location.
310 * @param point New value.
311 */
312 protected void setPoint(int index, PointValuePair point) {
313 if (index < 0 ||
314 index >= simplex.length) {
315 throw new OutOfRangeException(index, 0, simplex.length - 1);
316 }
317 simplex[index] = point;
318 }
319
320 /**
321 * Replace all points.
322 * Note that no deep-copy of {@code points} is performed.
323 *
324 * @param points New Points.
325 */
326 protected void setPoints(PointValuePair[] points) {
327 if (points.length != simplex.length) {
328 throw new DimensionMismatchException(points.length, simplex.length);
329 }
330 simplex = points;
331 }
332
333 /**
334 * Create steps for a unit hypercube.
335 *
336 * @param n Dimension of the hypercube.
337 * @param sideLength Length of the sides of the hypercube.
338 * @return the steps.
339 */
340 private static double[] createHypercubeSteps(int n,
341 double sideLength) {
342 final double[] steps = new double[n];
343 for (int i = 0; i < n; i++) {
344 steps[i] = sideLength;
345 }
346 return steps;
347 }
348 }