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   *
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 }