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.IntegerSequence;
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 IntegerSequence.Incrementor evaluations;
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         this.evaluations           = IntegerSequence.Incrementor.create();
102     }
103 
104     /** {@inheritDoc} */
105     public int getMaxEvaluations() {
106         return evaluations.getMaximalCount();
107     }
108     /** {@inheritDoc} */
109     public int getEvaluations() {
110         return evaluations.getCount();
111     }
112     /**
113      * @return the lower end of the search interval.
114      */
115     public double getMin() {
116         return searchMin;
117     }
118     /**
119      * @return the higher end of the search interval.
120      */
121     public double getMax() {
122         return searchMax;
123     }
124     /**
125      * @return the initial guess.
126      */
127     public double getStartValue() {
128         return searchStart;
129     }
130     /**
131      * {@inheritDoc}
132      */
133     public double getAbsoluteAccuracy() {
134         return absoluteAccuracy;
135     }
136     /**
137      * {@inheritDoc}
138      */
139     public double getRelativeAccuracy() {
140         return relativeAccuracy;
141     }
142     /**
143      * {@inheritDoc}
144      */
145     public double getFunctionValueAccuracy() {
146         return functionValueAccuracy;
147     }
148 
149     /**
150      * Compute the objective function value.
151      *
152      * @param point Point at which the objective function must be evaluated.
153      * @return the objective function value at specified point.
154      * @throws TooManyEvaluationsException if the maximal number of evaluations
155      * is exceeded.
156      */
157     protected double computeObjectiveValue(double point)
158         throws TooManyEvaluationsException {
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      * @exception NullArgumentException if f is null
174      */
175     protected void setup(int maxEval,
176                          FUNC f,
177                          double min, double max,
178                          double startValue)
179         throws NullArgumentException {
180         // Checks.
181         MathUtils.checkNotNull(f);
182 
183         // Reset.
184         searchMin = min;
185         searchMax = max;
186         searchStart = startValue;
187         function = f;
188         evaluations = evaluations.withMaximalCount(maxEval).withStart(0);
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.increment();
314         } catch (MaxCountExceededException e) {
315             throw new TooManyEvaluationsException(e.getMax());
316         }
317     }
318 }