View Javadoc
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   * The default values for relative and function tolerances are 1e-14
33   * and 1e-15, respectively. It is however highly recommended to not
34   * rely on the default, but rather carefully consider values that match
35   * user's expectations, as well as the specifics of each implementation.
36   *
37   * @param <FUNC> Type of function to solve.
38   *
39   * @since 2.0
40   */
41  public abstract class BaseAbstractUnivariateSolver<FUNC extends UnivariateFunction>
42      implements BaseUnivariateSolver<FUNC> {
43      /** Default relative accuracy. */
44      private static final double DEFAULT_RELATIVE_ACCURACY = 1e-14;
45      /** Default function value accuracy. */
46      private static final double DEFAULT_FUNCTION_VALUE_ACCURACY = 1e-15;
47      /** Function value accuracy. */
48      private final double functionValueAccuracy;
49      /** Absolute accuracy. */
50      private final double absoluteAccuracy;
51      /** Relative accuracy. */
52      private final double relativeAccuracy;
53      /** Evaluations counter. */
54      private final Incrementor evaluations = new Incrementor();
55      /** Lower end of search interval. */
56      private double searchMin;
57      /** Higher end of search interval. */
58      private double searchMax;
59      /** Initial guess. */
60      private double searchStart;
61      /** Function to solve. */
62      private FUNC function;
63  
64      /**
65       * Construct a solver with given absolute accuracy.
66       *
67       * @param absoluteAccuracy Maximum absolute error.
68       */
69      protected BaseAbstractUnivariateSolver(final double absoluteAccuracy) {
70          this(DEFAULT_RELATIVE_ACCURACY,
71               absoluteAccuracy,
72               DEFAULT_FUNCTION_VALUE_ACCURACY);
73      }
74  
75      /**
76       * Construct a solver with given accuracies.
77       *
78       * @param relativeAccuracy Maximum relative error.
79       * @param absoluteAccuracy Maximum absolute error.
80       */
81      protected BaseAbstractUnivariateSolver(final double relativeAccuracy,
82                                             final double absoluteAccuracy) {
83          this(relativeAccuracy,
84               absoluteAccuracy,
85               DEFAULT_FUNCTION_VALUE_ACCURACY);
86      }
87  
88      /**
89       * Construct a solver with given accuracies.
90       *
91       * @param relativeAccuracy Maximum relative error.
92       * @param absoluteAccuracy Maximum absolute error.
93       * @param functionValueAccuracy Maximum function value error.
94       */
95      protected BaseAbstractUnivariateSolver(final double relativeAccuracy,
96                                             final double absoluteAccuracy,
97                                             final double functionValueAccuracy) {
98          this.absoluteAccuracy = absoluteAccuracy;
99          this.relativeAccuracy = relativeAccuracy;
100         this.functionValueAccuracy = functionValueAccuracy;
101     }
102 
103     /** {@inheritDoc} */
104     public int getMaxEvaluations() {
105         return evaluations.getMaximalCount();
106     }
107     /** {@inheritDoc} */
108     public int getEvaluations() {
109         return evaluations.getCount();
110     }
111     /**
112      * @return the lower end of the search interval.
113      */
114     public double getMin() {
115         return searchMin;
116     }
117     /**
118      * @return the higher end of the search interval.
119      */
120     public double getMax() {
121         return searchMax;
122     }
123     /**
124      * @return the initial guess.
125      */
126     public double getStartValue() {
127         return searchStart;
128     }
129     /**
130      * {@inheritDoc}
131      */
132     public double getAbsoluteAccuracy() {
133         return absoluteAccuracy;
134     }
135     /**
136      * {@inheritDoc}
137      */
138     public double getRelativeAccuracy() {
139         return relativeAccuracy;
140     }
141     /**
142      * {@inheritDoc}
143      */
144     public double getFunctionValueAccuracy() {
145         return functionValueAccuracy;
146     }
147 
148     /**
149      * Compute the objective function value.
150      *
151      * @param point Point at which the objective function must be evaluated.
152      * @return the objective function value at specified point.
153      * @throws TooManyEvaluationsException if the maximal number of evaluations
154      * is exceeded.
155      */
156     protected double computeObjectiveValue(double point)
157         throws TooManyEvaluationsException {
158         incrementEvaluationCount();
159         return function.value(point);
160     }
161 
162     /**
163      * Prepare for computation.
164      * Subclasses must call this method if they override any of the
165      * {@code solve} methods.
166      *
167      * @param f Function to solve.
168      * @param min Lower bound for the interval.
169      * @param max Upper bound for the interval.
170      * @param startValue Start value to use.
171      * @param maxEval Maximum number of evaluations.
172      * @exception NullArgumentException if f is null
173      */
174     protected void setup(int maxEval,
175                          FUNC f,
176                          double min, double max,
177                          double startValue)
178         throws NullArgumentException {
179         // Checks.
180         MathUtils.checkNotNull(f);
181 
182         // Reset.
183         searchMin = min;
184         searchMax = max;
185         searchStart = startValue;
186         function = f;
187         evaluations.setMaximalCount(maxEval);
188         evaluations.resetCount();
189     }
190 
191     /** {@inheritDoc} */
192     public double solve(int maxEval, FUNC f, double min, double max, double startValue)
193         throws TooManyEvaluationsException,
194                NoBracketingException {
195         // Initialization.
196         setup(maxEval, f, min, max, startValue);
197 
198         // Perform computation.
199         return doSolve();
200     }
201 
202     /** {@inheritDoc} */
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     public double solve(int maxEval, FUNC f, double startValue)
209         throws TooManyEvaluationsException,
210                NoBracketingException {
211         return solve(maxEval, f, Double.NaN, Double.NaN, startValue);
212     }
213 
214     /**
215      * Method for implementing actual optimization algorithms in derived
216      * classes.
217      *
218      * @return the root.
219      * @throws TooManyEvaluationsException if the maximal number of evaluations
220      * is exceeded.
221      * @throws NoBracketingException if the initial search interval does not bracket
222      * a root and the solver requires it.
223      */
224     protected abstract double doSolve()
225         throws TooManyEvaluationsException, NoBracketingException;
226 
227     /**
228      * Check whether the function takes opposite signs at the endpoints.
229      *
230      * @param lower Lower endpoint.
231      * @param upper Upper endpoint.
232      * @return {@code true} if the function values have opposite signs at the
233      * given points.
234      */
235     protected boolean isBracketing(final double lower,
236                                    final double upper) {
237         return UnivariateSolverUtils.isBracketing(function, lower, upper);
238     }
239 
240     /**
241      * Check whether the arguments form a (strictly) increasing sequence.
242      *
243      * @param start First number.
244      * @param mid Second number.
245      * @param end Third number.
246      * @return {@code true} if the arguments form an increasing sequence.
247      */
248     protected boolean isSequence(final double start,
249                                  final double mid,
250                                  final double end) {
251         return UnivariateSolverUtils.isSequence(start, mid, end);
252     }
253 
254     /**
255      * Check that the endpoints specify an interval.
256      *
257      * @param lower Lower endpoint.
258      * @param upper Upper endpoint.
259      * @throws NumberIsTooLargeException if {@code lower >= upper}.
260      */
261     protected void verifyInterval(final double lower,
262                                   final double upper)
263         throws NumberIsTooLargeException {
264         UnivariateSolverUtils.verifyInterval(lower, upper);
265     }
266 
267     /**
268      * Check that {@code lower < initial < upper}.
269      *
270      * @param lower Lower endpoint.
271      * @param initial Initial value.
272      * @param upper Upper endpoint.
273      * @throws NumberIsTooLargeException if {@code lower >= initial} or
274      * {@code initial >= upper}.
275      */
276     protected void verifySequence(final double lower,
277                                   final double initial,
278                                   final double upper)
279         throws NumberIsTooLargeException {
280         UnivariateSolverUtils.verifySequence(lower, initial, upper);
281     }
282 
283     /**
284      * Check that the endpoints specify an interval and the function takes
285      * opposite signs at the endpoints.
286      *
287      * @param lower Lower endpoint.
288      * @param upper Upper endpoint.
289      * @throws NullArgumentException if the function has not been set.
290      * @throws NoBracketingException if the function has the same sign at
291      * the endpoints.
292      */
293     protected void verifyBracketing(final double lower,
294                                     final double upper)
295         throws NullArgumentException,
296                NoBracketingException {
297         UnivariateSolverUtils.verifyBracketing(function, lower, upper);
298     }
299 
300     /**
301      * Increment the evaluation count by one.
302      * Method {@link #computeObjectiveValue(double)} calls this method internally.
303      * It is provided for subclasses that do not exclusively use
304      * {@code computeObjectiveValue} to solve the function.
305      * See e.g. {@link AbstractUnivariateDifferentiableSolver}.
306      *
307      * @throws TooManyEvaluationsException when the allowed number of function
308      * evaluations has been exhausted.
309      */
310     protected void incrementEvaluationCount()
311         throws TooManyEvaluationsException {
312         try {
313             evaluations.incrementCount();
314         } catch (MaxCountExceededException e) {
315             throw new TooManyEvaluationsException(e.getMax());
316         }
317     }
318 }