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.RealPointValuePair;
025
026 /**
027 * This class implements the multi-directional direct search method.
028 *
029 * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
030 * @see NelderMead
031 * @since 1.2
032 */
033 public class MultiDirectional extends DirectSearchOptimizer {
034
035 /** Expansion coefficient. */
036 private final double khi;
037
038 /** Contraction coefficient. */
039 private final double gamma;
040
041 /** Build a multi-directional optimizer with default coefficients.
042 * <p>The default values are 2.0 for khi and 0.5 for gamma.</p>
043 */
044 public MultiDirectional() {
045 this.khi = 2.0;
046 this.gamma = 0.5;
047 }
048
049 /** Build a multi-directional optimizer with specified coefficients.
050 * @param khi expansion coefficient
051 * @param gamma contraction coefficient
052 */
053 public MultiDirectional(final double khi, final double gamma) {
054 this.khi = khi;
055 this.gamma = gamma;
056 }
057
058 /** {@inheritDoc} */
059 @Override
060 protected void iterateSimplex(final Comparator<RealPointValuePair> comparator)
061 throws FunctionEvaluationException, OptimizationException, IllegalArgumentException {
062
063 while (true) {
064
065 incrementIterationsCounter();
066
067 // save the original vertex
068 final RealPointValuePair[] original = simplex;
069 final RealPointValuePair best = original[0];
070
071 // perform a reflection step
072 final RealPointValuePair reflected = evaluateNewSimplex(original, 1.0, comparator);
073 if (comparator.compare(reflected, best) < 0) {
074
075 // compute the expanded simplex
076 final RealPointValuePair[] reflectedSimplex = simplex;
077 final RealPointValuePair expanded = evaluateNewSimplex(original, khi, comparator);
078 if (comparator.compare(reflected, expanded) <= 0) {
079 // accept the reflected simplex
080 simplex = reflectedSimplex;
081 }
082
083 return;
084
085 }
086
087 // compute the contracted simplex
088 final RealPointValuePair contracted = evaluateNewSimplex(original, gamma, comparator);
089 if (comparator.compare(contracted, best) < 0) {
090 // accept the contracted simplex
091 return;
092 }
093
094 }
095
096 }
097
098 /** Compute and evaluate a new simplex.
099 * @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 }