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 }