1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 package org.apache.commons.math3.analysis.solvers;
19
20 import org.apache.commons.math3.analysis.UnivariateFunction;
21 import org.apache.commons.math3.exception.MaxCountExceededException;
22 import org.apache.commons.math3.exception.NoBracketingException;
23 import org.apache.commons.math3.exception.TooManyEvaluationsException;
24 import org.apache.commons.math3.exception.NumberIsTooLargeException;
25 import org.apache.commons.math3.exception.NullArgumentException;
26 import org.apache.commons.math3.util.Incrementor;
27 import org.apache.commons.math3.util.MathUtils;
28
29 /**
30 * Provide a default implementation for several functions useful to generic
31 * solvers.
32 *
33 * @param <FUNC> Type of function to solve.
34 *
35 * @since 2.0
36 * @version $Id: BaseAbstractUnivariateSolver.java 1455194 2013-03-11 15:45:54Z luc $
37 */
38 public abstract class BaseAbstractUnivariateSolver<FUNC extends UnivariateFunction>
39 implements BaseUnivariateSolver<FUNC> {
40 /** Default relative accuracy. */
41 private static final double DEFAULT_RELATIVE_ACCURACY = 1e-14;
42 /** Default function value accuracy. */
43 private static final double DEFAULT_FUNCTION_VALUE_ACCURACY = 1e-15;
44 /** Function value accuracy. */
45 private final double functionValueAccuracy;
46 /** Absolute accuracy. */
47 private final double absoluteAccuracy;
48 /** Relative accuracy. */
49 private final double relativeAccuracy;
50 /** Evaluations counter. */
51 private final Incrementor evaluations = new Incrementor();
52 /** Lower end of search interval. */
53 private double searchMin;
54 /** Higher end of search interval. */
55 private double searchMax;
56 /** Initial guess. */
57 private double searchStart;
58 /** Function to solve. */
59 private FUNC function;
60
61 /**
62 * Construct a solver with given absolute accuracy.
63 *
64 * @param absoluteAccuracy Maximum absolute error.
65 */
66 protected BaseAbstractUnivariateSolver(final double absoluteAccuracy) {
67 this(DEFAULT_RELATIVE_ACCURACY,
68 absoluteAccuracy,
69 DEFAULT_FUNCTION_VALUE_ACCURACY);
70 }
71
72 /**
73 * Construct a solver with given accuracies.
74 *
75 * @param relativeAccuracy Maximum relative error.
76 * @param absoluteAccuracy Maximum absolute error.
77 */
78 protected BaseAbstractUnivariateSolver(final double relativeAccuracy,
79 final double absoluteAccuracy) {
80 this(relativeAccuracy,
81 absoluteAccuracy,
82 DEFAULT_FUNCTION_VALUE_ACCURACY);
83 }
84
85 /**
86 * Construct a solver with given accuracies.
87 *
88 * @param relativeAccuracy Maximum relative error.
89 * @param absoluteAccuracy Maximum absolute error.
90 * @param functionValueAccuracy Maximum function value error.
91 */
92 protected BaseAbstractUnivariateSolver(final double relativeAccuracy,
93 final double absoluteAccuracy,
94 final double functionValueAccuracy) {
95 this.absoluteAccuracy = absoluteAccuracy;
96 this.relativeAccuracy = relativeAccuracy;
97 this.functionValueAccuracy = functionValueAccuracy;
98 }
99
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 }