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 1435539 2013-01-19 13:27:24Z 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    }