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 }