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.RealConvergenceChecker;
025 import org.apache.commons.math.optimization.RealPointValuePair;
026
027 /**
028 * This class implements the multi-directional direct search method.
029 *
030 * @version $Revision: 811685 $ $Date: 2009-09-05 13:36:48 -0400 (Sat, 05 Sep 2009) $
031 * @see NelderMead
032 * @since 1.2
033 */
034 public class MultiDirectional extends DirectSearchOptimizer {
035
036 /** Expansion coefficient. */
037 private final double khi;
038
039 /** Contraction coefficient. */
040 private final double gamma;
041
042 /** Build a multi-directional optimizer with default coefficients.
043 * <p>The default values are 2.0 for khi and 0.5 for gamma.</p>
044 */
045 public MultiDirectional() {
046 this.khi = 2.0;
047 this.gamma = 0.5;
048 }
049
050 /** Build a multi-directional optimizer with specified coefficients.
051 * @param khi expansion coefficient
052 * @param gamma contraction coefficient
053 */
054 public MultiDirectional(final double khi, final double gamma) {
055 this.khi = khi;
056 this.gamma = gamma;
057 }
058
059 /** {@inheritDoc} */
060 @Override
061 protected void iterateSimplex(final Comparator<RealPointValuePair> comparator)
062 throws FunctionEvaluationException, OptimizationException, IllegalArgumentException {
063
064 final RealConvergenceChecker checker = getConvergenceChecker();
065 while (true) {
066
067 incrementIterationsCounter();
068
069 // save the original vertex
070 final RealPointValuePair[] original = simplex;
071 final RealPointValuePair best = original[0];
072
073 // perform a reflection step
074 final RealPointValuePair reflected = evaluateNewSimplex(original, 1.0, comparator);
075 if (comparator.compare(reflected, best) < 0) {
076
077 // compute the expanded simplex
078 final RealPointValuePair[] reflectedSimplex = simplex;
079 final RealPointValuePair expanded = evaluateNewSimplex(original, khi, comparator);
080 if (comparator.compare(reflected, expanded) <= 0) {
081 // accept the reflected simplex
082 simplex = reflectedSimplex;
083 }
084
085 return;
086
087 }
088
089 // compute the contracted simplex
090 final RealPointValuePair contracted = evaluateNewSimplex(original, gamma, comparator);
091 if (comparator.compare(contracted, best) < 0) {
092 // accept the contracted simplex
093 return;
094 }
095
096 // check convergence
097 final int iter = getIterations();
098 boolean converged = true;
099 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
116 * some point
117 * @exception OptimizationException if the maximal number of evaluations is exceeded
118 */
119 private RealPointValuePair evaluateNewSimplex(final RealPointValuePair[] original,
120 final double coeff,
121 final Comparator<RealPointValuePair> comparator)
122 throws FunctionEvaluationException, OptimizationException {
123
124 final double[] xSmallest = original[0].getPointRef();
125 final int n = xSmallest.length;
126
127 // create the linearly transformed simplex
128 simplex = new RealPointValuePair[n + 1];
129 simplex[0] = original[0];
130 for (int i = 1; i <= n; ++i) {
131 final double[] xOriginal = original[i].getPointRef();
132 final double[] xTransformed = new double[n];
133 for (int j = 0; j < n; ++j) {
134 xTransformed[j] = xSmallest[j] + coeff * (xSmallest[j] - xOriginal[j]);
135 }
136 simplex[i] = new RealPointValuePair(xTransformed, Double.NaN, false);
137 }
138
139 // evaluate it
140 evaluateSimplex(comparator);
141 return simplex[0];
142
143 }
144
145 }