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 }