1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 package org.apache.commons.math3.optim.nonlinear.scalar.noderiv; 18 19 import java.util.Comparator; 20 import org.apache.commons.math3.analysis.MultivariateFunction; 21 import org.apache.commons.math3.exception.NullArgumentException; 22 import org.apache.commons.math3.exception.MathUnsupportedOperationException; 23 import org.apache.commons.math3.exception.util.LocalizedFormats; 24 import org.apache.commons.math3.optim.nonlinear.scalar.GoalType; 25 import org.apache.commons.math3.optim.ConvergenceChecker; 26 import org.apache.commons.math3.optim.PointValuePair; 27 import org.apache.commons.math3.optim.SimpleValueChecker; 28 import org.apache.commons.math3.optim.OptimizationData; 29 import org.apache.commons.math3.optim.nonlinear.scalar.MultivariateOptimizer; 30 31 /** 32 * This class implements simplex-based direct search optimization. 33 * 34 * <p> 35 * Direct search methods only use objective function values, they do 36 * not need derivatives and don't either try to compute approximation 37 * of the derivatives. According to a 1996 paper by Margaret H. Wright 38 * (<a href="http://cm.bell-labs.com/cm/cs/doc/96/4-02.ps.gz">Direct 39 * Search Methods: Once Scorned, Now Respectable</a>), they are used 40 * when either the computation of the derivative is impossible (noisy 41 * functions, unpredictable discontinuities) or difficult (complexity, 42 * computation cost). In the first cases, rather than an optimum, a 43 * <em>not too bad</em> point is desired. In the latter cases, an 44 * optimum is desired but cannot be reasonably found. In all cases 45 * direct search methods can be useful. 46 * </p> 47 * <p> 48 * Simplex-based direct search methods are based on comparison of 49 * the objective function values at the vertices of a simplex (which is a 50 * set of n+1 points in dimension n) that is updated by the algorithms 51 * steps. 52 * <p> 53 * <p> 54 * The simplex update procedure ({@link NelderMeadSimplex} or 55 * {@link MultiDirectionalSimplex}) must be passed to the 56 * {@code optimize} method. 57 * </p> 58 * <p> 59 * Each call to {@code optimize} will re-use the start configuration of 60 * the current simplex and move it such that its first vertex is at the 61 * provided start point of the optimization. 62 * If the {@code optimize} method is called to solve a different problem 63 * and the number of parameters change, the simplex must be re-initialized 64 * to one with the appropriate dimensions. 65 * </p> 66 * <p> 67 * Convergence is checked by providing the <em>worst</em> points of 68 * previous and current simplex to the convergence checker, not the best 69 * ones. 70 * </p> 71 * <p> 72 * This simplex optimizer implementation does not directly support constrained 73 * optimization with simple bounds; so, for such optimizations, either a more 74 * dedicated algorithm must be used like 75 * {@link CMAESOptimizer} or {@link BOBYQAOptimizer}, or the objective 76 * function must be wrapped in an adapter like 77 * {@link org.apache.commons.math3.optim.nonlinear.scalar.MultivariateFunctionMappingAdapter 78 * MultivariateFunctionMappingAdapter} or 79 * {@link org.apache.commons.math3.optim.nonlinear.scalar.MultivariateFunctionPenaltyAdapter 80 * MultivariateFunctionPenaltyAdapter}. 81 * <br/> 82 * The call to {@link #optimize(OptimizationData[]) optimize} will throw 83 * {@link MathUnsupportedOperationException} if bounds are passed to it. 84 * </p> 85 * 86 * @since 3.0 87 */ 88 public class SimplexOptimizer extends MultivariateOptimizer { 89 /** Simplex update rule. */ 90 private AbstractSimplex simplex; 91 92 /** 93 * @param checker Convergence checker. 94 */ 95 public SimplexOptimizer(ConvergenceChecker<PointValuePair> checker) { 96 super(checker); 97 } 98 99 /** 100 * @param rel Relative threshold. 101 * @param abs Absolute threshold. 102 */ 103 public SimplexOptimizer(double rel, double abs) { 104 this(new SimpleValueChecker(rel, abs)); 105 } 106 107 /** 108 * {@inheritDoc} 109 * 110 * @param optData Optimization data. In addition to those documented in 111 * {@link MultivariateOptimizer#parseOptimizationData(OptimizationData[]) 112 * MultivariateOptimizer}, this method will register the following data: 113 * <ul> 114 * <li>{@link AbstractSimplex}</li> 115 * </ul> 116 * @return {@inheritDoc} 117 */ 118 @Override 119 public PointValuePair optimize(OptimizationData... optData) { 120 // Set up base class and perform computation. 121 return super.optimize(optData); 122 } 123 124 /** {@inheritDoc} */ 125 @Override 126 protected PointValuePair doOptimize() { 127 checkParameters(); 128 129 // Indirect call to "computeObjectiveValue" in order to update the 130 // evaluations counter. 131 final MultivariateFunction evalFunc 132 = new MultivariateFunction() { 133 public double value(double[] point) { 134 return computeObjectiveValue(point); 135 } 136 }; 137 138 final boolean isMinim = getGoalType() == GoalType.MINIMIZE; 139 final Comparator<PointValuePair> comparator 140 = new Comparator<PointValuePair>() { 141 public int compare(final PointValuePair o1, 142 final PointValuePair o2) { 143 final double v1 = o1.getValue(); 144 final double v2 = o2.getValue(); 145 return isMinim ? Double.compare(v1, v2) : Double.compare(v2, v1); 146 } 147 }; 148 149 // Initialize search. 150 simplex.build(getStartPoint()); 151 simplex.evaluate(evalFunc, comparator); 152 153 PointValuePair[] previous = null; 154 int iteration = 0; 155 final ConvergenceChecker<PointValuePair> checker = getConvergenceChecker(); 156 while (true) { 157 if (getIterations() > 0) { 158 boolean converged = true; 159 for (int i = 0; i < simplex.getSize(); i++) { 160 PointValuePair prev = previous[i]; 161 converged = converged && 162 checker.converged(iteration, prev, simplex.getPoint(i)); 163 } 164 if (converged) { 165 // We have found an optimum. 166 return simplex.getPoint(0); 167 } 168 } 169 170 // We still need to search. 171 previous = simplex.getPoints(); 172 simplex.iterate(evalFunc, comparator); 173 174 incrementIterationCount(); 175 } 176 } 177 178 /** 179 * Scans the list of (required and optional) optimization data that 180 * characterize the problem. 181 * 182 * @param optData Optimization data. 183 * The following data will be looked for: 184 * <ul> 185 * <li>{@link AbstractSimplex}</li> 186 * </ul> 187 */ 188 @Override 189 protected void parseOptimizationData(OptimizationData... optData) { 190 // Allow base class to register its own data. 191 super.parseOptimizationData(optData); 192 193 // The existing values (as set by the previous call) are reused if 194 // not provided in the argument list. 195 for (OptimizationData data : optData) { 196 if (data instanceof AbstractSimplex) { 197 simplex = (AbstractSimplex) data; 198 // If more data must be parsed, this statement _must_ be 199 // changed to "continue". 200 break; 201 } 202 } 203 } 204 205 /** 206 * @throws MathUnsupportedOperationException if bounds were passed to the 207 * {@link #optimize(OptimizationData[]) optimize} method. 208 * @throws NullArgumentException if no initial simplex was passed to the 209 * {@link #optimize(OptimizationData[]) optimize} method. 210 */ 211 private void checkParameters() { 212 if (simplex == null) { 213 throw new NullArgumentException(); 214 } 215 if (getLowerBound() != null || 216 getUpperBound() != null) { 217 throw new MathUnsupportedOperationException(LocalizedFormats.CONSTRAINT); 218 } 219 } 220 }