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 package org.apache.commons.math3.optim.nonlinear.scalar.noderiv; 018 019 import java.util.Comparator; 020 021 import org.apache.commons.math3.analysis.MultivariateFunction; 022 import org.apache.commons.math3.optim.PointValuePair; 023 024 /** 025 * This class implements the multi-directional direct search method. 026 * 027 * @version $Id: MultiDirectionalSimplex.java 1364392 2012-07-22 18:27:12Z tn $ 028 * @since 3.0 029 */ 030 public class MultiDirectionalSimplex extends AbstractSimplex { 031 /** Default value for {@link #khi}: {@value}. */ 032 private static final double DEFAULT_KHI = 2; 033 /** Default value for {@link #gamma}: {@value}. */ 034 private static final double DEFAULT_GAMMA = 0.5; 035 /** Expansion coefficient. */ 036 private final double khi; 037 /** Contraction coefficient. */ 038 private final double gamma; 039 040 /** 041 * Build a multi-directional simplex with default coefficients. 042 * The default values are 2.0 for khi and 0.5 for gamma. 043 * 044 * @param n Dimension of the simplex. 045 */ 046 public MultiDirectionalSimplex(final int n) { 047 this(n, 1d); 048 } 049 050 /** 051 * Build a multi-directional simplex with default coefficients. 052 * The default values are 2.0 for khi and 0.5 for gamma. 053 * 054 * @param n Dimension of the simplex. 055 * @param sideLength Length of the sides of the default (hypercube) 056 * simplex. See {@link AbstractSimplex#AbstractSimplex(int,double)}. 057 */ 058 public MultiDirectionalSimplex(final int n, double sideLength) { 059 this(n, sideLength, DEFAULT_KHI, DEFAULT_GAMMA); 060 } 061 062 /** 063 * Build a multi-directional simplex with specified coefficients. 064 * 065 * @param n Dimension of the simplex. See 066 * {@link AbstractSimplex#AbstractSimplex(int,double)}. 067 * @param khi Expansion coefficient. 068 * @param gamma Contraction coefficient. 069 */ 070 public MultiDirectionalSimplex(final int n, 071 final double khi, final double gamma) { 072 this(n, 1d, khi, gamma); 073 } 074 075 /** 076 * Build a multi-directional simplex with specified coefficients. 077 * 078 * @param n Dimension of the simplex. See 079 * {@link AbstractSimplex#AbstractSimplex(int,double)}. 080 * @param sideLength Length of the sides of the default (hypercube) 081 * simplex. See {@link AbstractSimplex#AbstractSimplex(int,double)}. 082 * @param khi Expansion coefficient. 083 * @param gamma Contraction coefficient. 084 */ 085 public MultiDirectionalSimplex(final int n, double sideLength, 086 final double khi, final double gamma) { 087 super(n, sideLength); 088 089 this.khi = khi; 090 this.gamma = gamma; 091 } 092 093 /** 094 * Build a multi-directional simplex with default coefficients. 095 * The default values are 2.0 for khi and 0.5 for gamma. 096 * 097 * @param steps Steps along the canonical axes representing box edges. 098 * They may be negative but not zero. See 099 */ 100 public MultiDirectionalSimplex(final double[] steps) { 101 this(steps, DEFAULT_KHI, DEFAULT_GAMMA); 102 } 103 104 /** 105 * Build a multi-directional simplex with specified coefficients. 106 * 107 * @param steps Steps along the canonical axes representing box edges. 108 * They may be negative but not zero. See 109 * {@link AbstractSimplex#AbstractSimplex(double[])}. 110 * @param khi Expansion coefficient. 111 * @param gamma Contraction coefficient. 112 */ 113 public MultiDirectionalSimplex(final double[] steps, 114 final double khi, final double gamma) { 115 super(steps); 116 117 this.khi = khi; 118 this.gamma = gamma; 119 } 120 121 /** 122 * Build a multi-directional simplex with default coefficients. 123 * The default values are 2.0 for khi and 0.5 for gamma. 124 * 125 * @param referenceSimplex Reference simplex. See 126 * {@link AbstractSimplex#AbstractSimplex(double[][])}. 127 */ 128 public MultiDirectionalSimplex(final double[][] referenceSimplex) { 129 this(referenceSimplex, DEFAULT_KHI, DEFAULT_GAMMA); 130 } 131 132 /** 133 * Build a multi-directional simplex with specified coefficients. 134 * 135 * @param referenceSimplex Reference simplex. See 136 * {@link AbstractSimplex#AbstractSimplex(double[][])}. 137 * @param khi Expansion coefficient. 138 * @param gamma Contraction coefficient. 139 * @throws org.apache.commons.math3.exception.NotStrictlyPositiveException 140 * if the reference simplex does not contain at least one point. 141 * @throws org.apache.commons.math3.exception.DimensionMismatchException 142 * if there is a dimension mismatch in the reference simplex. 143 */ 144 public MultiDirectionalSimplex(final double[][] referenceSimplex, 145 final double khi, final double gamma) { 146 super(referenceSimplex); 147 148 this.khi = khi; 149 this.gamma = gamma; 150 } 151 152 /** {@inheritDoc} */ 153 @Override 154 public void iterate(final MultivariateFunction evaluationFunction, 155 final Comparator<PointValuePair> comparator) { 156 // Save the original simplex. 157 final PointValuePair[] original = getPoints(); 158 final PointValuePair best = original[0]; 159 160 // Perform a reflection step. 161 final PointValuePair reflected = evaluateNewSimplex(evaluationFunction, 162 original, 1, comparator); 163 if (comparator.compare(reflected, best) < 0) { 164 // Compute the expanded simplex. 165 final PointValuePair[] reflectedSimplex = getPoints(); 166 final PointValuePair expanded = evaluateNewSimplex(evaluationFunction, 167 original, khi, comparator); 168 if (comparator.compare(reflected, expanded) <= 0) { 169 // Keep the reflected simplex. 170 setPoints(reflectedSimplex); 171 } 172 // Keep the expanded simplex. 173 return; 174 } 175 176 // Compute the contracted simplex. 177 evaluateNewSimplex(evaluationFunction, original, gamma, comparator); 178 179 } 180 181 /** 182 * Compute and evaluate a new simplex. 183 * 184 * @param evaluationFunction Evaluation function. 185 * @param original Original simplex (to be preserved). 186 * @param coeff Linear coefficient. 187 * @param comparator Comparator to use to sort simplex vertices from best 188 * to poorest. 189 * @return the best point in the transformed simplex. 190 * @throws org.apache.commons.math3.exception.TooManyEvaluationsException 191 * if the maximal number of evaluations is exceeded. 192 */ 193 private PointValuePair evaluateNewSimplex(final MultivariateFunction evaluationFunction, 194 final PointValuePair[] original, 195 final double coeff, 196 final Comparator<PointValuePair> comparator) { 197 final double[] xSmallest = original[0].getPointRef(); 198 // Perform a linear transformation on all the simplex points, 199 // except the first one. 200 setPoint(0, original[0]); 201 final int dim = getDimension(); 202 for (int i = 1; i < getSize(); i++) { 203 final double[] xOriginal = original[i].getPointRef(); 204 final double[] xTransformed = new double[dim]; 205 for (int j = 0; j < dim; j++) { 206 xTransformed[j] = xSmallest[j] + coeff * (xSmallest[j] - xOriginal[j]); 207 } 208 setPoint(i, new PointValuePair(xTransformed, Double.NaN, false)); 209 } 210 211 // Evaluate the simplex. 212 evaluate(evaluationFunction, comparator); 213 214 return getPoint(0); 215 } 216 }