diff options
Diffstat (limited to 'src/main/java/org/apache/commons/math3/optimization/univariate/BracketFinder.java')
| -rw-r--r-- | src/main/java/org/apache/commons/math3/optimization/univariate/BracketFinder.java | 289 |
1 files changed, 289 insertions, 0 deletions
diff --git a/src/main/java/org/apache/commons/math3/optimization/univariate/BracketFinder.java b/src/main/java/org/apache/commons/math3/optimization/univariate/BracketFinder.java new file mode 100644 index 0000000..cd3057f --- /dev/null +++ b/src/main/java/org/apache/commons/math3/optimization/univariate/BracketFinder.java @@ -0,0 +1,289 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math3.optimization.univariate; + +import org.apache.commons.math3.util.FastMath; +import org.apache.commons.math3.util.Incrementor; +import org.apache.commons.math3.exception.NotStrictlyPositiveException; +import org.apache.commons.math3.exception.TooManyEvaluationsException; +import org.apache.commons.math3.exception.MaxCountExceededException; +import org.apache.commons.math3.analysis.UnivariateFunction; +import org.apache.commons.math3.optimization.GoalType; + +/** + * Provide an interval that brackets a local optimum of a function. + * This code is based on a Python implementation (from <em>SciPy</em>, + * module {@code optimize.py} v0.5). + * + * @deprecated As of 3.1 (to be removed in 4.0). + * @since 2.2 + */ +@Deprecated +public class BracketFinder { + /** Tolerance to avoid division by zero. */ + private static final double EPS_MIN = 1e-21; + /** + * Golden section. + */ + private static final double GOLD = 1.618034; + /** + * Factor for expanding the interval. + */ + private final double growLimit; + /** + * Counter for function evaluations. + */ + private final Incrementor evaluations = new Incrementor(); + /** + * Lower bound of the bracket. + */ + private double lo; + /** + * Higher bound of the bracket. + */ + private double hi; + /** + * Point inside the bracket. + */ + private double mid; + /** + * Function value at {@link #lo}. + */ + private double fLo; + /** + * Function value at {@link #hi}. + */ + private double fHi; + /** + * Function value at {@link #mid}. + */ + private double fMid; + + /** + * Constructor with default values {@code 100, 50} (see the + * {@link #BracketFinder(double,int) other constructor}). + */ + public BracketFinder() { + this(100, 50); + } + + /** + * Create a bracketing interval finder. + * + * @param growLimit Expanding factor. + * @param maxEvaluations Maximum number of evaluations allowed for finding + * a bracketing interval. + */ + public BracketFinder(double growLimit, + int maxEvaluations) { + if (growLimit <= 0) { + throw new NotStrictlyPositiveException(growLimit); + } + if (maxEvaluations <= 0) { + throw new NotStrictlyPositiveException(maxEvaluations); + } + + this.growLimit = growLimit; + evaluations.setMaximalCount(maxEvaluations); + } + + /** + * Search new points that bracket a local optimum of the function. + * + * @param func Function whose optimum should be bracketed. + * @param goal {@link GoalType Goal type}. + * @param xA Initial point. + * @param xB Initial point. + * @throws TooManyEvaluationsException if the maximum number of evaluations + * is exceeded. + */ + public void search(UnivariateFunction func, GoalType goal, double xA, double xB) { + evaluations.resetCount(); + final boolean isMinim = goal == GoalType.MINIMIZE; + + double fA = eval(func, xA); + double fB = eval(func, xB); + if (isMinim ? + fA < fB : + fA > fB) { + + double tmp = xA; + xA = xB; + xB = tmp; + + tmp = fA; + fA = fB; + fB = tmp; + } + + double xC = xB + GOLD * (xB - xA); + double fC = eval(func, xC); + + while (isMinim ? fC < fB : fC > fB) { + double tmp1 = (xB - xA) * (fB - fC); + double tmp2 = (xB - xC) * (fB - fA); + + double val = tmp2 - tmp1; + double denom = FastMath.abs(val) < EPS_MIN ? 2 * EPS_MIN : 2 * val; + + double w = xB - ((xB - xC) * tmp2 - (xB - xA) * tmp1) / denom; + double wLim = xB + growLimit * (xC - xB); + + double fW; + if ((w - xC) * (xB - w) > 0) { + fW = eval(func, w); + if (isMinim ? + fW < fC : + fW > fC) { + xA = xB; + xB = w; + fA = fB; + fB = fW; + break; + } else if (isMinim ? + fW > fB : + fW < fB) { + xC = w; + fC = fW; + break; + } + w = xC + GOLD * (xC - xB); + fW = eval(func, w); + } else if ((w - wLim) * (wLim - xC) >= 0) { + w = wLim; + fW = eval(func, w); + } else if ((w - wLim) * (xC - w) > 0) { + fW = eval(func, w); + if (isMinim ? + fW < fC : + fW > fC) { + xB = xC; + xC = w; + w = xC + GOLD * (xC - xB); + fB = fC; + fC =fW; + fW = eval(func, w); + } + } else { + w = xC + GOLD * (xC - xB); + fW = eval(func, w); + } + + xA = xB; + fA = fB; + xB = xC; + fB = fC; + xC = w; + fC = fW; + } + + lo = xA; + fLo = fA; + mid = xB; + fMid = fB; + hi = xC; + fHi = fC; + + if (lo > hi) { + double tmp = lo; + lo = hi; + hi = tmp; + + tmp = fLo; + fLo = fHi; + fHi = tmp; + } + } + + /** + * @return the number of evalutations. + */ + public int getMaxEvaluations() { + return evaluations.getMaximalCount(); + } + + /** + * @return the number of evalutations. + */ + public int getEvaluations() { + return evaluations.getCount(); + } + + /** + * @return the lower bound of the bracket. + * @see #getFLo() + */ + public double getLo() { + return lo; + } + + /** + * Get function value at {@link #getLo()}. + * @return function value at {@link #getLo()} + */ + public double getFLo() { + return fLo; + } + + /** + * @return the higher bound of the bracket. + * @see #getFHi() + */ + public double getHi() { + return hi; + } + + /** + * Get function value at {@link #getHi()}. + * @return function value at {@link #getHi()} + */ + public double getFHi() { + return fHi; + } + + /** + * @return a point in the middle of the bracket. + * @see #getFMid() + */ + public double getMid() { + return mid; + } + + /** + * Get function value at {@link #getMid()}. + * @return function value at {@link #getMid()} + */ + public double getFMid() { + return fMid; + } + + /** + * @param f Function. + * @param x Argument. + * @return {@code f(x)} + * @throws TooManyEvaluationsException if the maximal number of evaluations is + * exceeded. + */ + private double eval(UnivariateFunction f, double x) { + try { + evaluations.incrementCount(); + } catch (MaxCountExceededException e) { + throw new TooManyEvaluationsException(e.getMax()); + } + return f.value(x); + } +} |