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