001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018package org.apache.commons.math3.analysis.solvers;
019
020import org.apache.commons.math3.analysis.UnivariateFunction;
021import org.apache.commons.math3.exception.MaxCountExceededException;
022import org.apache.commons.math3.exception.NoBracketingException;
023import org.apache.commons.math3.exception.TooManyEvaluationsException;
024import org.apache.commons.math3.exception.NumberIsTooLargeException;
025import org.apache.commons.math3.exception.NullArgumentException;
026import org.apache.commons.math3.util.IntegerSequence;
027import org.apache.commons.math3.util.MathUtils;
028
029/**
030 * Provide a default implementation for several functions useful to generic
031 * solvers.
032 * The default values for relative and function tolerances are 1e-14
033 * and 1e-15, respectively. It is however highly recommended to not
034 * rely on the default, but rather carefully consider values that match
035 * user's expectations, as well as the specifics of each implementation.
036 *
037 * @param <FUNC> Type of function to solve.
038 *
039 * @since 2.0
040 */
041public abstract class BaseAbstractUnivariateSolver<FUNC extends UnivariateFunction>
042    implements BaseUnivariateSolver<FUNC> {
043    /** Default relative accuracy. */
044    private static final double DEFAULT_RELATIVE_ACCURACY = 1e-14;
045    /** Default function value accuracy. */
046    private static final double DEFAULT_FUNCTION_VALUE_ACCURACY = 1e-15;
047    /** Function value accuracy. */
048    private final double functionValueAccuracy;
049    /** Absolute accuracy. */
050    private final double absoluteAccuracy;
051    /** Relative accuracy. */
052    private final double relativeAccuracy;
053    /** Evaluations counter. */
054    private IntegerSequence.Incrementor evaluations;
055    /** Lower end of search interval. */
056    private double searchMin;
057    /** Higher end of search interval. */
058    private double searchMax;
059    /** Initial guess. */
060    private double searchStart;
061    /** Function to solve. */
062    private FUNC function;
063
064    /**
065     * Construct a solver with given absolute accuracy.
066     *
067     * @param absoluteAccuracy Maximum absolute error.
068     */
069    protected BaseAbstractUnivariateSolver(final double absoluteAccuracy) {
070        this(DEFAULT_RELATIVE_ACCURACY,
071             absoluteAccuracy,
072             DEFAULT_FUNCTION_VALUE_ACCURACY);
073    }
074
075    /**
076     * Construct a solver with given accuracies.
077     *
078     * @param relativeAccuracy Maximum relative error.
079     * @param absoluteAccuracy Maximum absolute error.
080     */
081    protected BaseAbstractUnivariateSolver(final double relativeAccuracy,
082                                           final double absoluteAccuracy) {
083        this(relativeAccuracy,
084             absoluteAccuracy,
085             DEFAULT_FUNCTION_VALUE_ACCURACY);
086    }
087
088    /**
089     * Construct a solver with given accuracies.
090     *
091     * @param relativeAccuracy Maximum relative error.
092     * @param absoluteAccuracy Maximum absolute error.
093     * @param functionValueAccuracy Maximum function value error.
094     */
095    protected BaseAbstractUnivariateSolver(final double relativeAccuracy,
096                                           final double absoluteAccuracy,
097                                           final double functionValueAccuracy) {
098        this.absoluteAccuracy      = absoluteAccuracy;
099        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}