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 }