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 1455194 2013-03-11 15:45:54Z luc $
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 * @exception NullArgumentException if f is null
170 */
171 protected void setup(int maxEval,
172 FUNC f,
173 double min, double max,
174 double startValue)
175 throws NullArgumentException {
176 // Checks.
177 MathUtils.checkNotNull(f);
178
179 // Reset.
180 searchMin = min;
181 searchMax = max;
182 searchStart = startValue;
183 function = f;
184 evaluations.setMaximalCount(maxEval);
185 evaluations.resetCount();
186 }
187
188 /** {@inheritDoc} */
189 public double solve(int maxEval, FUNC f, double min, double max, double startValue)
190 throws TooManyEvaluationsException,
191 NoBracketingException {
192 // Initialization.
193 setup(maxEval, f, min, max, startValue);
194
195 // Perform computation.
196 return doSolve();
197 }
198
199 /** {@inheritDoc} */
200 public double solve(int maxEval, FUNC f, double min, double max) {
201 return solve(maxEval, f, min, max, min + 0.5 * (max - min));
202 }
203
204 /** {@inheritDoc} */
205 public double solve(int maxEval, FUNC f, double startValue)
206 throws TooManyEvaluationsException,
207 NoBracketingException {
208 return solve(maxEval, f, Double.NaN, Double.NaN, startValue);
209 }
210
211 /**
212 * Method for implementing actual optimization algorithms in derived
213 * classes.
214 *
215 * @return the root.
216 * @throws TooManyEvaluationsException if the maximal number of evaluations
217 * is exceeded.
218 * @throws NoBracketingException if the initial search interval does not bracket
219 * a root and the solver requires it.
220 */
221 protected abstract double doSolve()
222 throws TooManyEvaluationsException, NoBracketingException;
223
224 /**
225 * Check whether the function takes opposite signs at the endpoints.
226 *
227 * @param lower Lower endpoint.
228 * @param upper Upper endpoint.
229 * @return {@code true} if the function values have opposite signs at the
230 * given points.
231 */
232 protected boolean isBracketing(final double lower,
233 final double upper) {
234 return UnivariateSolverUtils.isBracketing(function, lower, upper);
235 }
236
237 /**
238 * Check whether the arguments form a (strictly) increasing sequence.
239 *
240 * @param start First number.
241 * @param mid Second number.
242 * @param end Third number.
243 * @return {@code true} if the arguments form an increasing sequence.
244 */
245 protected boolean isSequence(final double start,
246 final double mid,
247 final double end) {
248 return UnivariateSolverUtils.isSequence(start, mid, end);
249 }
250
251 /**
252 * Check that the endpoints specify an interval.
253 *
254 * @param lower Lower endpoint.
255 * @param upper Upper endpoint.
256 * @throws NumberIsTooLargeException if {@code lower >= upper}.
257 */
258 protected void verifyInterval(final double lower,
259 final double upper)
260 throws NumberIsTooLargeException {
261 UnivariateSolverUtils.verifyInterval(lower, upper);
262 }
263
264 /**
265 * Check that {@code lower < initial < upper}.
266 *
267 * @param lower Lower endpoint.
268 * @param initial Initial value.
269 * @param upper Upper endpoint.
270 * @throws NumberIsTooLargeException if {@code lower >= initial} or
271 * {@code initial >= upper}.
272 */
273 protected void verifySequence(final double lower,
274 final double initial,
275 final double upper)
276 throws NumberIsTooLargeException {
277 UnivariateSolverUtils.verifySequence(lower, initial, upper);
278 }
279
280 /**
281 * Check that the endpoints specify an interval and the function takes
282 * opposite signs at the endpoints.
283 *
284 * @param lower Lower endpoint.
285 * @param upper Upper endpoint.
286 * @throws NullArgumentException if the function has not been set.
287 * @throws NoBracketingException if the function has the same sign at
288 * the endpoints.
289 */
290 protected void verifyBracketing(final double lower,
291 final double upper)
292 throws NullArgumentException,
293 NoBracketingException {
294 UnivariateSolverUtils.verifyBracketing(function, lower, upper);
295 }
296
297 /**
298 * Increment the evaluation count by one.
299 * Method {@link #computeObjectiveValue(double)} calls this method internally.
300 * It is provided for subclasses that do not exclusively use
301 * {@code computeObjectiveValue} to solve the function.
302 * See e.g. {@link AbstractUnivariateDifferentiableSolver}.
303 *
304 * @throws TooManyEvaluationsException when the allowed number of function
305 * evaluations has been exhausted.
306 */
307 protected void incrementEvaluationCount()
308 throws TooManyEvaluationsException {
309 try {
310 evaluations.incrementCount();
311 } catch (MaxCountExceededException e) {
312 throw new TooManyEvaluationsException(e.getMax());
313 }
314 }
315 }