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