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.exception.NullArgumentException;
024 import org.apache.commons.math3.optimization.GoalType;
025 import org.apache.commons.math3.optimization.ConvergenceChecker;
026 import org.apache.commons.math3.optimization.PointValuePair;
027 import org.apache.commons.math3.optimization.SimpleValueChecker;
028 import org.apache.commons.math3.optimization.MultivariateOptimizer;
029 import org.apache.commons.math3.optimization.OptimizationData;
030
031 /**
032 * This class implements simplex-based direct search optimization.
033 *
034 * <p>
035 * Direct search methods only use objective function values, they do
036 * not need derivatives and don't either try to compute approximation
037 * of the derivatives. According to a 1996 paper by Margaret H. Wright
038 * (<a href="http://cm.bell-labs.com/cm/cs/doc/96/4-02.ps.gz">Direct
039 * Search Methods: Once Scorned, Now Respectable</a>), they are used
040 * when either the computation of the derivative is impossible (noisy
041 * functions, unpredictable discontinuities) or difficult (complexity,
042 * computation cost). In the first cases, rather than an optimum, a
043 * <em>not too bad</em> point is desired. In the latter cases, an
044 * optimum is desired but cannot be reasonably found. In all cases
045 * direct search methods can be useful.
046 * </p>
047 * <p>
048 * Simplex-based direct search methods are based on comparison of
049 * the objective function values at the vertices of a simplex (which is a
050 * set of n+1 points in dimension n) that is updated by the algorithms
051 * steps.
052 * <p>
053 * <p>
054 * The {@link #setSimplex(AbstractSimplex) setSimplex} method <em>must</em>
055 * be called prior to calling the {@code optimize} method.
056 * </p>
057 * <p>
058 * Each call to {@link #optimize(int,MultivariateFunction,GoalType,double[])
059 * optimize} will re-use the start configuration of the current simplex and
060 * move it such that its first vertex is at the provided start point of the
061 * optimization. If the {@code optimize} method is called to solve a different
062 * problem and the number of parameters change, the simplex must be
063 * re-initialized to one with the appropriate dimensions.
064 * </p>
065 * <p>
066 * Convergence is checked by providing the <em>worst</em> points of
067 * previous and current simplex to the convergence checker, not the best
068 * ones.
069 * </p>
070 * <p>
071 * This simplex optimizer implementation does not directly support constrained
072 * optimization with simple bounds, so for such optimizations, either a more
073 * dedicated method must be used like {@link CMAESOptimizer} or {@link
074 * BOBYQAOptimizer}, or the optimized method must be wrapped in an adapter like
075 * {@link MultivariateFunctionMappingAdapter} or {@link
076 * MultivariateFunctionPenaltyAdapter}.
077 * </p>
078 *
079 * @see AbstractSimplex
080 * @see MultivariateFunctionMappingAdapter
081 * @see MultivariateFunctionPenaltyAdapter
082 * @see CMAESOptimizer
083 * @see BOBYQAOptimizer
084 * @version $Id: SimplexOptimizer.java 1422230 2012-12-15 12:11:13Z erans $
085 * @deprecated As of 3.1 (to be removed in 4.0).
086 * @since 3.0
087 */
088 @Deprecated
089 public class SimplexOptimizer
090 extends BaseAbstractMultivariateOptimizer<MultivariateFunction>
091 implements MultivariateOptimizer {
092 /** Simplex. */
093 private AbstractSimplex simplex;
094
095 /**
096 * Constructor using a default {@link SimpleValueChecker convergence
097 * checker}.
098 * @deprecated See {@link SimpleValueChecker#SimpleValueChecker()}
099 */
100 @Deprecated
101 public SimplexOptimizer() {
102 this(new SimpleValueChecker());
103 }
104
105 /**
106 * @param checker Convergence checker.
107 */
108 public SimplexOptimizer(ConvergenceChecker<PointValuePair> checker) {
109 super(checker);
110 }
111
112 /**
113 * @param rel Relative threshold.
114 * @param abs Absolute threshold.
115 */
116 public SimplexOptimizer(double rel, double abs) {
117 this(new SimpleValueChecker(rel, abs));
118 }
119
120 /**
121 * Set the simplex algorithm.
122 *
123 * @param simplex Simplex.
124 * @deprecated As of 3.1. The initial simplex can now be passed as an
125 * argument of the {@link #optimize(int,MultivariateFunction,GoalType,OptimizationData[])}
126 * method.
127 */
128 @Deprecated
129 public void setSimplex(AbstractSimplex simplex) {
130 parseOptimizationData(simplex);
131 }
132
133 /**
134 * Optimize an objective function.
135 *
136 * @param maxEval Allowed number of evaluations of the objective function.
137 * @param f Objective function.
138 * @param goalType Optimization type.
139 * @param optData Optimization data. The following data will be looked for:
140 * <ul>
141 * <li>{@link org.apache.commons.math3.optimization.InitialGuess InitialGuess}</li>
142 * <li>{@link AbstractSimplex}</li>
143 * </ul>
144 * @return the point/value pair giving the optimal value for objective
145 * function.
146 */
147 @Override
148 protected PointValuePair optimizeInternal(int maxEval, MultivariateFunction f,
149 GoalType goalType,
150 OptimizationData... optData) {
151 // Scan "optData" for the input specific to this optimizer.
152 parseOptimizationData(optData);
153
154 // The parent's method will retrieve the common parameters from
155 // "optData" and call "doOptimize".
156 return super.optimizeInternal(maxEval, f, goalType, optData);
157 }
158
159 /**
160 * Scans the list of (required and optional) optimization data that
161 * characterize the problem.
162 *
163 * @param optData Optimization data. The following data will be looked for:
164 * <ul>
165 * <li>{@link AbstractSimplex}</li>
166 * </ul>
167 */
168 private void parseOptimizationData(OptimizationData... optData) {
169 // The existing values (as set by the previous call) are reused if
170 // not provided in the argument list.
171 for (OptimizationData data : optData) {
172 if (data instanceof AbstractSimplex) {
173 simplex = (AbstractSimplex) data;
174 continue;
175 }
176 }
177 }
178
179 /** {@inheritDoc} */
180 @Override
181 protected PointValuePair doOptimize() {
182 if (simplex == null) {
183 throw new NullArgumentException();
184 }
185
186 // Indirect call to "computeObjectiveValue" in order to update the
187 // evaluations counter.
188 final MultivariateFunction evalFunc
189 = new MultivariateFunction() {
190 public double value(double[] point) {
191 return computeObjectiveValue(point);
192 }
193 };
194
195 final boolean isMinim = getGoalType() == GoalType.MINIMIZE;
196 final Comparator<PointValuePair> comparator
197 = new Comparator<PointValuePair>() {
198 public int compare(final PointValuePair o1,
199 final PointValuePair o2) {
200 final double v1 = o1.getValue();
201 final double v2 = o2.getValue();
202 return isMinim ? Double.compare(v1, v2) : Double.compare(v2, v1);
203 }
204 };
205
206 // Initialize search.
207 simplex.build(getStartPoint());
208 simplex.evaluate(evalFunc, comparator);
209
210 PointValuePair[] previous = null;
211 int iteration = 0;
212 final ConvergenceChecker<PointValuePair> checker = getConvergenceChecker();
213 while (true) {
214 if (iteration > 0) {
215 boolean converged = true;
216 for (int i = 0; i < simplex.getSize(); i++) {
217 PointValuePair prev = previous[i];
218 converged = converged &&
219 checker.converged(iteration, prev, simplex.getPoint(i));
220 }
221 if (converged) {
222 // We have found an optimum.
223 return simplex.getPoint(0);
224 }
225 }
226
227 // We still need to search.
228 previous = simplex.getPoints();
229 simplex.iterate(evalFunc, comparator);
230 ++iteration;
231 }
232 }
233 }