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;
19  
20  /** 
21   * This class implements the multi-directional direct search method.
22   *
23   * @version $Revision: 620312 $ $Date: 2008-02-10 12:28:59 -0700 (Sun, 10 Feb 2008) $
24   * @see NelderMead
25   * @since 1.2
26   */
27  public class MultiDirectional
28    extends DirectSearchOptimizer {
29  
30    /** Build a multi-directional optimizer with default coefficients.
31     * <p>The default values are 2.0 for khi and 0.5 for gamma.</p>
32     */
33    public MultiDirectional() {
34      super();
35      this.khi   = 2.0;
36      this.gamma = 0.5;
37    }
38  
39    /** Build a multi-directional optimizer with specified coefficients.
40     * @param khi expansion coefficient
41     * @param gamma contraction coefficient
42     */
43    public MultiDirectional(double khi, double gamma) {
44      super();
45      this.khi   = khi;
46      this.gamma = gamma;
47    }
48  
49    /** Compute the next simplex of the algorithm.
50     * @exception CostException if the function cannot be evaluated at
51     * some point
52     */
53    protected void iterateSimplex()
54      throws CostException {
55  
56      while (true) {
57  
58        // save the original vertex
59        PointCostPair[] original = simplex;
60        double originalCost = original[0].getCost();
61  
62        // perform a reflection step
63        double reflectedCost = evaluateNewSimplex(original, 1.0);
64        if (reflectedCost < originalCost) {
65  
66          // compute the expanded simplex
67          PointCostPair[] reflected = simplex;
68          double expandedCost = evaluateNewSimplex(original, khi);
69          if (reflectedCost <= expandedCost) {
70            // accept the reflected simplex
71            simplex = reflected;
72          }
73  
74          return;
75  
76        }
77  
78        // compute the contracted simplex
79        double contractedCost = evaluateNewSimplex(original, gamma);
80        if (contractedCost < originalCost) {
81          // accept the contracted simplex
82          return;
83        }
84  
85      }
86  
87    }
88  
89    /** Compute and evaluate a new simplex.
90     * @param original original simplex (to be preserved)
91     * @param coeff linear coefficient
92     * @return smallest cost in the transformed simplex
93     * @exception CostException if the function cannot be evaluated at
94     * some point
95     */
96    private double evaluateNewSimplex(PointCostPair[] original, double coeff)
97      throws CostException {
98  
99      double[] xSmallest = original[0].getPoint();
100     int n = xSmallest.length;
101 
102     // create the linearly transformed simplex
103     simplex = new PointCostPair[n + 1];
104     simplex[0] = original[0];
105     for (int i = 1; i <= n; ++i) {
106       double[] xOriginal    = original[i].getPoint();
107       double[] xTransformed = new double[n];
108       for (int j = 0; j < n; ++j) {
109         xTransformed[j] = xSmallest[j] + coeff * (xSmallest[j] - xOriginal[j]);
110       }
111       simplex[i] = new PointCostPair(xTransformed, Double.NaN);
112     }
113 
114     // evaluate it
115     evaluateSimplex();
116     return simplex[0].getCost();
117 
118   }
119 
120   /** Expansion coefficient. */
121   private double khi;
122 
123   /** Contraction coefficient. */
124   private double gamma;
125 
126 }