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.analysis.solvers; 019 020 import org.apache.commons.math3.analysis.UnivariateFunction; 021 import org.apache.commons.math3.exception.MaxCountExceededException; 022 import org.apache.commons.math3.exception.NoBracketingException; 023 import org.apache.commons.math3.exception.TooManyEvaluationsException; 024 import org.apache.commons.math3.exception.NumberIsTooLargeException; 025 import org.apache.commons.math3.exception.NullArgumentException; 026 import org.apache.commons.math3.util.Incrementor; 027 import org.apache.commons.math3.util.MathUtils; 028 029 /** 030 * Provide a default implementation for several functions useful to generic 031 * solvers. 032 * 033 * @param <FUNC> Type of function to solve. 034 * 035 * @since 2.0 036 * @version $Id: BaseAbstractUnivariateSolver.java 1391927 2012-09-30 00:03:30Z erans $ 037 */ 038 public abstract class BaseAbstractUnivariateSolver<FUNC extends UnivariateFunction> 039 implements BaseUnivariateSolver<FUNC> { 040 /** Default relative accuracy. */ 041 private static final double DEFAULT_RELATIVE_ACCURACY = 1e-14; 042 /** Default function value accuracy. */ 043 private static final double DEFAULT_FUNCTION_VALUE_ACCURACY = 1e-15; 044 /** Function value accuracy. */ 045 private final double functionValueAccuracy; 046 /** Absolute accuracy. */ 047 private final double absoluteAccuracy; 048 /** Relative accuracy. */ 049 private final double relativeAccuracy; 050 /** Evaluations counter. */ 051 private final Incrementor evaluations = new Incrementor(); 052 /** Lower end of search interval. */ 053 private double searchMin; 054 /** Higher end of search interval. */ 055 private double searchMax; 056 /** Initial guess. */ 057 private double searchStart; 058 /** Function to solve. */ 059 private FUNC function; 060 061 /** 062 * Construct a solver with given absolute accuracy. 063 * 064 * @param absoluteAccuracy Maximum absolute error. 065 */ 066 protected BaseAbstractUnivariateSolver(final double absoluteAccuracy) { 067 this(DEFAULT_RELATIVE_ACCURACY, 068 absoluteAccuracy, 069 DEFAULT_FUNCTION_VALUE_ACCURACY); 070 } 071 072 /** 073 * Construct a solver with given accuracies. 074 * 075 * @param relativeAccuracy Maximum relative error. 076 * @param absoluteAccuracy Maximum absolute error. 077 */ 078 protected BaseAbstractUnivariateSolver(final double relativeAccuracy, 079 final double absoluteAccuracy) { 080 this(relativeAccuracy, 081 absoluteAccuracy, 082 DEFAULT_FUNCTION_VALUE_ACCURACY); 083 } 084 085 /** 086 * Construct a solver with given accuracies. 087 * 088 * @param relativeAccuracy Maximum relative error. 089 * @param absoluteAccuracy Maximum absolute error. 090 * @param functionValueAccuracy Maximum function value error. 091 */ 092 protected BaseAbstractUnivariateSolver(final double relativeAccuracy, 093 final double absoluteAccuracy, 094 final double functionValueAccuracy) { 095 this.absoluteAccuracy = absoluteAccuracy; 096 this.relativeAccuracy = relativeAccuracy; 097 this.functionValueAccuracy = functionValueAccuracy; 098 } 099 100 /** {@inheritDoc} */ 101 public int getMaxEvaluations() { 102 return evaluations.getMaximalCount(); 103 } 104 /** {@inheritDoc} */ 105 public int getEvaluations() { 106 return evaluations.getCount(); 107 } 108 /** 109 * @return the lower end of the search interval. 110 */ 111 public double getMin() { 112 return searchMin; 113 } 114 /** 115 * @return the higher end of the search interval. 116 */ 117 public double getMax() { 118 return searchMax; 119 } 120 /** 121 * @return the initial guess. 122 */ 123 public double getStartValue() { 124 return searchStart; 125 } 126 /** 127 * {@inheritDoc} 128 */ 129 public double getAbsoluteAccuracy() { 130 return absoluteAccuracy; 131 } 132 /** 133 * {@inheritDoc} 134 */ 135 public double getRelativeAccuracy() { 136 return relativeAccuracy; 137 } 138 /** 139 * {@inheritDoc} 140 */ 141 public double getFunctionValueAccuracy() { 142 return functionValueAccuracy; 143 } 144 145 /** 146 * Compute the objective function value. 147 * 148 * @param point Point at which the objective function must be evaluated. 149 * @return the objective function value at specified point. 150 * @throws TooManyEvaluationsException if the maximal number of evaluations 151 * is exceeded. 152 */ 153 protected double computeObjectiveValue(double point) 154 throws TooManyEvaluationsException { 155 incrementEvaluationCount(); 156 return function.value(point); 157 } 158 159 /** 160 * Prepare for computation. 161 * Subclasses must call this method if they override any of the 162 * {@code solve} methods. 163 * 164 * @param f Function to solve. 165 * @param min Lower bound for the interval. 166 * @param max Upper bound for the interval. 167 * @param startValue Start value to use. 168 * @param maxEval Maximum number of evaluations. 169 */ 170 protected void setup(int maxEval, 171 FUNC f, 172 double min, double max, 173 double startValue) { 174 // Checks. 175 MathUtils.checkNotNull(f); 176 177 // Reset. 178 searchMin = min; 179 searchMax = max; 180 searchStart = startValue; 181 function = f; 182 evaluations.setMaximalCount(maxEval); 183 evaluations.resetCount(); 184 } 185 186 /** {@inheritDoc} */ 187 public double solve(int maxEval, FUNC f, double min, double max, double startValue) 188 throws TooManyEvaluationsException, 189 NoBracketingException { 190 // Initialization. 191 setup(maxEval, f, min, max, startValue); 192 193 // Perform computation. 194 return doSolve(); 195 } 196 197 /** {@inheritDoc} */ 198 public double solve(int maxEval, FUNC f, double min, double max) { 199 return solve(maxEval, f, min, max, min + 0.5 * (max - min)); 200 } 201 202 /** {@inheritDoc} */ 203 public double solve(int maxEval, FUNC f, double startValue) 204 throws TooManyEvaluationsException, 205 NoBracketingException { 206 return solve(maxEval, f, Double.NaN, Double.NaN, startValue); 207 } 208 209 /** 210 * Method for implementing actual optimization algorithms in derived 211 * classes. 212 * 213 * @return the root. 214 * @throws TooManyEvaluationsException if the maximal number of evaluations 215 * is exceeded. 216 * @throws NoBracketingException if the initial search interval does not bracket 217 * a root and the solver requires it. 218 */ 219 protected abstract double doSolve() 220 throws TooManyEvaluationsException, NoBracketingException; 221 222 /** 223 * Check whether the function takes opposite signs at the endpoints. 224 * 225 * @param lower Lower endpoint. 226 * @param upper Upper endpoint. 227 * @return {@code true} if the function values have opposite signs at the 228 * given points. 229 */ 230 protected boolean isBracketing(final double lower, 231 final double upper) { 232 return UnivariateSolverUtils.isBracketing(function, lower, upper); 233 } 234 235 /** 236 * Check whether the arguments form a (strictly) increasing sequence. 237 * 238 * @param start First number. 239 * @param mid Second number. 240 * @param end Third number. 241 * @return {@code true} if the arguments form an increasing sequence. 242 */ 243 protected boolean isSequence(final double start, 244 final double mid, 245 final double end) { 246 return UnivariateSolverUtils.isSequence(start, mid, end); 247 } 248 249 /** 250 * Check that the endpoints specify an interval. 251 * 252 * @param lower Lower endpoint. 253 * @param upper Upper endpoint. 254 * @throws NumberIsTooLargeException if {@code lower >= upper}. 255 */ 256 protected void verifyInterval(final double lower, 257 final double upper) 258 throws NumberIsTooLargeException { 259 UnivariateSolverUtils.verifyInterval(lower, upper); 260 } 261 262 /** 263 * Check that {@code lower < initial < upper}. 264 * 265 * @param lower Lower endpoint. 266 * @param initial Initial value. 267 * @param upper Upper endpoint. 268 * @throws NumberIsTooLargeException if {@code lower >= initial} or 269 * {@code initial >= upper}. 270 */ 271 protected void verifySequence(final double lower, 272 final double initial, 273 final double upper) 274 throws NumberIsTooLargeException { 275 UnivariateSolverUtils.verifySequence(lower, initial, upper); 276 } 277 278 /** 279 * Check that the endpoints specify an interval and the function takes 280 * opposite signs at the endpoints. 281 * 282 * @param lower Lower endpoint. 283 * @param upper Upper endpoint. 284 * @throws NullArgumentException if the function has not been set. 285 * @throws NoBracketingException if the function has the same sign at 286 * the endpoints. 287 */ 288 protected void verifyBracketing(final double lower, 289 final double upper) 290 throws NullArgumentException, 291 NoBracketingException { 292 UnivariateSolverUtils.verifyBracketing(function, lower, upper); 293 } 294 295 /** 296 * Increment the evaluation count by one. 297 * Method {@link #computeObjectiveValue(double)} calls this method internally. 298 * It is provided for subclasses that do not exclusively use 299 * {@code computeObjectiveValue} to solve the function. 300 * See e.g. {@link AbstractUnivariateDifferentiableSolver}. 301 * 302 * @throws TooManyEvaluationsException when the allowed number of function 303 * evaluations has been exhausted. 304 */ 305 protected void incrementEvaluationCount() 306 throws TooManyEvaluationsException { 307 try { 308 evaluations.incrementCount(); 309 } catch (MaxCountExceededException e) { 310 throw new TooManyEvaluationsException(e.getMax()); 311 } 312 } 313 }