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.math4.legacy.analysis.solvers;
019
020import org.apache.commons.math4.legacy.analysis.UnivariateFunction;
021import org.apache.commons.math4.legacy.exception.NullArgumentException;
022import org.apache.commons.math4.legacy.exception.MaxCountExceededException;
023import org.apache.commons.math4.legacy.exception.TooManyEvaluationsException;
024import org.apache.commons.math4.legacy.core.IntegerSequence;
025
026/**
027 * Provide a default implementation for several functions useful to generic
028 * solvers.
029 * The default values for relative and function tolerances are 1e-14
030 * and 1e-15, respectively. It is however highly recommended to not
031 * rely on the default, but rather carefully consider values that match
032 * user's expectations, as well as the specifics of each implementation.
033 *
034 * @param <FUNC> Type of function to solve.
035 *
036 * @since 2.0
037 */
038public abstract class BaseAbstractUnivariateSolver<FUNC extends UnivariateFunction>
039    implements BaseUnivariateSolver<FUNC> {
040    /** Default relative accuracy. */
041    private static final double DEFAULT_RELATIVE_ACCURACY = 1e-14;
042    /** Default function value accuracy. */
043    private static final double DEFAULT_FUNCTION_VALUE_ACCURACY = 1e-15;
044    /** Function value accuracy. */
045    private final double functionValueAccuracy;
046    /** Absolute accuracy. */
047    private final double absoluteAccuracy;
048    /** Relative accuracy. */
049    private final double relativeAccuracy;
050    /** Evaluations counter. */
051    private IntegerSequence.Incrementor evaluations;
052    /** Lower end of search interval. */
053    private double searchMin;
054    /** Higher end of search interval. */
055    private double searchMax;
056    /** Initial guess. */
057    private double searchStart;
058    /** Function to solve. */
059    private FUNC function;
060
061    /**
062     * Construct a solver with given absolute accuracy.
063     *
064     * @param absoluteAccuracy Maximum absolute error.
065     */
066    protected BaseAbstractUnivariateSolver(final double absoluteAccuracy) {
067        this(DEFAULT_RELATIVE_ACCURACY,
068             absoluteAccuracy,
069             DEFAULT_FUNCTION_VALUE_ACCURACY);
070    }
071
072    /**
073     * Construct a solver with given accuracies.
074     *
075     * @param relativeAccuracy Maximum relative error.
076     * @param absoluteAccuracy Maximum absolute error.
077     */
078    protected BaseAbstractUnivariateSolver(final double relativeAccuracy,
079                                           final double absoluteAccuracy) {
080        this(relativeAccuracy,
081             absoluteAccuracy,
082             DEFAULT_FUNCTION_VALUE_ACCURACY);
083    }
084
085    /**
086     * Construct a solver with given accuracies.
087     *
088     * @param relativeAccuracy Maximum relative error.
089     * @param absoluteAccuracy Maximum absolute error.
090     * @param functionValueAccuracy Maximum function value error.
091     */
092    protected BaseAbstractUnivariateSolver(final double relativeAccuracy,
093                                           final double absoluteAccuracy,
094                                           final double functionValueAccuracy) {
095        this.absoluteAccuracy = absoluteAccuracy;
096        this.relativeAccuracy = relativeAccuracy;
097        this.functionValueAccuracy = functionValueAccuracy;
098    }
099
100    /** {@inheritDoc} */
101    @Override
102    public int getMaxEvaluations() {
103        return evaluations.getMaximalCount();
104    }
105    /** {@inheritDoc} */
106    @Override
107    public int getEvaluations() {
108        return evaluations.getCount();
109    }
110    /**
111     * @return the lower end of the search interval.
112     */
113    public double getMin() {
114        return searchMin;
115    }
116    /**
117     * @return the higher end of the search interval.
118     */
119    public double getMax() {
120        return searchMax;
121    }
122    /**
123     * @return the initial guess.
124     */
125    public double getStartValue() {
126        return searchStart;
127    }
128    /**
129     * {@inheritDoc}
130     */
131    @Override
132    public double getAbsoluteAccuracy() {
133        return absoluteAccuracy;
134    }
135    /**
136     * {@inheritDoc}
137     */
138    @Override
139    public double getRelativeAccuracy() {
140        return relativeAccuracy;
141    }
142    /**
143     * {@inheritDoc}
144     */
145    @Override
146    public double getFunctionValueAccuracy() {
147        return functionValueAccuracy;
148    }
149
150    /**
151     * Compute the objective function value.
152     *
153     * @param point Point at which the objective function must be evaluated.
154     * @return the objective function value at specified point.
155     * @throws TooManyEvaluationsException if the maximal number of evaluations
156     * is exceeded.
157     */
158    protected double computeObjectiveValue(double point) {
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     * @throws NullArgumentException if {@code f} is {@code null}.
174     */
175    protected void setup(int maxEval,
176                         FUNC f,
177                         double min, double max,
178                         double startValue) {
179        // Checks.
180        NullArgumentException.check(f);
181
182        // Reset.
183        searchMin = min;
184        searchMax = max;
185        searchStart = startValue;
186        function = f;
187        evaluations = IntegerSequence.Incrementor.create()
188            .withMaximalCount(maxEval);
189    }
190
191    /** {@inheritDoc} */
192    @Override
193    public double solve(int maxEval, FUNC f, double min, double max, double startValue) {
194        // Initialization.
195        setup(maxEval, f, min, max, startValue);
196
197        // Perform computation.
198        return doSolve();
199    }
200
201    /** {@inheritDoc} */
202    @Override
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    @Override
209    public double solve(int maxEval, FUNC f, double startValue) {
210        return solve(maxEval, f, Double.NaN, Double.NaN, startValue);
211    }
212
213    /**
214     * Method for implementing actual optimization algorithms in derived
215     * classes.
216     *
217     * @return the root.
218     * @throws TooManyEvaluationsException if the maximal number of evaluations
219     * is exceeded.
220     * @throws org.apache.commons.math4.legacy.exception.NoBracketingException
221     * if the initial search interval does not bracket a root and the
222     * solver requires it.
223     */
224    protected abstract double doSolve();
225
226    /**
227     * Check whether the function takes opposite signs at the endpoints.
228     *
229     * @param lower Lower endpoint.
230     * @param upper Upper endpoint.
231     * @return {@code true} if the function values have opposite signs at the
232     * given points.
233     */
234    protected boolean isBracketing(final double lower,
235                                   final double upper) {
236        return UnivariateSolverUtils.isBracketing(function, lower, upper);
237    }
238
239    /**
240     * Check whether the arguments form a (strictly) increasing sequence.
241     *
242     * @param start First number.
243     * @param mid Second number.
244     * @param end Third number.
245     * @return {@code true} if the arguments form an increasing sequence.
246     */
247    protected boolean isSequence(final double start,
248                                 final double mid,
249                                 final double end) {
250        return UnivariateSolverUtils.isSequence(start, mid, end);
251    }
252
253    /**
254     * Check that the endpoints specify an interval.
255     *
256     * @param lower Lower endpoint.
257     * @param upper Upper endpoint.
258     * @throws org.apache.commons.math4.legacy.exception.NumberIsTooLargeException
259     * if {@code lower >= upper}.
260     */
261    protected void verifyInterval(final double lower,
262                                  final double upper) {
263        UnivariateSolverUtils.verifyInterval(lower, upper);
264    }
265
266    /**
267     * Check that {@code lower < initial < upper}.
268     *
269     * @param lower Lower endpoint.
270     * @param initial Initial value.
271     * @param upper Upper endpoint.
272     * @throws org.apache.commons.math4.legacy.exception.NumberIsTooLargeException
273     * if {@code lower >= initial} or {@code initial >= upper}.
274     */
275    protected void verifySequence(final double lower,
276                                  final double initial,
277                                  final double upper) {
278        UnivariateSolverUtils.verifySequence(lower, initial, upper);
279    }
280
281    /**
282     * Check that the endpoints specify an interval and the function takes
283     * opposite signs at the endpoints.
284     *
285     * @param lower Lower endpoint.
286     * @param upper Upper endpoint.
287     * @throws NullArgumentException if the function has not been set.
288     * @throws org.apache.commons.math4.legacy.exception.NoBracketingException
289     * if the function has the same sign at the endpoints.
290     */
291    protected void verifyBracketing(final double lower,
292                                    final double upper) {
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        try {
308            evaluations.increment();
309        } catch (MaxCountExceededException e) {
310            throw new TooManyEvaluationsException(e.getMax());
311        }
312    }
313}