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    }