View Javadoc

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.RealPointValuePair;
25  
26  /** 
27   * This class implements the multi-directional direct search method.
28   *
29   * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
30   * @see NelderMead
31   * @since 1.2
32   */
33  public class MultiDirectional extends DirectSearchOptimizer {
34  
35      /** Expansion coefficient. */
36      private final double khi;
37  
38      /** Contraction coefficient. */
39      private final double gamma;
40  
41      /** Build a multi-directional optimizer with default coefficients.
42       * <p>The default values are 2.0 for khi and 0.5 for gamma.</p>
43       */
44      public MultiDirectional() {
45          this.khi   = 2.0;
46          this.gamma = 0.5;
47      }
48  
49      /** Build a multi-directional optimizer with specified coefficients.
50       * @param khi expansion coefficient
51       * @param gamma contraction coefficient
52       */
53      public MultiDirectional(final double khi, final double gamma) {
54          this.khi   = khi;
55          this.gamma = gamma;
56      }
57  
58      /** {@inheritDoc} */
59      @Override
60      protected void iterateSimplex(final Comparator<RealPointValuePair> comparator)
61          throws FunctionEvaluationException, OptimizationException, IllegalArgumentException {
62  
63          while (true) {
64  
65              incrementIterationsCounter();
66  
67              // save the original vertex
68              final RealPointValuePair[] original = simplex;
69              final RealPointValuePair best = original[0];
70  
71              // perform a reflection step
72              final RealPointValuePair reflected = evaluateNewSimplex(original, 1.0, comparator);
73              if (comparator.compare(reflected, best) < 0) {
74  
75                  // compute the expanded simplex
76                  final RealPointValuePair[] reflectedSimplex = simplex;
77                  final RealPointValuePair expanded = evaluateNewSimplex(original, khi, comparator);
78                  if (comparator.compare(reflected, expanded) <= 0) {
79                      // accept the reflected simplex
80                      simplex = reflectedSimplex;
81                  }
82  
83                  return;
84  
85              }
86  
87              // compute the contracted simplex
88              final RealPointValuePair contracted = evaluateNewSimplex(original, gamma, comparator);
89              if (comparator.compare(contracted, best) < 0) {
90                  // accept the contracted simplex
91                  return;
92              }
93  
94          }
95  
96      }
97  
98      /** Compute and evaluate a new simplex.
99       * @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 }