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