    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
    018    package org.apache.commons.math3.analysis.solvers;
    019
    020    import org.apache.commons.math3.analysis.UnivariateFunction;
    021    import org.apache.commons.math3.exception.MaxCountExceededException;
    022    import org.apache.commons.math3.exception.NoBracketingException;
    023    import org.apache.commons.math3.exception.TooManyEvaluationsException;
    024    import org.apache.commons.math3.exception.NumberIsTooLargeException;
    025    import org.apache.commons.math3.exception.NullArgumentException;
    026    import org.apache.commons.math3.util.Incrementor;
    027    import org.apache.commons.math3.util.MathUtils;
    028
    029    /**
    030     * Provide a default implementation for several functions useful to generic
    031     * solvers.
    032     *
    033     * @param <FUNC> Type of function to solve.
    034     *
    035     * @since 2.0
    036     * @version $Id: BaseAbstractUnivariateSolver.java 1391927 2012-09-30 00:03:30Z erans $
    037     */
    038    public 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 final Incrementor evaluations = new Incrementor();
    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        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         */
    170        protected void setup(int maxEval,
    171                             FUNC f,
    172                             double min, double max,
    173                             double startValue) {
    174            // Checks.
    175            MathUtils.checkNotNull(f);
    176
    177            // Reset.
    178            searchMin = min;
    179            searchMax = max;
    180            searchStart = startValue;
    181            function = f;
    182            evaluations.setMaximalCount(maxEval);
    183            evaluations.resetCount();
    184        }
    185
    186        /** {@inheritDoc} */
    187        public double solve(int maxEval, FUNC f, double min, double max, double startValue)
    188            throws TooManyEvaluationsException,
    189                   NoBracketingException {
    190            // Initialization.
    191            setup(maxEval, f, min, max, startValue);
    192
    193            // Perform computation.
    194            return doSolve();
    195        }
    196
    197        /** {@inheritDoc} */
    198        public double solve(int maxEval, FUNC f, double min, double max) {
    199            return solve(maxEval, f, min, max, min + 0.5 * (max - min));
    200        }
    201
    202        /** {@inheritDoc} */
    203        public double solve(int maxEval, FUNC f, double startValue)
    204            throws TooManyEvaluationsException,
    205                   NoBracketingException {
    206            return solve(maxEval, f, Double.NaN, Double.NaN, startValue);
    207        }
    208
    209        /**
    210         * Method for implementing actual optimization algorithms in derived
    211         * classes.
    212         *
    213         * @return the root.
    214         * @throws TooManyEvaluationsException if the maximal number of evaluations
    215         * is exceeded.
    216         * @throws NoBracketingException if the initial search interval does not bracket
    217         * a root and the solver requires it.
    218         */
    219        protected abstract double doSolve()
    220            throws TooManyEvaluationsException, NoBracketingException;
    221
    222        /**
    223         * Check whether the function takes opposite signs at the endpoints.
    224         *
    225         * @param lower Lower endpoint.
    226         * @param upper Upper endpoint.
    227         * @return {@code true} if the function values have opposite signs at the
    228         * given points.
    229         */
    230        protected boolean isBracketing(final double lower,
    231                                       final double upper) {
    232            return UnivariateSolverUtils.isBracketing(function, lower, upper);
    233        }
    234
    235        /**
    236         * Check whether the arguments form a (strictly) increasing sequence.
    237         *
    238         * @param start First number.
    239         * @param mid Second number.
    240         * @param end Third number.
    241         * @return {@code true} if the arguments form an increasing sequence.
    242         */
    243        protected boolean isSequence(final double start,
    244                                     final double mid,
    245                                     final double end) {
    246            return UnivariateSolverUtils.isSequence(start, mid, end);
    247        }
    248
    249        /**
    250         * Check that the endpoints specify an interval.
    251         *
    252         * @param lower Lower endpoint.
    253         * @param upper Upper endpoint.
    254         * @throws NumberIsTooLargeException if {@code lower >= upper}.
    255         */
    256        protected void verifyInterval(final double lower,
    257                                      final double upper)
    258            throws NumberIsTooLargeException {
    259            UnivariateSolverUtils.verifyInterval(lower, upper);
    260        }
    261
    262        /**
    263         * Check that {@code lower < initial < upper}.
    264         *
    265         * @param lower Lower endpoint.
    266         * @param initial Initial value.
    267         * @param upper Upper endpoint.
    268         * @throws NumberIsTooLargeException if {@code lower >= initial} or
    269         * {@code initial >= upper}.
    270         */
    271        protected void verifySequence(final double lower,
    272                                      final double initial,
    273                                      final double upper)
    274            throws NumberIsTooLargeException {
    275            UnivariateSolverUtils.verifySequence(lower, initial, upper);
    276        }
    277
    278        /**
    279         * Check that the endpoints specify an interval and the function takes
    280         * opposite signs at the endpoints.
    281         *
    282         * @param lower Lower endpoint.
    283         * @param upper Upper endpoint.
    284         * @throws NullArgumentException if the function has not been set.
    285         * @throws NoBracketingException if the function has the same sign at
    286         * the endpoints.
    287         */
    288        protected void verifyBracketing(final double lower,
    289                                        final double upper)
    290            throws NullArgumentException,
    291                   NoBracketingException {
    292            UnivariateSolverUtils.verifyBracketing(function, lower, upper);
    293        }
    294
    295        /**
    296         * Increment the evaluation count by one.
    297         * Method {@link #computeObjectiveValue(double)} calls this method internally.
    298         * It is provided for subclasses that do not exclusively use
    299         * {@code computeObjectiveValue} to solve the function.
    300         * See e.g. {@link AbstractUnivariateDifferentiableSolver}.
    301         *
    302         * @throws TooManyEvaluationsException when the allowed number of function
    303         * evaluations has been exhausted.
    304         */
    305        protected void incrementEvaluationCount()
    306            throws TooManyEvaluationsException {
    307            try {
    308                evaluations.incrementCount();
    309            } catch (MaxCountExceededException e) {
    310                throw new TooManyEvaluationsException(e.getMax());
    311            }
    312        }
    313    }