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