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