AbstractSimplex.java

  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. import java.util.Arrays;
  19. import java.util.Comparator;

  20. import org.apache.commons.math3.analysis.MultivariateFunction;
  21. import org.apache.commons.math3.exception.NotStrictlyPositiveException;
  22. import org.apache.commons.math3.exception.DimensionMismatchException;
  23. import org.apache.commons.math3.exception.ZeroException;
  24. import org.apache.commons.math3.exception.OutOfRangeException;
  25. import org.apache.commons.math3.exception.NullArgumentException;
  26. import org.apache.commons.math3.exception.MathIllegalArgumentException;
  27. import org.apache.commons.math3.exception.util.LocalizedFormats;
  28. import org.apache.commons.math3.optim.PointValuePair;
  29. import org.apache.commons.math3.optim.OptimizationData;

  30. /**
  31.  * This class implements the simplex concept.
  32.  * It is intended to be used in conjunction with {@link SimplexOptimizer}.
  33.  * <br/>
  34.  * The initial configuration of the simplex is set by the constructors
  35.  * {@link #AbstractSimplex(double[])} or {@link #AbstractSimplex(double[][])}.
  36.  * The other {@link #AbstractSimplex(int) constructor} will set all steps
  37.  * to 1, thus building a default configuration from a unit hypercube.
  38.  * <br/>
  39.  * Users <em>must</em> call the {@link #build(double[]) build} method in order
  40.  * to create the data structure that will be acted on by the other methods of
  41.  * this class.
  42.  *
  43.  * @see SimplexOptimizer
  44.  * @since 3.0
  45.  */
  46. public abstract class AbstractSimplex implements OptimizationData {
  47.     /** Simplex. */
  48.     private PointValuePair[] simplex;
  49.     /** Start simplex configuration. */
  50.     private double[][] startConfiguration;
  51.     /** Simplex dimension (must be equal to {@code simplex.length - 1}). */
  52.     private final int dimension;

  53.     /**
  54.      * Build a unit hypercube simplex.
  55.      *
  56.      * @param n Dimension of the simplex.
  57.      */
  58.     protected AbstractSimplex(int n) {
  59.         this(n, 1d);
  60.     }

  61.     /**
  62.      * Build a hypercube simplex with the given side length.
  63.      *
  64.      * @param n Dimension of the simplex.
  65.      * @param sideLength Length of the sides of the hypercube.
  66.      */
  67.     protected AbstractSimplex(int n,
  68.                               double sideLength) {
  69.         this(createHypercubeSteps(n, sideLength));
  70.     }

  71.     /**
  72.      * The start configuration for simplex is built from a box parallel to
  73.      * the canonical axes of the space. The simplex is the subset of vertices
  74.      * of a box parallel to the canonical axes. It is built as the path followed
  75.      * while traveling from one vertex of the box to the diagonally opposite
  76.      * vertex moving only along the box edges. The first vertex of the box will
  77.      * be located at the start point of the optimization.
  78.      * As an example, in dimension 3 a simplex has 4 vertices. Setting the
  79.      * steps to (1, 10, 2) and the start point to (1, 1, 1) would imply the
  80.      * start simplex would be: { (1, 1, 1), (2, 1, 1), (2, 11, 1), (2, 11, 3) }.
  81.      * The first vertex would be set to the start point at (1, 1, 1) and the
  82.      * last vertex would be set to the diagonally opposite vertex at (2, 11, 3).
  83.      *
  84.      * @param steps Steps along the canonical axes representing box edges. They
  85.      * may be negative but not zero.
  86.      * @throws NullArgumentException if {@code steps} is {@code null}.
  87.      * @throws ZeroException if one of the steps is zero.
  88.      */
  89.     protected AbstractSimplex(final double[] steps) {
  90.         if (steps == null) {
  91.             throw new NullArgumentException();
  92.         }
  93.         if (steps.length == 0) {
  94.             throw new ZeroException();
  95.         }
  96.         dimension = steps.length;

  97.         // Only the relative position of the n final vertices with respect
  98.         // to the first one are stored.
  99.         startConfiguration = new double[dimension][dimension];
  100.         for (int i = 0; i < dimension; i++) {
  101.             final double[] vertexI = startConfiguration[i];
  102.             for (int j = 0; j < i + 1; j++) {
  103.                 if (steps[j] == 0) {
  104.                     throw new ZeroException(LocalizedFormats.EQUAL_VERTICES_IN_SIMPLEX);
  105.                 }
  106.                 System.arraycopy(steps, 0, vertexI, 0, j + 1);
  107.             }
  108.         }
  109.     }

  110.     /**
  111.      * The real initial simplex will be set up by moving the reference
  112.      * simplex such that its first point is located at the start point of the
  113.      * optimization.
  114.      *
  115.      * @param referenceSimplex Reference simplex.
  116.      * @throws NotStrictlyPositiveException if the reference simplex does not
  117.      * contain at least one point.
  118.      * @throws DimensionMismatchException if there is a dimension mismatch
  119.      * in the reference simplex.
  120.      * @throws IllegalArgumentException if one of its vertices is duplicated.
  121.      */
  122.     protected AbstractSimplex(final double[][] referenceSimplex) {
  123.         if (referenceSimplex.length <= 0) {
  124.             throw new NotStrictlyPositiveException(LocalizedFormats.SIMPLEX_NEED_ONE_POINT,
  125.                                                    referenceSimplex.length);
  126.         }
  127.         dimension = referenceSimplex.length - 1;

  128.         // Only the relative position of the n final vertices with respect
  129.         // to the first one are stored.
  130.         startConfiguration = new double[dimension][dimension];
  131.         final double[] ref0 = referenceSimplex[0];

  132.         // Loop over vertices.
  133.         for (int i = 0; i < referenceSimplex.length; i++) {
  134.             final double[] refI = referenceSimplex[i];

  135.             // Safety checks.
  136.             if (refI.length != dimension) {
  137.                 throw new DimensionMismatchException(refI.length, dimension);
  138.             }
  139.             for (int j = 0; j < i; j++) {
  140.                 final double[] refJ = referenceSimplex[j];
  141.                 boolean allEquals = true;
  142.                 for (int k = 0; k < dimension; k++) {
  143.                     if (refI[k] != refJ[k]) {
  144.                         allEquals = false;
  145.                         break;
  146.                     }
  147.                 }
  148.                 if (allEquals) {
  149.                     throw new MathIllegalArgumentException(LocalizedFormats.EQUAL_VERTICES_IN_SIMPLEX,
  150.                                                            i, j);
  151.                 }
  152.             }

  153.             // Store vertex i position relative to vertex 0 position.
  154.             if (i > 0) {
  155.                 final double[] confI = startConfiguration[i - 1];
  156.                 for (int k = 0; k < dimension; k++) {
  157.                     confI[k] = refI[k] - ref0[k];
  158.                 }
  159.             }
  160.         }
  161.     }

  162.     /**
  163.      * Get simplex dimension.
  164.      *
  165.      * @return the dimension of the simplex.
  166.      */
  167.     public int getDimension() {
  168.         return dimension;
  169.     }

  170.     /**
  171.      * Get simplex size.
  172.      * After calling the {@link #build(double[]) build} method, this method will
  173.      * will be equivalent to {@code getDimension() + 1}.
  174.      *
  175.      * @return the size of the simplex.
  176.      */
  177.     public int getSize() {
  178.         return simplex.length;
  179.     }

  180.     /**
  181.      * Compute the next simplex of the algorithm.
  182.      *
  183.      * @param evaluationFunction Evaluation function.
  184.      * @param comparator Comparator to use to sort simplex vertices from best
  185.      * to worst.
  186.      * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
  187.      * if the algorithm fails to converge.
  188.      */
  189.     public abstract void iterate(final MultivariateFunction evaluationFunction,
  190.                                  final Comparator<PointValuePair> comparator);

  191.     /**
  192.      * Build an initial simplex.
  193.      *
  194.      * @param startPoint First point of the simplex.
  195.      * @throws DimensionMismatchException if the start point does not match
  196.      * simplex dimension.
  197.      */
  198.     public void build(final double[] startPoint) {
  199.         if (dimension != startPoint.length) {
  200.             throw new DimensionMismatchException(dimension, startPoint.length);
  201.         }

  202.         // Set first vertex.
  203.         simplex = new PointValuePair[dimension + 1];
  204.         simplex[0] = new PointValuePair(startPoint, Double.NaN);

  205.         // Set remaining vertices.
  206.         for (int i = 0; i < dimension; i++) {
  207.             final double[] confI = startConfiguration[i];
  208.             final double[] vertexI = new double[dimension];
  209.             for (int k = 0; k < dimension; k++) {
  210.                 vertexI[k] = startPoint[k] + confI[k];
  211.             }
  212.             simplex[i + 1] = new PointValuePair(vertexI, Double.NaN);
  213.         }
  214.     }

  215.     /**
  216.      * Evaluate all the non-evaluated points of the simplex.
  217.      *
  218.      * @param evaluationFunction Evaluation function.
  219.      * @param comparator Comparator to use to sort simplex vertices from best to worst.
  220.      * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
  221.      * if the maximal number of evaluations is exceeded.
  222.      */
  223.     public void evaluate(final MultivariateFunction evaluationFunction,
  224.                          final Comparator<PointValuePair> comparator) {
  225.         // Evaluate the objective function at all non-evaluated simplex points.
  226.         for (int i = 0; i < simplex.length; i++) {
  227.             final PointValuePair vertex = simplex[i];
  228.             final double[] point = vertex.getPointRef();
  229.             if (Double.isNaN(vertex.getValue())) {
  230.                 simplex[i] = new PointValuePair(point, evaluationFunction.value(point), false);
  231.             }
  232.         }

  233.         // Sort the simplex from best to worst.
  234.         Arrays.sort(simplex, comparator);
  235.     }

  236.     /**
  237.      * Replace the worst point of the simplex by a new point.
  238.      *
  239.      * @param pointValuePair Point to insert.
  240.      * @param comparator Comparator to use for sorting the simplex vertices
  241.      * from best to worst.
  242.      */
  243.     protected void replaceWorstPoint(PointValuePair pointValuePair,
  244.                                      final Comparator<PointValuePair> comparator) {
  245.         for (int i = 0; i < dimension; i++) {
  246.             if (comparator.compare(simplex[i], pointValuePair) > 0) {
  247.                 PointValuePair tmp = simplex[i];
  248.                 simplex[i] = pointValuePair;
  249.                 pointValuePair = tmp;
  250.             }
  251.         }
  252.         simplex[dimension] = pointValuePair;
  253.     }

  254.     /**
  255.      * Get the points of the simplex.
  256.      *
  257.      * @return all the simplex points.
  258.      */
  259.     public PointValuePair[] getPoints() {
  260.         final PointValuePair[] copy = new PointValuePair[simplex.length];
  261.         System.arraycopy(simplex, 0, copy, 0, simplex.length);
  262.         return copy;
  263.     }

  264.     /**
  265.      * Get the simplex point stored at the requested {@code index}.
  266.      *
  267.      * @param index Location.
  268.      * @return the point at location {@code index}.
  269.      */
  270.     public PointValuePair getPoint(int index) {
  271.         if (index < 0 ||
  272.             index >= simplex.length) {
  273.             throw new OutOfRangeException(index, 0, simplex.length - 1);
  274.         }
  275.         return simplex[index];
  276.     }

  277.     /**
  278.      * Store a new point at location {@code index}.
  279.      * Note that no deep-copy of {@code point} is performed.
  280.      *
  281.      * @param index Location.
  282.      * @param point New value.
  283.      */
  284.     protected void setPoint(int index, PointValuePair point) {
  285.         if (index < 0 ||
  286.             index >= simplex.length) {
  287.             throw new OutOfRangeException(index, 0, simplex.length - 1);
  288.         }
  289.         simplex[index] = point;
  290.     }

  291.     /**
  292.      * Replace all points.
  293.      * Note that no deep-copy of {@code points} is performed.
  294.      *
  295.      * @param points New Points.
  296.      */
  297.     protected void setPoints(PointValuePair[] points) {
  298.         if (points.length != simplex.length) {
  299.             throw new DimensionMismatchException(points.length, simplex.length);
  300.         }
  301.         simplex = points;
  302.     }

  303.     /**
  304.      * Create steps for a unit hypercube.
  305.      *
  306.      * @param n Dimension of the hypercube.
  307.      * @param sideLength Length of the sides of the hypercube.
  308.      * @return the steps.
  309.      */
  310.     private static double[] createHypercubeSteps(int n,
  311.                                                  double sideLength) {
  312.         final double[] steps = new double[n];
  313.         for (int i = 0; i < n; i++) {
  314.             steps[i] = sideLength;
  315.         }
  316.         return steps;
  317.     }
  318. }