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    
018    package org.apache.commons.math.optimization.direct;
019    
020    import java.util.Comparator;
021    
022    import org.apache.commons.math.FunctionEvaluationException;
023    import org.apache.commons.math.optimization.OptimizationException;
024    import org.apache.commons.math.optimization.RealPointValuePair;
025    
026    /** 
027     * This class implements the multi-directional direct search method.
028     *
029     * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
030     * @see NelderMead
031     * @since 1.2
032     */
033    public class MultiDirectional extends DirectSearchOptimizer {
034    
035        /** Expansion coefficient. */
036        private final double khi;
037    
038        /** Contraction coefficient. */
039        private final double gamma;
040    
041        /** Build a multi-directional optimizer with default coefficients.
042         * <p>The default values are 2.0 for khi and 0.5 for gamma.</p>
043         */
044        public MultiDirectional() {
045            this.khi   = 2.0;
046            this.gamma = 0.5;
047        }
048    
049        /** Build a multi-directional optimizer with specified coefficients.
050         * @param khi expansion coefficient
051         * @param gamma contraction coefficient
052         */
053        public MultiDirectional(final double khi, final double gamma) {
054            this.khi   = khi;
055            this.gamma = gamma;
056        }
057    
058        /** {@inheritDoc} */
059        @Override
060        protected void iterateSimplex(final Comparator<RealPointValuePair> comparator)
061            throws FunctionEvaluationException, OptimizationException, IllegalArgumentException {
062    
063            while (true) {
064    
065                incrementIterationsCounter();
066    
067                // save the original vertex
068                final RealPointValuePair[] original = simplex;
069                final RealPointValuePair best = original[0];
070    
071                // perform a reflection step
072                final RealPointValuePair reflected = evaluateNewSimplex(original, 1.0, comparator);
073                if (comparator.compare(reflected, best) < 0) {
074    
075                    // compute the expanded simplex
076                    final RealPointValuePair[] reflectedSimplex = simplex;
077                    final RealPointValuePair expanded = evaluateNewSimplex(original, khi, comparator);
078                    if (comparator.compare(reflected, expanded) <= 0) {
079                        // accept the reflected simplex
080                        simplex = reflectedSimplex;
081                    }
082    
083                    return;
084    
085                }
086    
087                // compute the contracted simplex
088                final RealPointValuePair contracted = evaluateNewSimplex(original, gamma, comparator);
089                if (comparator.compare(contracted, best) < 0) {
090                    // accept the contracted simplex
091                    return;
092                }
093    
094            }
095    
096        }
097    
098        /** Compute and evaluate a new simplex.
099         * @param original original simplex (to be preserved)
100         * @param coeff linear coefficient
101         * @param comparator comparator to use to sort simplex vertices from best to poorest
102         * @return best point in the transformed simplex
103         * @exception FunctionEvaluationException if the function cannot be evaluated at
104         * some point
105         * @exception OptimizationException if the maximal number of evaluations is exceeded
106         */
107        private RealPointValuePair evaluateNewSimplex(final RealPointValuePair[] original,
108                                                  final double coeff,
109                                                  final Comparator<RealPointValuePair> comparator)
110            throws FunctionEvaluationException, OptimizationException {
111    
112            final double[] xSmallest = original[0].getPointRef();
113            final int n = xSmallest.length;
114    
115            // create the linearly transformed simplex
116            simplex = new RealPointValuePair[n + 1];
117            simplex[0] = original[0];
118            for (int i = 1; i <= n; ++i) {
119                final double[] xOriginal    = original[i].getPointRef();
120                final double[] xTransformed = new double[n];
121                for (int j = 0; j < n; ++j) {
122                    xTransformed[j] = xSmallest[j] + coeff * (xSmallest[j] - xOriginal[j]);
123                }
124                simplex[i] = new RealPointValuePair(xTransformed, Double.NaN, false);
125            }
126    
127            // evaluate it
128            evaluateSimplex(comparator);
129            return simplex[0];
130    
131        }
132    
133    }