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 */ 017package org.apache.commons.math3.optim.nonlinear.scalar.noderiv; 018 019import java.util.Comparator; 020import org.apache.commons.math3.analysis.MultivariateFunction; 021import org.apache.commons.math3.exception.NullArgumentException; 022import org.apache.commons.math3.exception.MathUnsupportedOperationException; 023import org.apache.commons.math3.exception.util.LocalizedFormats; 024import org.apache.commons.math3.optim.nonlinear.scalar.GoalType; 025import org.apache.commons.math3.optim.ConvergenceChecker; 026import org.apache.commons.math3.optim.PointValuePair; 027import org.apache.commons.math3.optim.SimpleValueChecker; 028import org.apache.commons.math3.optim.OptimizationData; 029import org.apache.commons.math3.optim.nonlinear.scalar.MultivariateOptimizer; 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 simplex update procedure ({@link NelderMeadSimplex} or 055 * {@link MultiDirectionalSimplex}) must be passed to the 056 * {@code optimize} method. 057 * </p> 058 * <p> 059 * Each call to {@code optimize} will re-use the start configuration of 060 * the current simplex and move it such that its first vertex is at the 061 * provided start point of the optimization. 062 * If the {@code optimize} method is called to solve a different problem 063 * and the number of parameters change, the simplex must be re-initialized 064 * to one with the appropriate dimensions. 065 * </p> 066 * <p> 067 * Convergence is checked by providing the <em>worst</em> points of 068 * previous and current simplex to the convergence checker, not the best 069 * ones. 070 * </p> 071 * <p> 072 * This simplex optimizer implementation does not directly support constrained 073 * optimization with simple bounds; so, for such optimizations, either a more 074 * dedicated algorithm must be used like 075 * {@link CMAESOptimizer} or {@link BOBYQAOptimizer}, or the objective 076 * function must be wrapped in an adapter like 077 * {@link org.apache.commons.math3.optim.nonlinear.scalar.MultivariateFunctionMappingAdapter 078 * MultivariateFunctionMappingAdapter} or 079 * {@link org.apache.commons.math3.optim.nonlinear.scalar.MultivariateFunctionPenaltyAdapter 080 * MultivariateFunctionPenaltyAdapter}. 081 * <br/> 082 * The call to {@link #optimize(OptimizationData[]) optimize} will throw 083 * {@link MathUnsupportedOperationException} if bounds are passed to it. 084 * </p> 085 * 086 * @since 3.0 087 */ 088public class SimplexOptimizer extends MultivariateOptimizer { 089 /** Simplex update rule. */ 090 private AbstractSimplex simplex; 091 092 /** 093 * @param checker Convergence checker. 094 */ 095 public SimplexOptimizer(ConvergenceChecker<PointValuePair> checker) { 096 super(checker); 097 } 098 099 /** 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 /** {@inheritDoc} */ 134 public double value(double[] point) { 135 return computeObjectiveValue(point); 136 } 137 }; 138 139 final boolean isMinim = getGoalType() == GoalType.MINIMIZE; 140 final Comparator<PointValuePair> comparator 141 = new Comparator<PointValuePair>() { 142 /** {@inheritDoc} */ 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 (getIterations() > 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 176 incrementIterationCount(); 177 } 178 } 179 180 /** 181 * Scans the list of (required and optional) optimization data that 182 * characterize the problem. 183 * 184 * @param optData Optimization data. 185 * The following data will be looked for: 186 * <ul> 187 * <li>{@link AbstractSimplex}</li> 188 * </ul> 189 */ 190 @Override 191 protected void parseOptimizationData(OptimizationData... optData) { 192 // Allow base class to register its own data. 193 super.parseOptimizationData(optData); 194 195 // The existing values (as set by the previous call) are reused if 196 // not provided in the argument list. 197 for (OptimizationData data : optData) { 198 if (data instanceof AbstractSimplex) { 199 simplex = (AbstractSimplex) data; 200 // If more data must be parsed, this statement _must_ be 201 // changed to "continue". 202 break; 203 } 204 } 205 } 206 207 /** 208 * @throws MathUnsupportedOperationException if bounds were passed to the 209 * {@link #optimize(OptimizationData[]) optimize} method. 210 * @throws NullArgumentException if no initial simplex was passed to the 211 * {@link #optimize(OptimizationData[]) optimize} method. 212 */ 213 private void checkParameters() { 214 if (simplex == null) { 215 throw new NullArgumentException(); 216 } 217 if (getLowerBound() != null || 218 getUpperBound() != null) { 219 throw new MathUnsupportedOperationException(LocalizedFormats.CONSTRAINT); 220 } 221 } 222}