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