    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    package org.apache.commons.math3.optim.nonlinear.scalar.noderiv;
    018
    019    import java.util.Comparator;
    020
    021    import org.apache.commons.math3.analysis.MultivariateFunction;
    022    import org.apache.commons.math3.optim.PointValuePair;
    023
    024    /**
    025     * This class implements the multi-directional direct search method.
    026     *
    027     * @version $Id: MultiDirectionalSimplex.java 1364392 2012-07-22 18:27:12Z tn $
    028     * @since 3.0
    029     */
    030    public class MultiDirectionalSimplex extends AbstractSimplex {
    031        /** Default value for {@link #khi}: {@value}. */
    032        private static final double DEFAULT_KHI = 2;
    033        /** Default value for {@link #gamma}: {@value}. */
    034        private static final double DEFAULT_GAMMA = 0.5;
    035        /** Expansion coefficient. */
    036        private final double khi;
    037        /** Contraction coefficient. */
    038        private final double gamma;
    039
    040        /**
    041         * Build a multi-directional simplex with default coefficients.
    042         * The default values are 2.0 for khi and 0.5 for gamma.
    043         *
    044         * @param n Dimension of the simplex.
    045         */
    046        public MultiDirectionalSimplex(final int n) {
    047            this(n, 1d);
    048        }
    049
    050        /**
    051         * Build a multi-directional simplex with default coefficients.
    052         * The default values are 2.0 for khi and 0.5 for gamma.
    053         *
    054         * @param n Dimension of the simplex.
    055         * @param sideLength Length of the sides of the default (hypercube)
    056         * simplex. See {@link AbstractSimplex#AbstractSimplex(int,double)}.
    057         */
    058        public MultiDirectionalSimplex(final int n, double sideLength) {
    059            this(n, sideLength, DEFAULT_KHI, DEFAULT_GAMMA);
    060        }
    061
    062        /**
    063         * Build a multi-directional simplex with specified coefficients.
    064         *
    065         * @param n Dimension of the simplex. See
    066         * {@link AbstractSimplex#AbstractSimplex(int,double)}.
    067         * @param khi Expansion coefficient.
    068         * @param gamma Contraction coefficient.
    069         */
    070        public MultiDirectionalSimplex(final int n,
    071                                       final double khi, final double gamma) {
    072            this(n, 1d, khi, gamma);
    073        }
    074
    075        /**
    076         * Build a multi-directional simplex with specified coefficients.
    077         *
    078         * @param n Dimension of the simplex. See
    079         * {@link AbstractSimplex#AbstractSimplex(int,double)}.
    080         * @param sideLength Length of the sides of the default (hypercube)
    081         * simplex. See {@link AbstractSimplex#AbstractSimplex(int,double)}.
    082         * @param khi Expansion coefficient.
    083         * @param gamma Contraction coefficient.
    084         */
    085        public MultiDirectionalSimplex(final int n, double sideLength,
    086                                       final double khi, final double gamma) {
    087            super(n, sideLength);
    088
    089            this.khi   = khi;
    090            this.gamma = gamma;
    091        }
    092
    093        /**
    094         * Build a multi-directional simplex with default coefficients.
    095         * The default values are 2.0 for khi and 0.5 for gamma.
    096         *
    097         * @param steps Steps along the canonical axes representing box edges.
    098         * They may be negative but not zero. See
    099         */
    100        public MultiDirectionalSimplex(final double[] steps) {
    101            this(steps, DEFAULT_KHI, DEFAULT_GAMMA);
    102        }
    103
    104        /**
    105         * Build a multi-directional simplex with specified coefficients.
    106         *
    107         * @param steps Steps along the canonical axes representing box edges.
    108         * They may be negative but not zero. See
    109         * {@link AbstractSimplex#AbstractSimplex(double[])}.
    110         * @param khi Expansion coefficient.
    111         * @param gamma Contraction coefficient.
    112         */
    113        public MultiDirectionalSimplex(final double[] steps,
    114                                       final double khi, final double gamma) {
    115            super(steps);
    116
    117            this.khi   = khi;
    118            this.gamma = gamma;
    119        }
    120
    121        /**
    122         * Build a multi-directional simplex with default coefficients.
    123         * The default values are 2.0 for khi and 0.5 for gamma.
    124         *
    125         * @param referenceSimplex Reference simplex. See
    126         * {@link AbstractSimplex#AbstractSimplex(double[][])}.
    127         */
    128        public MultiDirectionalSimplex(final double[][] referenceSimplex) {
    129            this(referenceSimplex, DEFAULT_KHI, DEFAULT_GAMMA);
    130        }
    131
    132        /**
    133         * Build a multi-directional simplex with specified coefficients.
    134         *
    135         * @param referenceSimplex Reference simplex. See
    136         * {@link AbstractSimplex#AbstractSimplex(double[][])}.
    137         * @param khi Expansion coefficient.
    138         * @param gamma Contraction coefficient.
    139         * @throws org.apache.commons.math3.exception.NotStrictlyPositiveException
    140         * if the reference simplex does not contain at least one point.
    141         * @throws org.apache.commons.math3.exception.DimensionMismatchException
    142         * if there is a dimension mismatch in the reference simplex.
    143         */
    144        public MultiDirectionalSimplex(final double[][] referenceSimplex,
    145                                       final double khi, final double gamma) {
    146            super(referenceSimplex);
    147
    148            this.khi   = khi;
    149            this.gamma = gamma;
    150        }
    151
    152        /** {@inheritDoc} */
    153        @Override
    154        public void iterate(final MultivariateFunction evaluationFunction,
    155                            final Comparator<PointValuePair> comparator) {
    156            // Save the original simplex.
    157            final PointValuePair[] original = getPoints();
    158            final PointValuePair best = original[0];
    159
    160            // Perform a reflection step.
    161            final PointValuePair reflected = evaluateNewSimplex(evaluationFunction,
    162                                                                    original, 1, comparator);
    163            if (comparator.compare(reflected, best) < 0) {
    164                // Compute the expanded simplex.
    165                final PointValuePair[] reflectedSimplex = getPoints();
    166                final PointValuePair expanded = evaluateNewSimplex(evaluationFunction,
    167                                                                       original, khi, comparator);
    168                if (comparator.compare(reflected, expanded) <= 0) {
    169                    // Keep the reflected simplex.
    170                    setPoints(reflectedSimplex);
    171                }
    172                // Keep the expanded simplex.
    173                return;
    174            }
    175
    176            // Compute the contracted simplex.
    177            evaluateNewSimplex(evaluationFunction, original, gamma, comparator);
    178
    179        }
    180
    181        /**
    182         * Compute and evaluate a new simplex.
    183         *
    184         * @param evaluationFunction Evaluation function.
    185         * @param original Original simplex (to be preserved).
    186         * @param coeff Linear coefficient.
    187         * @param comparator Comparator to use to sort simplex vertices from best
    188         * to poorest.
    189         * @return the best point in the transformed simplex.
    190         * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
    191         * if the maximal number of evaluations is exceeded.
    192         */
    193        private PointValuePair evaluateNewSimplex(final MultivariateFunction evaluationFunction,
    194                                                      final PointValuePair[] original,
    195                                                      final double coeff,
    196                                                      final Comparator<PointValuePair> comparator) {
    197            final double[] xSmallest = original[0].getPointRef();
    198            // Perform a linear transformation on all the simplex points,
    199            // except the first one.
    200            setPoint(0, original[0]);
    201            final int dim = getDimension();
    202            for (int i = 1; i < getSize(); i++) {
    203                final double[] xOriginal = original[i].getPointRef();
    204                final double[] xTransformed = new double[dim];
    205                for (int j = 0; j < dim; j++) {
    206                    xTransformed[j] = xSmallest[j] + coeff * (xSmallest[j] - xOriginal[j]);
    207                }
    208                setPoint(i, new PointValuePair(xTransformed, Double.NaN, false));
    209            }
    210
    211            // Evaluate the simplex.
    212            evaluate(evaluationFunction, comparator);
    213
    214            return getPoint(0);
    215        }
    216    }