Home | History | Annotate | Download | only in direct 
      1 /*
      2  * Licensed to the Apache Software Foundation (ASF) under one or more
      3  * contributor license agreements.  See the NOTICE file distributed with
      4  * this work for additional information regarding copyright ownership.
      5  * The ASF licenses this file to You under the Apache License, Version 2.0
      6  * (the "License"); you may not use this file except in compliance with
      7  * the License.  You may obtain a copy of the License at
      8  *
      9  *      http://www.apache.org/licenses/LICENSE-2.0
     10  *
     11  * Unless required by applicable law or agreed to in writing, software
     12  * distributed under the License is distributed on an "AS IS" BASIS,
     13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     14  * See the License for the specific language governing permissions and
     15  * limitations under the License.
     16  */
     17 
     18 package org.apache.commons.math.optimization.direct;
     19 
     20 import java.util.Comparator;
     21 
     22 import org.apache.commons.math.FunctionEvaluationException;
     23 import org.apache.commons.math.optimization.OptimizationException;
     24 import org.apache.commons.math.optimization.RealConvergenceChecker;
     25 import org.apache.commons.math.optimization.RealPointValuePair;
     26 
     27 /**
     28  * This class implements the multi-directional direct search method.
     29  *
     30  * @version $Revision: 1070725 $ $Date: 2011-02-15 02:31:12 +0100 (mar. 15 fvr. 2011) $
     31  * @see NelderMead
     32  * @since 1.2
     33  */
     34 public class MultiDirectional extends DirectSearchOptimizer {
     35 
     36     /** Expansion coefficient. */
     37     private final double khi;
     38 
     39     /** Contraction coefficient. */
     40     private final double gamma;
     41 
     42     /** Build a multi-directional optimizer with default coefficients.
     43      * <p>The default values are 2.0 for khi and 0.5 for gamma.</p>
     44      */
     45     public MultiDirectional() {
     46         this.khi   = 2.0;
     47         this.gamma = 0.5;
     48     }
     49 
     50     /** Build a multi-directional optimizer with specified coefficients.
     51      * @param khi expansion coefficient
     52      * @param gamma contraction coefficient
     53      */
     54     public MultiDirectional(final double khi, final double gamma) {
     55         this.khi   = khi;
     56         this.gamma = gamma;
     57     }
     58 
     59     /** {@inheritDoc} */
     60     @Override
     61     protected void iterateSimplex(final Comparator<RealPointValuePair> comparator)
     62         throws FunctionEvaluationException, OptimizationException, IllegalArgumentException {
     63 
     64         final RealConvergenceChecker checker = getConvergenceChecker();
     65         while (true) {
     66 
     67             incrementIterationsCounter();
     68 
     69             // save the original vertex
     70             final RealPointValuePair[] original = simplex;
     71             final RealPointValuePair best = original[0];
     72 
     73             // perform a reflection step
     74             final RealPointValuePair reflected = evaluateNewSimplex(original, 1.0, comparator);
     75             if (comparator.compare(reflected, best) < 0) {
     76 
     77                 // compute the expanded simplex
     78                 final RealPointValuePair[] reflectedSimplex = simplex;
     79                 final RealPointValuePair expanded = evaluateNewSimplex(original, khi, comparator);
     80                 if (comparator.compare(reflected, expanded) <= 0) {
     81                     // accept the reflected simplex
     82                     simplex = reflectedSimplex;
     83                 }
     84 
     85                 return;
     86 
     87             }
     88 
     89             // compute the contracted simplex
     90             final RealPointValuePair contracted = evaluateNewSimplex(original, gamma, comparator);
     91             if (comparator.compare(contracted, best) < 0) {
     92                 // accept the contracted simplex
     93                 return;
     94             }
     95 
     96             // check convergence
     97             final int iter = getIterations();
     98             boolean converged = true;
     99             for (int i = 0; i < simplex.length; ++i) {
    100                 converged &= checker.converged(iter, original[i], simplex[i]);
    101             }
    102             if (converged) {
    103                 return;
    104             }
    105 
    106         }
    107 
    108     }
    109 
    110     /** Compute and evaluate a new simplex.
    111      * @param original original simplex (to be preserved)
    112      * @param coeff linear coefficient
    113      * @param comparator comparator to use to sort simplex vertices from best to poorest
    114      * @return best point in the transformed simplex
    115      * @exception FunctionEvaluationException if the function cannot be evaluated at some point
    116      * @exception OptimizationException if the maximal number of evaluations is exceeded
    117      */
    118     private RealPointValuePair evaluateNewSimplex(final RealPointValuePair[] original,
    119                                               final double coeff,
    120                                               final Comparator<RealPointValuePair> comparator)
    121         throws FunctionEvaluationException, OptimizationException {
    122 
    123         final double[] xSmallest = original[0].getPointRef();
    124         final int n = xSmallest.length;
    125 
    126         // create the linearly transformed simplex
    127         simplex = new RealPointValuePair[n + 1];
    128         simplex[0] = original[0];
    129         for (int i = 1; i <= n; ++i) {
    130             final double[] xOriginal    = original[i].getPointRef();
    131             final double[] xTransformed = new double[n];
    132             for (int j = 0; j < n; ++j) {
    133                 xTransformed[j] = xSmallest[j] + coeff * (xSmallest[j] - xOriginal[j]);
    134             }
    135             simplex[i] = new RealPointValuePair(xTransformed, Double.NaN, false);
    136         }
    137 
    138         // evaluate it
    139         evaluateSimplex(comparator);
    140         return simplex[0];
    141 
    142     }
    143 
    144 }
    145