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.math4.legacy.analysis.solvers;
19
20 import org.apache.commons.math4.legacy.analysis.UnivariateFunction;
21 import org.apache.commons.math4.legacy.exception.NullArgumentException;
22 import org.apache.commons.math4.legacy.exception.MaxCountExceededException;
23 import org.apache.commons.math4.legacy.exception.TooManyEvaluationsException;
24 import org.apache.commons.math4.legacy.core.IntegerSequence;
25
26 /**
27 * Provide a default implementation for several functions useful to generic
28 * solvers.
29 * The default values for relative and function tolerances are 1e-14
30 * and 1e-15, respectively. It is however highly recommended to not
31 * rely on the default, but rather carefully consider values that match
32 * user's expectations, as well as the specifics of each implementation.
33 *
34 * @param <FUNC> Type of function to solve.
35 *
36 * @since 2.0
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 IntegerSequence.Incrementor evaluations;
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 @Override
102 public int getMaxEvaluations() {
103 return evaluations.getMaximalCount();
104 }
105 /** {@inheritDoc} */
106 @Override
107 public int getEvaluations() {
108 return evaluations.getCount();
109 }
110 /**
111 * @return the lower end of the search interval.
112 */
113 public double getMin() {
114 return searchMin;
115 }
116 /**
117 * @return the higher end of the search interval.
118 */
119 public double getMax() {
120 return searchMax;
121 }
122 /**
123 * @return the initial guess.
124 */
125 public double getStartValue() {
126 return searchStart;
127 }
128 /**
129 * {@inheritDoc}
130 */
131 @Override
132 public double getAbsoluteAccuracy() {
133 return absoluteAccuracy;
134 }
135 /**
136 * {@inheritDoc}
137 */
138 @Override
139 public double getRelativeAccuracy() {
140 return relativeAccuracy;
141 }
142 /**
143 * {@inheritDoc}
144 */
145 @Override
146 public double getFunctionValueAccuracy() {
147 return functionValueAccuracy;
148 }
149
150 /**
151 * Compute the objective function value.
152 *
153 * @param point Point at which the objective function must be evaluated.
154 * @return the objective function value at specified point.
155 * @throws TooManyEvaluationsException if the maximal number of evaluations
156 * is exceeded.
157 */
158 protected double computeObjectiveValue(double point) {
159 incrementEvaluationCount();
160 return function.value(point);
161 }
162
163 /**
164 * Prepare for computation.
165 * Subclasses must call this method if they override any of the
166 * {@code solve} methods.
167 *
168 * @param f Function to solve.
169 * @param min Lower bound for the interval.
170 * @param max Upper bound for the interval.
171 * @param startValue Start value to use.
172 * @param maxEval Maximum number of evaluations.
173 * @throws NullArgumentException if {@code f} is {@code null}.
174 */
175 protected void setup(int maxEval,
176 FUNC f,
177 double min, double max,
178 double startValue) {
179 // Checks.
180 NullArgumentException.check(f);
181
182 // Reset.
183 searchMin = min;
184 searchMax = max;
185 searchStart = startValue;
186 function = f;
187 evaluations = IntegerSequence.Incrementor.create()
188 .withMaximalCount(maxEval);
189 }
190
191 /** {@inheritDoc} */
192 @Override
193 public double solve(int maxEval, FUNC f, double min, double max, double startValue) {
194 // Initialization.
195 setup(maxEval, f, min, max, startValue);
196
197 // Perform computation.
198 return doSolve();
199 }
200
201 /** {@inheritDoc} */
202 @Override
203 public double solve(int maxEval, FUNC f, double min, double max) {
204 return solve(maxEval, f, min, max, min + 0.5 * (max - min));
205 }
206
207 /** {@inheritDoc} */
208 @Override
209 public double solve(int maxEval, FUNC f, double startValue) {
210 return solve(maxEval, f, Double.NaN, Double.NaN, startValue);
211 }
212
213 /**
214 * Method for implementing actual optimization algorithms in derived
215 * classes.
216 *
217 * @return the root.
218 * @throws TooManyEvaluationsException if the maximal number of evaluations
219 * is exceeded.
220 * @throws org.apache.commons.math4.legacy.exception.NoBracketingException
221 * if the initial search interval does not bracket a root and the
222 * solver requires it.
223 */
224 protected abstract double doSolve();
225
226 /**
227 * Check whether the function takes opposite signs at the endpoints.
228 *
229 * @param lower Lower endpoint.
230 * @param upper Upper endpoint.
231 * @return {@code true} if the function values have opposite signs at the
232 * given points.
233 */
234 protected boolean isBracketing(final double lower,
235 final double upper) {
236 return UnivariateSolverUtils.isBracketing(function, lower, upper);
237 }
238
239 /**
240 * Check whether the arguments form a (strictly) increasing sequence.
241 *
242 * @param start First number.
243 * @param mid Second number.
244 * @param end Third number.
245 * @return {@code true} if the arguments form an increasing sequence.
246 */
247 protected boolean isSequence(final double start,
248 final double mid,
249 final double end) {
250 return UnivariateSolverUtils.isSequence(start, mid, end);
251 }
252
253 /**
254 * Check that the endpoints specify an interval.
255 *
256 * @param lower Lower endpoint.
257 * @param upper Upper endpoint.
258 * @throws org.apache.commons.math4.legacy.exception.NumberIsTooLargeException
259 * if {@code lower >= upper}.
260 */
261 protected void verifyInterval(final double lower,
262 final double upper) {
263 UnivariateSolverUtils.verifyInterval(lower, upper);
264 }
265
266 /**
267 * Check that {@code lower < initial < upper}.
268 *
269 * @param lower Lower endpoint.
270 * @param initial Initial value.
271 * @param upper Upper endpoint.
272 * @throws org.apache.commons.math4.legacy.exception.NumberIsTooLargeException
273 * if {@code lower >= initial} or {@code initial >= upper}.
274 */
275 protected void verifySequence(final double lower,
276 final double initial,
277 final double upper) {
278 UnivariateSolverUtils.verifySequence(lower, initial, upper);
279 }
280
281 /**
282 * Check that the endpoints specify an interval and the function takes
283 * opposite signs at the endpoints.
284 *
285 * @param lower Lower endpoint.
286 * @param upper Upper endpoint.
287 * @throws NullArgumentException if the function has not been set.
288 * @throws org.apache.commons.math4.legacy.exception.NoBracketingException
289 * if the function has the same sign at the endpoints.
290 */
291 protected void verifyBracketing(final double lower,
292 final double upper) {
293 UnivariateSolverUtils.verifyBracketing(function, lower, upper);
294 }
295
296 /**
297 * Increment the evaluation count by one.
298 * Method {@link #computeObjectiveValue(double)} calls this method internally.
299 * It is provided for subclasses that do not exclusively use
300 * {@code computeObjectiveValue} to solve the function.
301 * See e.g. {@link AbstractUnivariateDifferentiableSolver}.
302 *
303 * @throws TooManyEvaluationsException when the allowed number of function
304 * evaluations has been exhausted.
305 */
306 protected void incrementEvaluationCount() {
307 try {
308 evaluations.increment();
309 } catch (MaxCountExceededException e) {
310 throw new TooManyEvaluationsException(e.getMax());
311 }
312 }
313 }