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 }