BaseAbstractUnivariateSolver.java

  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. package org.apache.commons.math4.legacy.analysis.solvers;

  18. import org.apache.commons.math4.legacy.analysis.UnivariateFunction;
  19. import org.apache.commons.math4.legacy.exception.NullArgumentException;
  20. import org.apache.commons.math4.legacy.exception.MaxCountExceededException;
  21. import org.apache.commons.math4.legacy.exception.TooManyEvaluationsException;
  22. import org.apache.commons.math4.legacy.core.IntegerSequence;

  23. /**
  24.  * Provide a default implementation for several functions useful to generic
  25.  * solvers.
  26.  * The default values for relative and function tolerances are 1e-14
  27.  * and 1e-15, respectively. It is however highly recommended to not
  28.  * rely on the default, but rather carefully consider values that match
  29.  * user's expectations, as well as the specifics of each implementation.
  30.  *
  31.  * @param <FUNC> Type of function to solve.
  32.  *
  33.  * @since 2.0
  34.  */
  35. public abstract class BaseAbstractUnivariateSolver<FUNC extends UnivariateFunction>
  36.     implements BaseUnivariateSolver<FUNC> {
  37.     /** Default relative accuracy. */
  38.     private static final double DEFAULT_RELATIVE_ACCURACY = 1e-14;
  39.     /** Default function value accuracy. */
  40.     private static final double DEFAULT_FUNCTION_VALUE_ACCURACY = 1e-15;
  41.     /** Function value accuracy. */
  42.     private final double functionValueAccuracy;
  43.     /** Absolute accuracy. */
  44.     private final double absoluteAccuracy;
  45.     /** Relative accuracy. */
  46.     private final double relativeAccuracy;
  47.     /** Evaluations counter. */
  48.     private IntegerSequence.Incrementor evaluations;
  49.     /** Lower end of search interval. */
  50.     private double searchMin;
  51.     /** Higher end of search interval. */
  52.     private double searchMax;
  53.     /** Initial guess. */
  54.     private double searchStart;
  55.     /** Function to solve. */
  56.     private FUNC function;

  57.     /**
  58.      * Construct a solver with given absolute accuracy.
  59.      *
  60.      * @param absoluteAccuracy Maximum absolute error.
  61.      */
  62.     protected BaseAbstractUnivariateSolver(final double absoluteAccuracy) {
  63.         this(DEFAULT_RELATIVE_ACCURACY,
  64.              absoluteAccuracy,
  65.              DEFAULT_FUNCTION_VALUE_ACCURACY);
  66.     }

  67.     /**
  68.      * Construct a solver with given accuracies.
  69.      *
  70.      * @param relativeAccuracy Maximum relative error.
  71.      * @param absoluteAccuracy Maximum absolute error.
  72.      */
  73.     protected BaseAbstractUnivariateSolver(final double relativeAccuracy,
  74.                                            final double absoluteAccuracy) {
  75.         this(relativeAccuracy,
  76.              absoluteAccuracy,
  77.              DEFAULT_FUNCTION_VALUE_ACCURACY);
  78.     }

  79.     /**
  80.      * Construct a solver with given accuracies.
  81.      *
  82.      * @param relativeAccuracy Maximum relative error.
  83.      * @param absoluteAccuracy Maximum absolute error.
  84.      * @param functionValueAccuracy Maximum function value error.
  85.      */
  86.     protected BaseAbstractUnivariateSolver(final double relativeAccuracy,
  87.                                            final double absoluteAccuracy,
  88.                                            final double functionValueAccuracy) {
  89.         this.absoluteAccuracy = absoluteAccuracy;
  90.         this.relativeAccuracy = relativeAccuracy;
  91.         this.functionValueAccuracy = functionValueAccuracy;
  92.     }

  93.     /** {@inheritDoc} */
  94.     @Override
  95.     public int getMaxEvaluations() {
  96.         return evaluations.getMaximalCount();
  97.     }
  98.     /** {@inheritDoc} */
  99.     @Override
  100.     public int getEvaluations() {
  101.         return evaluations.getCount();
  102.     }
  103.     /**
  104.      * @return the lower end of the search interval.
  105.      */
  106.     public double getMin() {
  107.         return searchMin;
  108.     }
  109.     /**
  110.      * @return the higher end of the search interval.
  111.      */
  112.     public double getMax() {
  113.         return searchMax;
  114.     }
  115.     /**
  116.      * @return the initial guess.
  117.      */
  118.     public double getStartValue() {
  119.         return searchStart;
  120.     }
  121.     /**
  122.      * {@inheritDoc}
  123.      */
  124.     @Override
  125.     public double getAbsoluteAccuracy() {
  126.         return absoluteAccuracy;
  127.     }
  128.     /**
  129.      * {@inheritDoc}
  130.      */
  131.     @Override
  132.     public double getRelativeAccuracy() {
  133.         return relativeAccuracy;
  134.     }
  135.     /**
  136.      * {@inheritDoc}
  137.      */
  138.     @Override
  139.     public double getFunctionValueAccuracy() {
  140.         return functionValueAccuracy;
  141.     }

  142.     /**
  143.      * Compute the objective function value.
  144.      *
  145.      * @param point Point at which the objective function must be evaluated.
  146.      * @return the objective function value at specified point.
  147.      * @throws TooManyEvaluationsException if the maximal number of evaluations
  148.      * is exceeded.
  149.      */
  150.     protected double computeObjectiveValue(double point) {
  151.         incrementEvaluationCount();
  152.         return function.value(point);
  153.     }

  154.     /**
  155.      * Prepare for computation.
  156.      * Subclasses must call this method if they override any of the
  157.      * {@code solve} methods.
  158.      *
  159.      * @param f Function to solve.
  160.      * @param min Lower bound for the interval.
  161.      * @param max Upper bound for the interval.
  162.      * @param startValue Start value to use.
  163.      * @param maxEval Maximum number of evaluations.
  164.      * @throws NullArgumentException if {@code f} is {@code null}.
  165.      */
  166.     protected void setup(int maxEval,
  167.                          FUNC f,
  168.                          double min, double max,
  169.                          double startValue) {
  170.         // Checks.
  171.         NullArgumentException.check(f);

  172.         // Reset.
  173.         searchMin = min;
  174.         searchMax = max;
  175.         searchStart = startValue;
  176.         function = f;
  177.         evaluations = IntegerSequence.Incrementor.create()
  178.             .withMaximalCount(maxEval);
  179.     }

  180.     /** {@inheritDoc} */
  181.     @Override
  182.     public double solve(int maxEval, FUNC f, double min, double max, double startValue) {
  183.         // Initialization.
  184.         setup(maxEval, f, min, max, startValue);

  185.         // Perform computation.
  186.         return doSolve();
  187.     }

  188.     /** {@inheritDoc} */
  189.     @Override
  190.     public double solve(int maxEval, FUNC f, double min, double max) {
  191.         return solve(maxEval, f, min, max, min + 0.5 * (max - min));
  192.     }

  193.     /** {@inheritDoc} */
  194.     @Override
  195.     public double solve(int maxEval, FUNC f, double startValue) {
  196.         return solve(maxEval, f, Double.NaN, Double.NaN, startValue);
  197.     }

  198.     /**
  199.      * Method for implementing actual optimization algorithms in derived
  200.      * classes.
  201.      *
  202.      * @return the root.
  203.      * @throws TooManyEvaluationsException if the maximal number of evaluations
  204.      * is exceeded.
  205.      * @throws org.apache.commons.math4.legacy.exception.NoBracketingException
  206.      * if the initial search interval does not bracket a root and the
  207.      * solver requires it.
  208.      */
  209.     protected abstract double doSolve();

  210.     /**
  211.      * Check whether the function takes opposite signs at the endpoints.
  212.      *
  213.      * @param lower Lower endpoint.
  214.      * @param upper Upper endpoint.
  215.      * @return {@code true} if the function values have opposite signs at the
  216.      * given points.
  217.      */
  218.     protected boolean isBracketing(final double lower,
  219.                                    final double upper) {
  220.         return UnivariateSolverUtils.isBracketing(function, lower, upper);
  221.     }

  222.     /**
  223.      * Check whether the arguments form a (strictly) increasing sequence.
  224.      *
  225.      * @param start First number.
  226.      * @param mid Second number.
  227.      * @param end Third number.
  228.      * @return {@code true} if the arguments form an increasing sequence.
  229.      */
  230.     protected boolean isSequence(final double start,
  231.                                  final double mid,
  232.                                  final double end) {
  233.         return UnivariateSolverUtils.isSequence(start, mid, end);
  234.     }

  235.     /**
  236.      * Check that the endpoints specify an interval.
  237.      *
  238.      * @param lower Lower endpoint.
  239.      * @param upper Upper endpoint.
  240.      * @throws org.apache.commons.math4.legacy.exception.NumberIsTooLargeException
  241.      * if {@code lower >= upper}.
  242.      */
  243.     protected void verifyInterval(final double lower,
  244.                                   final double upper) {
  245.         UnivariateSolverUtils.verifyInterval(lower, upper);
  246.     }

  247.     /**
  248.      * Check that {@code lower < initial < upper}.
  249.      *
  250.      * @param lower Lower endpoint.
  251.      * @param initial Initial value.
  252.      * @param upper Upper endpoint.
  253.      * @throws org.apache.commons.math4.legacy.exception.NumberIsTooLargeException
  254.      * if {@code lower >= initial} or {@code initial >= upper}.
  255.      */
  256.     protected void verifySequence(final double lower,
  257.                                   final double initial,
  258.                                   final double upper) {
  259.         UnivariateSolverUtils.verifySequence(lower, initial, upper);
  260.     }

  261.     /**
  262.      * Check that the endpoints specify an interval and the function takes
  263.      * opposite signs at the endpoints.
  264.      *
  265.      * @param lower Lower endpoint.
  266.      * @param upper Upper endpoint.
  267.      * @throws NullArgumentException if the function has not been set.
  268.      * @throws org.apache.commons.math4.legacy.exception.NoBracketingException
  269.      * if the function has the same sign at the endpoints.
  270.      */
  271.     protected void verifyBracketing(final double lower,
  272.                                     final double upper) {
  273.         UnivariateSolverUtils.verifyBracketing(function, lower, upper);
  274.     }

  275.     /**
  276.      * Increment the evaluation count by one.
  277.      * Method {@link #computeObjectiveValue(double)} calls this method internally.
  278.      * It is provided for subclasses that do not exclusively use
  279.      * {@code computeObjectiveValue} to solve the function.
  280.      * See e.g. {@link AbstractUnivariateDifferentiableSolver}.
  281.      *
  282.      * @throws TooManyEvaluationsException when the allowed number of function
  283.      * evaluations has been exhausted.
  284.      */
  285.     protected void incrementEvaluationCount() {
  286.         try {
  287.             evaluations.increment();
  288.         } catch (MaxCountExceededException e) {
  289.             throw new TooManyEvaluationsException(e.getMax());
  290.         }
  291.     }
  292. }