Simplex

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.apache.commons.math4.legacy.optim.nonlinear.scalar.noderiv;

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Collections;
import java.util.function.UnaryOperator;
import java.util.function.DoublePredicate;

import org.apache.commons.math4.legacy.analysis.MultivariateFunction;
import org.apache.commons.math4.legacy.exception.DimensionMismatchException;
import org.apache.commons.math4.legacy.exception.MathIllegalArgumentException;
import org.apache.commons.math4.legacy.exception.NotStrictlyPositiveException;
import org.apache.commons.math4.legacy.exception.ZeroException;
import org.apache.commons.math4.legacy.exception.util.LocalizedFormats;
import org.apache.commons.math4.legacy.optim.OptimizationData;
import org.apache.commons.math4.legacy.optim.PointValuePair;

/**
 * Represents a <a href="https://en.wikipedia.org/wiki/Simplex">simplex</a>.
 *
 * @see SimplexOptimizer
 */
public final class Simplex implements OptimizationData {
    /** Coordinates. */
    private final List<PointValuePair> points;

    /**
     * Builds from a given set of coordinates.
     *
     * @param referenceSimplex Reference simplex.
     * @throws NotStrictlyPositiveException if the reference simplex does not
     * contain at least one point.
     * @throws DimensionMismatchException if there is a dimension mismatch
     * in the reference simplex.
     * @throws IllegalArgumentException if one of its vertices is duplicated.
     */
    private Simplex(double[][] referenceSimplex) {
        if (referenceSimplex.length <= 0) {
            throw new NotStrictlyPositiveException(LocalizedFormats.SIMPLEX_NEED_ONE_POINT,
                                                   referenceSimplex.length);
        }
        final int len = referenceSimplex.length;
        points = new ArrayList<>(len);

        final int dim = len - 1;

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

            // Safety checks.
            if (refI.length != dim) {
                throw new DimensionMismatchException(refI.length, dim);
            }
            for (int j = 1; j < i; j++) {
                final double[] refJ = referenceSimplex[j];
                boolean allEquals = true;
                for (int k = 0; k < dim; k++) {
                    if (refI[k] != refJ[k]) {
                        allEquals = false;
                        break;
                    }
                }
                if (allEquals) {
                    throw new MathIllegalArgumentException(LocalizedFormats.EQUAL_VERTICES_IN_SIMPLEX,
                                                           i, j);
                }
            }

            points.add(new PointValuePair(refI, Double.NaN));
        }
    }

    /**
     * Builds from an existing simplex.
     *
     * @param points Simplex data.  Reference will be stored in the newly
     * constructed instance.
     */
    private Simplex(List<PointValuePair> points) {
        this.points = points;
    }

    /**
     * Builds from a given set of coordinates.
     *
     * @param simplex Simplex coordinates.
     * @return a new instance.
     * @throws NotStrictlyPositiveException if the reference simplex does not
     * contain at least one point.
     * @throws DimensionMismatchException if there is a dimension mismatch
     * in the reference simplex.
     * @throws IllegalArgumentException if one of its vertices is duplicated.
     */
    public static Simplex of(double[][] simplex) {
        return new Simplex(simplex);
    }

    /**
     * Builds simplex with the given side length.
     *
     * @param dim Space dimensions.
     * @param sideLength Length of the sides of the hypercube.
     * @return a new instance.
     */
    public static Simplex equalSidesAlongAxes(int dim,
                                              double sideLength) {
        final double[] steps = new double[dim];
        Arrays.fill(steps, sideLength);
        return alongAxes(steps);
    }

    /**
     * The start configuration for simplex is built from a box parallel to
     * the canonical axes of the space. The simplex is the subset of vertices
     * of a box parallel to the canonical axes. It is built as the path followed
     * while traveling from one vertex of the box to the diagonally opposite
     * vertex moving only along the box edges. The first vertex of the box will
     * be located at the origin of the coordinate system.
     *
     * To be used for simplex-based optimization, the simplex must be
     * {@link #translate(double[]) translated} so that its first vertex will be
     * the {@link org.apache.commons.math4.legacy.optim.InitialGuess initial guess}.
     *
     * For example, in dimension 3 a simplex has 4 vertices. Setting the
     * steps to (1, 10, 2) and the start point to (1, 1, 1) would imply the
     * initial simplex would be:
     * <ol>
     *  <li>(1, 1, 1),</li>
     *  <li>(2, 1, 1),</li>
     *  <li>(2, 11, 1),</li>
     *  <li>(2, 11, 3).</li>
     * </ol>
     *
     * @param steps Steps along the canonical axes representing box edges.
     * They may be negative but not zero.
     * @throws ZeroException if one of the steps is zero.
     * @return a new instance.
     */
    public static Simplex alongAxes(double[] steps) {
        if (steps.length == 0) {
            throw new ZeroException();
        }
        final int dim = steps.length;
        final int len = dim + 1;

        // Only the relative position of the n final vertices with respect
        // to the first one are stored.
        final double[][] simplex = new double[len][dim];
        for (int i = 1; i < len; i++) { // First point is the origin (zero).
            final double[] vertexI = simplex[i];
            for (int j = 0; j < i; j++) {
                if (steps[j] == 0) {
                    throw new ZeroException();
                }
                System.arraycopy(steps, 0, vertexI, 0, j + 1);
            }
        }

        return new Simplex(simplex);
    }

    /**
     * Returns the space dimension.
     *
     * @return the dimension of the simplex.
     */
    public int getDimension() {
        return points.size() - 1;
    }

    /**
     * Returns the number of vertices.
     *
     * @return the size of the simplex.
     */
    public int getSize() {
        return points.size();
    }

    /**
     * Evaluates the (non-evaluated) simplex points and returns a new instance
     * with vertices sorted from best to worst.
     *
     * @param function Evaluation function.
     * @param comparator Comparator for sorting vertices, from best to worst.
     * @return a new instance in which the vertices are sorted according to
     * the given {@code comparator}.
     */
    public Simplex evaluate(MultivariateFunction function,
                            Comparator<PointValuePair> comparator) {
        final List<PointValuePair> newPoints = new ArrayList<>(points.size());
        for (PointValuePair pv : points) {
            final double[] coord = pv.getPoint();
            final double value = Double.isNaN(pv.getValue()) ?
                function.value(coord) :
                pv.getValue();

            newPoints.add(new PointValuePair(coord, value, false));
        }

        Collections.sort(newPoints, comparator);
        return new Simplex(newPoints);
    }

    /**
     * Retrieves a copy of the simplex point stored at {@code index}.
     *
     * @param index Location.
     * @return the point at location {@code index}.
     */
    public PointValuePair get(int index) {
        final PointValuePair p = points.get(index);
        return new PointValuePair(p.getPoint(), p.getValue());
    }

    /**
     * Creates a (deep) copy of the simplex points.
     *
     * @return the points.
     */
    public List<PointValuePair> asList() {
        return asList(0, points.size());
    }

    /**
     * Generator of simplex transform.
     *
     * @see MultiDirectionalTransform
     * @see NelderMeadTransform
     * @see HedarFukushimaTransform
     */
    public interface TransformFactory extends OptimizationData {
        /**
         * Creates a simplex transformation.
         *
         * @param evaluationFunction Evaluation function.
         * @param comparator Vertex fitness comparator.
         * @param saAcceptance Simulated annealing acceptance test.
         * @return the simplex transform operator.
         */
        UnaryOperator<Simplex> create(MultivariateFunction evaluationFunction,
                                      Comparator<PointValuePair> comparator,
                                      DoublePredicate saAcceptance);
    }

    /**
     * Creates a (deep) copy of the simplex points within slots
     * {@code from} (included) and {@code to} (excluded).
     *
     * @param from Index of the first point to retrieve.
     * @param to One past the index of the last point to retrieve.
     * @return the points.
     * @throws IllegalArgumentException if {@code from} and {@code to} are
     * not within the {@code [0, n + 1]} interval (where {@code n} is the
     * space dimension) or {@code from > to}.
     */
    /* package private */ List<PointValuePair> asList(int from,
                                                      int to) {
        if (from < 0 ||
            to > points.size() ||
            from > to) {
            throw new IllegalArgumentException("Index");
        }

        final int len = to - from;
        final List<PointValuePair> copy = new ArrayList<>(len);
        for (int i = from; i < to; i++) {
            copy.add(get(i));
        }

        return copy;
    }

    /**
     * Utility for evaluating a point with coordinates \( a_i + s (b_i - a_i) \).
     *
     * @param a Cartesian coordinates.
     * @param s Scaling factor.
     * @param b Cartesian coordinates.
     * @param function Evaluation function.
     * @return a new point.
     */
    /* package private */ static PointValuePair newPoint(double[] a,
                                                         double s,
                                                         double[] b,
                                                         MultivariateFunction function) {
        final int dim = a.length;
        final double[] r = new double[dim];
        for (int i = 0; i < dim; i++) {
            final double m = a[i];
            r[i] = m + s * (b[i] - m);
        }

        return new PointValuePair(r, function.value(r), false);
    }

    /**
     * Utility for the "shrinking" a simplex: All the points will be
     * transformed except the one at index 0.
     *
     * @param sigma Shrink factor.
     * @param function Evaluation function.
     * @return a new instance.
     */
    /* package private */ Simplex shrink(double sigma,
                                         MultivariateFunction function) {
        final int replSize = getSize() - 1;
        final List<PointValuePair> replacement = new ArrayList<>();
        final double[] bestPoint = get(0).getPoint();
        for (int i = 0; i < replSize; i++) {
            replacement.add(Simplex.newPoint(bestPoint,
                                             sigma,
                                             get(i + 1).getPoint(),
                                             function));
        }

        return replaceLast(replacement);
    }

    /**
     * Translates the simplex such that the first point's new coordinates
     * will be at the given {@code point}.
     *
     * @param point Coordinates of the new simplex's first point.
     * @return the translated points.
     * @throws DimensionMismatchException if the dimensions do not match.
     */
    /* package private */ Simplex translate(double[] point) {
        final int dim = point.length;
        if (getDimension() != dim) {
            throw new DimensionMismatchException(getDimension(), dim);
        }
        final int len = points.size();
        final double[][] coordinates = new double[len][dim];
        final double[] current0 = points.get(0).getPoint(); // Current first point.

        // Set new vertices.
        for (int i = 0; i < len; i++) {
            final double[] currentI = points.get(i).getPoint();

            final double[] newI = coordinates[i];
            for (int k = 0; k < dim; k++) {
                newI[k] = point[k] + currentI[k] - current0[k];
            }
        }

        return new Simplex(coordinates);
    }

    /**
     * Creates a new simplex where the given {@code point} replaces the one at the
     * last position.
     * Caveat: No check is done that the resulting set of points forms is a simplex.
     *
     * @param point Point.
     * @return a new instance.
     */
    /* package private */ Simplex replaceLast(PointValuePair point) {
        final List<PointValuePair> newPoints = asList(0, getDimension()); // Deep copy.
        newPoints.add(new PointValuePair(point.getPoint(), // Deep copy.
                                         point.getValue(),
                                         false));

        return new Simplex(newPoints);
    }

    /**
     * Replace the last points of the simplex with the points from the given
     * {@code replacement} list.
     * Caveat: No check is done that the resulting set of points is a simplex.
     *
     * @param replacement List of points that will replace the last points of
     * the {@code simplex}.
     * @return a new instance.
     */
    /* package private */ Simplex replaceLast(List<PointValuePair> replacement) {
        final int nPoints = replacement.size();
        final int from = points.size() - nPoints;
        final List<PointValuePair> newPoints = asList(0, from); // Deep copy.


        for (int i = 0; i < nPoints; i++) {
            final PointValuePair p = replacement.get(i);
            newPoints.add(new PointValuePair(p.getPoint(), // Deep copy.
                                             p.getValue(),
                                             false));
        }

        return new Simplex(newPoints);
    }

    /**
     * @param list List of simplex points.
     * @return the centroid of the points in the given {@code list}.
     */
    /* package private */ static double[] centroid(List<PointValuePair> list) {
        final double[] centroid = list.get(0).getPoint();

        final int nPoints = list.size();
        final int dim = centroid.length;
        for (int i = 1; i < nPoints; i++) {
            final double[] p = list.get(i).getPoint();
            for (int k = 0; k < dim; k++) {
                centroid[k] += p[k];
            }
        }

        for (int k = 0; k < dim; k++) {
            centroid[k] /= nPoints;
        }

        return centroid;
    }
}