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.optim.nonlinear.scalar.noderiv; 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.optim.PointValuePair; 032 import org.apache.commons.math3.optim.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 1397759 2012-10-13 01:12:58Z erans $ 049 * @since 3.0 050 */ 051 public abstract class AbstractSimplex implements OptimizationData { 052 /** Simplex. */ 053 private PointValuePair[] simplex; 054 /** Start simplex configuration. */ 055 private double[][] startConfiguration; 056 /** Simplex dimension (must be equal to {@code simplex.length - 1}). */ 057 private final int dimension; 058 059 /** 060 * Build a unit hypercube simplex. 061 * 062 * @param n Dimension of the simplex. 063 */ 064 protected AbstractSimplex(int n) { 065 this(n, 1d); 066 } 067 068 /** 069 * Build a hypercube simplex with the given side length. 070 * 071 * @param n Dimension of the simplex. 072 * @param sideLength Length of the sides of the hypercube. 073 */ 074 protected AbstractSimplex(int n, 075 double sideLength) { 076 this(createHypercubeSteps(n, sideLength)); 077 } 078 079 /** 080 * The start configuration for simplex is built from a box parallel to 081 * the canonical axes of the space. The simplex is the subset of vertices 082 * of a box parallel to the canonical axes. It is built as the path followed 083 * while traveling from one vertex of the box to the diagonally opposite 084 * vertex moving only along the box edges. The first vertex of the box will 085 * be located at the start point of the optimization. 086 * As an example, in dimension 3 a simplex has 4 vertices. Setting the 087 * steps to (1, 10, 2) and the start point to (1, 1, 1) would imply the 088 * start simplex would be: { (1, 1, 1), (2, 1, 1), (2, 11, 1), (2, 11, 3) }. 089 * The first vertex would be set to the start point at (1, 1, 1) and the 090 * last vertex would be set to the diagonally opposite vertex at (2, 11, 3). 091 * 092 * @param steps Steps along the canonical axes representing box edges. They 093 * may be negative but not zero. 094 * @throws NullArgumentException if {@code steps} is {@code null}. 095 * @throws ZeroException if one of the steps is zero. 096 */ 097 protected AbstractSimplex(final double[] steps) { 098 if (steps == null) { 099 throw new NullArgumentException(); 100 } 101 if (steps.length == 0) { 102 throw new ZeroException(); 103 } 104 dimension = steps.length; 105 106 // Only the relative position of the n final vertices with respect 107 // to the first one are stored. 108 startConfiguration = new double[dimension][dimension]; 109 for (int i = 0; i < dimension; i++) { 110 final double[] vertexI = startConfiguration[i]; 111 for (int j = 0; j < i + 1; j++) { 112 if (steps[j] == 0) { 113 throw new ZeroException(LocalizedFormats.EQUAL_VERTICES_IN_SIMPLEX); 114 } 115 System.arraycopy(steps, 0, vertexI, 0, j + 1); 116 } 117 } 118 } 119 120 /** 121 * The real initial simplex will be set up by moving the reference 122 * simplex such that its first point is located at the start point of the 123 * optimization. 124 * 125 * @param referenceSimplex Reference simplex. 126 * @throws NotStrictlyPositiveException if the reference simplex does not 127 * contain at least one point. 128 * @throws DimensionMismatchException if there is a dimension mismatch 129 * in the reference simplex. 130 * @throws IllegalArgumentException if one of its vertices is duplicated. 131 */ 132 protected AbstractSimplex(final double[][] referenceSimplex) { 133 if (referenceSimplex.length <= 0) { 134 throw new NotStrictlyPositiveException(LocalizedFormats.SIMPLEX_NEED_ONE_POINT, 135 referenceSimplex.length); 136 } 137 dimension = referenceSimplex.length - 1; 138 139 // Only the relative position of the n final vertices with respect 140 // to the first one are stored. 141 startConfiguration = new double[dimension][dimension]; 142 final double[] ref0 = referenceSimplex[0]; 143 144 // Loop over vertices. 145 for (int i = 0; i < referenceSimplex.length; i++) { 146 final double[] refI = referenceSimplex[i]; 147 148 // Safety checks. 149 if (refI.length != dimension) { 150 throw new DimensionMismatchException(refI.length, dimension); 151 } 152 for (int j = 0; j < i; j++) { 153 final double[] refJ = referenceSimplex[j]; 154 boolean allEquals = true; 155 for (int k = 0; k < dimension; k++) { 156 if (refI[k] != refJ[k]) { 157 allEquals = false; 158 break; 159 } 160 } 161 if (allEquals) { 162 throw new MathIllegalArgumentException(LocalizedFormats.EQUAL_VERTICES_IN_SIMPLEX, 163 i, j); 164 } 165 } 166 167 // Store vertex i position relative to vertex 0 position. 168 if (i > 0) { 169 final double[] confI = startConfiguration[i - 1]; 170 for (int k = 0; k < dimension; k++) { 171 confI[k] = refI[k] - ref0[k]; 172 } 173 } 174 } 175 } 176 177 /** 178 * Get simplex dimension. 179 * 180 * @return the dimension of the simplex. 181 */ 182 public int getDimension() { 183 return dimension; 184 } 185 186 /** 187 * Get simplex size. 188 * After calling the {@link #build(double[]) build} method, this method will 189 * will be equivalent to {@code getDimension() + 1}. 190 * 191 * @return the size of the simplex. 192 */ 193 public int getSize() { 194 return simplex.length; 195 } 196 197 /** 198 * Compute the next simplex of the algorithm. 199 * 200 * @param evaluationFunction Evaluation function. 201 * @param comparator Comparator to use to sort simplex vertices from best 202 * to worst. 203 * @throws org.apache.commons.math3.exception.TooManyEvaluationsException 204 * if the algorithm fails to converge. 205 */ 206 public abstract void iterate(final MultivariateFunction evaluationFunction, 207 final Comparator<PointValuePair> comparator); 208 209 /** 210 * Build an initial simplex. 211 * 212 * @param startPoint First point of the simplex. 213 * @throws DimensionMismatchException if the start point does not match 214 * simplex dimension. 215 */ 216 public void build(final double[] startPoint) { 217 if (dimension != startPoint.length) { 218 throw new DimensionMismatchException(dimension, startPoint.length); 219 } 220 221 // Set first vertex. 222 simplex = new PointValuePair[dimension + 1]; 223 simplex[0] = new PointValuePair(startPoint, Double.NaN); 224 225 // Set remaining vertices. 226 for (int i = 0; i < dimension; i++) { 227 final double[] confI = startConfiguration[i]; 228 final double[] vertexI = new double[dimension]; 229 for (int k = 0; k < dimension; k++) { 230 vertexI[k] = startPoint[k] + confI[k]; 231 } 232 simplex[i + 1] = new PointValuePair(vertexI, Double.NaN); 233 } 234 } 235 236 /** 237 * Evaluate all the non-evaluated points of the simplex. 238 * 239 * @param evaluationFunction Evaluation function. 240 * @param comparator Comparator to use to sort simplex vertices from best to worst. 241 * @throws org.apache.commons.math3.exception.TooManyEvaluationsException 242 * if the maximal number of evaluations is exceeded. 243 */ 244 public void evaluate(final MultivariateFunction evaluationFunction, 245 final Comparator<PointValuePair> comparator) { 246 // Evaluate the objective function at all non-evaluated simplex points. 247 for (int i = 0; i < simplex.length; i++) { 248 final PointValuePair vertex = simplex[i]; 249 final double[] point = vertex.getPointRef(); 250 if (Double.isNaN(vertex.getValue())) { 251 simplex[i] = new PointValuePair(point, evaluationFunction.value(point), false); 252 } 253 } 254 255 // Sort the simplex from best to worst. 256 Arrays.sort(simplex, comparator); 257 } 258 259 /** 260 * Replace the worst point of the simplex by a new point. 261 * 262 * @param pointValuePair Point to insert. 263 * @param comparator Comparator to use for sorting the simplex vertices 264 * from best to worst. 265 */ 266 protected void replaceWorstPoint(PointValuePair pointValuePair, 267 final Comparator<PointValuePair> comparator) { 268 for (int i = 0; i < dimension; i++) { 269 if (comparator.compare(simplex[i], pointValuePair) > 0) { 270 PointValuePair tmp = simplex[i]; 271 simplex[i] = pointValuePair; 272 pointValuePair = tmp; 273 } 274 } 275 simplex[dimension] = pointValuePair; 276 } 277 278 /** 279 * Get the points of the simplex. 280 * 281 * @return all the simplex points. 282 */ 283 public PointValuePair[] getPoints() { 284 final PointValuePair[] copy = new PointValuePair[simplex.length]; 285 System.arraycopy(simplex, 0, copy, 0, simplex.length); 286 return copy; 287 } 288 289 /** 290 * Get the simplex point stored at the requested {@code index}. 291 * 292 * @param index Location. 293 * @return the point at location {@code index}. 294 */ 295 public PointValuePair getPoint(int index) { 296 if (index < 0 || 297 index >= simplex.length) { 298 throw new OutOfRangeException(index, 0, simplex.length - 1); 299 } 300 return simplex[index]; 301 } 302 303 /** 304 * Store a new point at location {@code index}. 305 * Note that no deep-copy of {@code point} is performed. 306 * 307 * @param index Location. 308 * @param point New value. 309 */ 310 protected void setPoint(int index, PointValuePair point) { 311 if (index < 0 || 312 index >= simplex.length) { 313 throw new OutOfRangeException(index, 0, simplex.length - 1); 314 } 315 simplex[index] = point; 316 } 317 318 /** 319 * Replace all points. 320 * Note that no deep-copy of {@code points} is performed. 321 * 322 * @param points New Points. 323 */ 324 protected void setPoints(PointValuePair[] points) { 325 if (points.length != simplex.length) { 326 throw new DimensionMismatchException(points.length, simplex.length); 327 } 328 simplex = points; 329 } 330 331 /** 332 * Create steps for a unit hypercube. 333 * 334 * @param n Dimension of the hypercube. 335 * @param sideLength Length of the sides of the hypercube. 336 * @return the steps. 337 */ 338 private static double[] createHypercubeSteps(int n, 339 double sideLength) { 340 final double[] steps = new double[n]; 341 for (int i = 0; i < n; i++) { 342 steps[i] = sideLength; 343 } 344 return steps; 345 } 346 }