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 }