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