diff options
Diffstat (limited to 'src/main/java/org/apache/commons/math3/optimization/univariate')
9 files changed, 1314 insertions, 0 deletions
diff --git a/src/main/java/org/apache/commons/math3/optimization/univariate/BaseAbstractUnivariateOptimizer.java b/src/main/java/org/apache/commons/math3/optimization/univariate/BaseAbstractUnivariateOptimizer.java new file mode 100644 index 0000000..fcacd01 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/optimization/univariate/BaseAbstractUnivariateOptimizer.java @@ -0,0 +1,162 @@ +/* + * 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.Incrementor; +import org.apache.commons.math3.exception.MaxCountExceededException; +import org.apache.commons.math3.exception.TooManyEvaluationsException; +import org.apache.commons.math3.exception.NullArgumentException; +import org.apache.commons.math3.analysis.UnivariateFunction; +import org.apache.commons.math3.optimization.GoalType; +import org.apache.commons.math3.optimization.ConvergenceChecker; + +/** + * Provide a default implementation for several functions useful to generic + * optimizers. + * + * @deprecated As of 3.1 (to be removed in 4.0). + * @since 2.0 + */ +@Deprecated +public abstract class BaseAbstractUnivariateOptimizer + implements UnivariateOptimizer { + /** Convergence checker. */ + private final ConvergenceChecker<UnivariatePointValuePair> checker; + /** Evaluations counter. */ + private final Incrementor evaluations = new Incrementor(); + /** Optimization type */ + private GoalType goal; + /** Lower end of search interval. */ + private double searchMin; + /** Higher end of search interval. */ + private double searchMax; + /** Initial guess . */ + private double searchStart; + /** Function to optimize. */ + private UnivariateFunction function; + + /** + * @param checker Convergence checking procedure. + */ + protected BaseAbstractUnivariateOptimizer(ConvergenceChecker<UnivariatePointValuePair> checker) { + this.checker = checker; + } + + /** {@inheritDoc} */ + public int getMaxEvaluations() { + return evaluations.getMaximalCount(); + } + + /** {@inheritDoc} */ + public int getEvaluations() { + return evaluations.getCount(); + } + + /** + * @return the optimization type. + */ + public GoalType getGoalType() { + return goal; + } + /** + * @return the lower end of the search interval. + */ + public double getMin() { + return searchMin; + } + /** + * @return the higher end of the search interval. + */ + public double getMax() { + return searchMax; + } + /** + * @return the initial guess. + */ + public double getStartValue() { + return searchStart; + } + + /** + * Compute the objective function value. + * + * @param point Point at which the objective function must be evaluated. + * @return the objective function value at specified point. + * @throws TooManyEvaluationsException if the maximal number of evaluations + * is exceeded. + */ + protected double computeObjectiveValue(double point) { + try { + evaluations.incrementCount(); + } catch (MaxCountExceededException e) { + throw new TooManyEvaluationsException(e.getMax()); + } + return function.value(point); + } + + /** {@inheritDoc} */ + public UnivariatePointValuePair optimize(int maxEval, UnivariateFunction f, + GoalType goalType, + double min, double max, + double startValue) { + // Checks. + if (f == null) { + throw new NullArgumentException(); + } + if (goalType == null) { + throw new NullArgumentException(); + } + + // Reset. + searchMin = min; + searchMax = max; + searchStart = startValue; + goal = goalType; + function = f; + evaluations.setMaximalCount(maxEval); + evaluations.resetCount(); + + // Perform computation. + return doOptimize(); + } + + /** {@inheritDoc} */ + public UnivariatePointValuePair optimize(int maxEval, + UnivariateFunction f, + GoalType goalType, + double min, double max){ + return optimize(maxEval, f, goalType, min, max, min + 0.5 * (max - min)); + } + + /** + * {@inheritDoc} + */ + public ConvergenceChecker<UnivariatePointValuePair> getConvergenceChecker() { + return checker; + } + + /** + * Method for implementing actual optimization algorithms in derived + * classes. + * + * @return the optimum and its corresponding function value. + * @throws TooManyEvaluationsException if the maximal number of evaluations + * is exceeded. + */ + protected abstract UnivariatePointValuePair doOptimize(); +} diff --git a/src/main/java/org/apache/commons/math3/optimization/univariate/BaseUnivariateOptimizer.java b/src/main/java/org/apache/commons/math3/optimization/univariate/BaseUnivariateOptimizer.java new file mode 100644 index 0000000..fcae6f1 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/optimization/univariate/BaseUnivariateOptimizer.java @@ -0,0 +1,86 @@ +/* + * 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.analysis.UnivariateFunction; +import org.apache.commons.math3.optimization.BaseOptimizer; +import org.apache.commons.math3.optimization.GoalType; + +/** + * This interface is mainly intended to enforce the internal coherence of + * Commons-Math. Users of the API are advised to base their code on + * the following interfaces: + * <ul> + * <li>{@link org.apache.commons.math3.optimization.univariate.UnivariateOptimizer}</li> + * </ul> + * + * @param <FUNC> Type of the objective function to be optimized. + * + * @deprecated As of 3.1 (to be removed in 4.0). + * @since 3.0 + */ +@Deprecated +public interface BaseUnivariateOptimizer<FUNC extends UnivariateFunction> + extends BaseOptimizer<UnivariatePointValuePair> { + /** + * Find an optimum in the given interval. + * + * An optimizer may require that the interval brackets a single optimum. + * + * @param f Function to optimize. + * @param goalType Type of optimization goal: either + * {@link GoalType#MAXIMIZE} or {@link GoalType#MINIMIZE}. + * @param min Lower bound for the interval. + * @param max Upper bound for the interval. + * @param maxEval Maximum number of function evaluations. + * @return a (point, value) pair where the function is optimum. + * @throws org.apache.commons.math3.exception.TooManyEvaluationsException + * if the maximum evaluation count is exceeded. + * @throws org.apache.commons.math3.exception.ConvergenceException + * if the optimizer detects a convergence problem. + * @throws IllegalArgumentException if {@code min > max} or the endpoints + * do not satisfy the requirements specified by the optimizer. + */ + UnivariatePointValuePair optimize(int maxEval, FUNC f, GoalType goalType, + double min, double max); + + /** + * Find an optimum in the given interval, start at startValue. + * An optimizer may require that the interval brackets a single optimum. + * + * @param f Function to optimize. + * @param goalType Type of optimization goal: either + * {@link GoalType#MAXIMIZE} or {@link GoalType#MINIMIZE}. + * @param min Lower bound for the interval. + * @param max Upper bound for the interval. + * @param startValue Start value to use. + * @param maxEval Maximum number of function evaluations. + * @return a (point, value) pair where the function is optimum. + * @throws org.apache.commons.math3.exception.TooManyEvaluationsException + * if the maximum evaluation count is exceeded. + * @throws org.apache.commons.math3.exception.ConvergenceException if the + * optimizer detects a convergence problem. + * @throws IllegalArgumentException if {@code min > max} or the endpoints + * do not satisfy the requirements specified by the optimizer. + * @throws org.apache.commons.math3.exception.NullArgumentException if any + * argument is {@code null}. + */ + UnivariatePointValuePair optimize(int maxEval, FUNC f, GoalType goalType, + double min, double max, + double startValue); +} 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); + } +} diff --git a/src/main/java/org/apache/commons/math3/optimization/univariate/BrentOptimizer.java b/src/main/java/org/apache/commons/math3/optimization/univariate/BrentOptimizer.java new file mode 100644 index 0000000..763ec99 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/optimization/univariate/BrentOptimizer.java @@ -0,0 +1,316 @@ +/* + * 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.Precision; +import org.apache.commons.math3.util.FastMath; +import org.apache.commons.math3.exception.NumberIsTooSmallException; +import org.apache.commons.math3.exception.NotStrictlyPositiveException; +import org.apache.commons.math3.optimization.ConvergenceChecker; +import org.apache.commons.math3.optimization.GoalType; + +/** + * For a function defined on some interval {@code (lo, hi)}, this class + * finds an approximation {@code x} to the point at which the function + * attains its minimum. + * It implements Richard Brent's algorithm (from his book "Algorithms for + * Minimization without Derivatives", p. 79) for finding minima of real + * univariate functions. + * <br/> + * This code is an adaptation, partly based on the Python code from SciPy + * (module "optimize.py" v0.5); the original algorithm is also modified + * <ul> + * <li>to use an initial guess provided by the user,</li> + * <li>to ensure that the best point encountered is the one returned.</li> + * </ul> + * + * @deprecated As of 3.1 (to be removed in 4.0). + * @since 2.0 + */ +@Deprecated +public class BrentOptimizer extends BaseAbstractUnivariateOptimizer { + /** + * Golden section. + */ + private static final double GOLDEN_SECTION = 0.5 * (3 - FastMath.sqrt(5)); + /** + * Minimum relative tolerance. + */ + private static final double MIN_RELATIVE_TOLERANCE = 2 * FastMath.ulp(1d); + /** + * Relative threshold. + */ + private final double relativeThreshold; + /** + * Absolute threshold. + */ + private final double absoluteThreshold; + + /** + * The arguments are used implement the original stopping criterion + * of Brent's algorithm. + * {@code abs} and {@code rel} define a tolerance + * {@code tol = rel |x| + abs}. {@code rel} should be no smaller than + * <em>2 macheps</em> and preferably not much less than <em>sqrt(macheps)</em>, + * where <em>macheps</em> is the relative machine precision. {@code abs} must + * be positive. + * + * @param rel Relative threshold. + * @param abs Absolute threshold. + * @param checker Additional, user-defined, convergence checking + * procedure. + * @throws NotStrictlyPositiveException if {@code abs <= 0}. + * @throws NumberIsTooSmallException if {@code rel < 2 * Math.ulp(1d)}. + */ + public BrentOptimizer(double rel, + double abs, + ConvergenceChecker<UnivariatePointValuePair> checker) { + super(checker); + + if (rel < MIN_RELATIVE_TOLERANCE) { + throw new NumberIsTooSmallException(rel, MIN_RELATIVE_TOLERANCE, true); + } + if (abs <= 0) { + throw new NotStrictlyPositiveException(abs); + } + + relativeThreshold = rel; + absoluteThreshold = abs; + } + + /** + * The arguments are used for implementing the original stopping criterion + * of Brent's algorithm. + * {@code abs} and {@code rel} define a tolerance + * {@code tol = rel |x| + abs}. {@code rel} should be no smaller than + * <em>2 macheps</em> and preferably not much less than <em>sqrt(macheps)</em>, + * where <em>macheps</em> is the relative machine precision. {@code abs} must + * be positive. + * + * @param rel Relative threshold. + * @param abs Absolute threshold. + * @throws NotStrictlyPositiveException if {@code abs <= 0}. + * @throws NumberIsTooSmallException if {@code rel < 2 * Math.ulp(1d)}. + */ + public BrentOptimizer(double rel, + double abs) { + this(rel, abs, null); + } + + /** {@inheritDoc} */ + @Override + protected UnivariatePointValuePair doOptimize() { + final boolean isMinim = getGoalType() == GoalType.MINIMIZE; + final double lo = getMin(); + final double mid = getStartValue(); + final double hi = getMax(); + + // Optional additional convergence criteria. + final ConvergenceChecker<UnivariatePointValuePair> checker + = getConvergenceChecker(); + + double a; + double b; + if (lo < hi) { + a = lo; + b = hi; + } else { + a = hi; + b = lo; + } + + double x = mid; + double v = x; + double w = x; + double d = 0; + double e = 0; + double fx = computeObjectiveValue(x); + if (!isMinim) { + fx = -fx; + } + double fv = fx; + double fw = fx; + + UnivariatePointValuePair previous = null; + UnivariatePointValuePair current + = new UnivariatePointValuePair(x, isMinim ? fx : -fx); + // Best point encountered so far (which is the initial guess). + UnivariatePointValuePair best = current; + + int iter = 0; + while (true) { + final double m = 0.5 * (a + b); + final double tol1 = relativeThreshold * FastMath.abs(x) + absoluteThreshold; + final double tol2 = 2 * tol1; + + // Default stopping criterion. + final boolean stop = FastMath.abs(x - m) <= tol2 - 0.5 * (b - a); + if (!stop) { + double p = 0; + double q = 0; + double r = 0; + double u = 0; + + if (FastMath.abs(e) > tol1) { // Fit parabola. + r = (x - w) * (fx - fv); + q = (x - v) * (fx - fw); + p = (x - v) * q - (x - w) * r; + q = 2 * (q - r); + + if (q > 0) { + p = -p; + } else { + q = -q; + } + + r = e; + e = d; + + if (p > q * (a - x) && + p < q * (b - x) && + FastMath.abs(p) < FastMath.abs(0.5 * q * r)) { + // Parabolic interpolation step. + d = p / q; + u = x + d; + + // f must not be evaluated too close to a or b. + if (u - a < tol2 || b - u < tol2) { + if (x <= m) { + d = tol1; + } else { + d = -tol1; + } + } + } else { + // Golden section step. + if (x < m) { + e = b - x; + } else { + e = a - x; + } + d = GOLDEN_SECTION * e; + } + } else { + // Golden section step. + if (x < m) { + e = b - x; + } else { + e = a - x; + } + d = GOLDEN_SECTION * e; + } + + // Update by at least "tol1". + if (FastMath.abs(d) < tol1) { + if (d >= 0) { + u = x + tol1; + } else { + u = x - tol1; + } + } else { + u = x + d; + } + + double fu = computeObjectiveValue(u); + if (!isMinim) { + fu = -fu; + } + + // User-defined convergence checker. + previous = current; + current = new UnivariatePointValuePair(u, isMinim ? fu : -fu); + best = best(best, + best(previous, + current, + isMinim), + isMinim); + + if (checker != null && checker.converged(iter, previous, current)) { + return best; + } + + // Update a, b, v, w and x. + if (fu <= fx) { + if (u < x) { + b = x; + } else { + a = x; + } + v = w; + fv = fw; + w = x; + fw = fx; + x = u; + fx = fu; + } else { + if (u < x) { + a = u; + } else { + b = u; + } + if (fu <= fw || + Precision.equals(w, x)) { + v = w; + fv = fw; + w = u; + fw = fu; + } else if (fu <= fv || + Precision.equals(v, x) || + Precision.equals(v, w)) { + v = u; + fv = fu; + } + } + } else { // Default termination (Brent's criterion). + return best(best, + best(previous, + current, + isMinim), + isMinim); + } + ++iter; + } + } + + /** + * Selects the best of two points. + * + * @param a Point and value. + * @param b Point and value. + * @param isMinim {@code true} if the selected point must be the one with + * the lowest value. + * @return the best point, or {@code null} if {@code a} and {@code b} are + * both {@code null}. When {@code a} and {@code b} have the same function + * value, {@code a} is returned. + */ + private UnivariatePointValuePair best(UnivariatePointValuePair a, + UnivariatePointValuePair b, + boolean isMinim) { + if (a == null) { + return b; + } + if (b == null) { + return a; + } + + if (isMinim) { + return a.getValue() <= b.getValue() ? a : b; + } else { + return a.getValue() >= b.getValue() ? a : b; + } + } +} diff --git a/src/main/java/org/apache/commons/math3/optimization/univariate/SimpleUnivariateValueChecker.java b/src/main/java/org/apache/commons/math3/optimization/univariate/SimpleUnivariateValueChecker.java new file mode 100644 index 0000000..82c50b6 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/optimization/univariate/SimpleUnivariateValueChecker.java @@ -0,0 +1,139 @@ +/* + * 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.exception.NotStrictlyPositiveException; +import org.apache.commons.math3.optimization.AbstractConvergenceChecker; + +/** + * Simple implementation of the + * {@link org.apache.commons.math3.optimization.ConvergenceChecker} interface + * that uses only objective function values. + * + * Convergence is considered to have been reached if either the relative + * difference between the objective function values is smaller than a + * threshold or if either the absolute difference between the objective + * function values is smaller than another threshold. + * <br/> + * The {@link #converged(int,UnivariatePointValuePair,UnivariatePointValuePair) + * converged} method will also return {@code true} if the number of iterations + * has been set (see {@link #SimpleUnivariateValueChecker(double,double,int) + * this constructor}). + * + * @deprecated As of 3.1 (to be removed in 4.0). + * @since 3.1 + */ +@Deprecated +public class SimpleUnivariateValueChecker + extends AbstractConvergenceChecker<UnivariatePointValuePair> { + /** + * If {@link #maxIterationCount} is set to this value, the number of + * iterations will never cause + * {@link #converged(int,UnivariatePointValuePair,UnivariatePointValuePair)} + * to return {@code true}. + */ + private static final int ITERATION_CHECK_DISABLED = -1; + /** + * Number of iterations after which the + * {@link #converged(int,UnivariatePointValuePair,UnivariatePointValuePair)} + * method will return true (unless the check is disabled). + */ + private final int maxIterationCount; + + /** + * Build an instance with default thresholds. + * @deprecated See {@link AbstractConvergenceChecker#AbstractConvergenceChecker()} + */ + @Deprecated + public SimpleUnivariateValueChecker() { + maxIterationCount = ITERATION_CHECK_DISABLED; + } + + /** Build an instance with specified thresholds. + * + * In order to perform only relative checks, the absolute tolerance + * must be set to a negative value. In order to perform only absolute + * checks, the relative tolerance must be set to a negative value. + * + * @param relativeThreshold relative tolerance threshold + * @param absoluteThreshold absolute tolerance threshold + */ + public SimpleUnivariateValueChecker(final double relativeThreshold, + final double absoluteThreshold) { + super(relativeThreshold, absoluteThreshold); + maxIterationCount = ITERATION_CHECK_DISABLED; + } + + /** + * Builds an instance with specified thresholds. + * + * In order to perform only relative checks, the absolute tolerance + * must be set to a negative value. In order to perform only absolute + * checks, the relative tolerance must be set to a negative value. + * + * @param relativeThreshold relative tolerance threshold + * @param absoluteThreshold absolute tolerance threshold + * @param maxIter Maximum iteration count. + * @throws NotStrictlyPositiveException if {@code maxIter <= 0}. + * + * @since 3.1 + */ + public SimpleUnivariateValueChecker(final double relativeThreshold, + final double absoluteThreshold, + final int maxIter) { + super(relativeThreshold, absoluteThreshold); + + if (maxIter <= 0) { + throw new NotStrictlyPositiveException(maxIter); + } + maxIterationCount = maxIter; + } + + /** + * Check if the optimization algorithm has converged considering the + * last two points. + * This method may be called several time from the same algorithm + * iteration with different points. This can be detected by checking the + * iteration number at each call if needed. Each time this method is + * called, the previous and current point correspond to points with the + * same role at each iteration, so they can be compared. As an example, + * simplex-based algorithms call this method for all points of the simplex, + * not only for the best or worst ones. + * + * @param iteration Index of current iteration + * @param previous Best point in the previous iteration. + * @param current Best point in the current iteration. + * @return {@code true} if the algorithm has converged. + */ + @Override + public boolean converged(final int iteration, + final UnivariatePointValuePair previous, + final UnivariatePointValuePair current) { + if (maxIterationCount != ITERATION_CHECK_DISABLED && iteration >= maxIterationCount) { + return true; + } + + final double p = previous.getValue(); + final double c = current.getValue(); + final double difference = FastMath.abs(p - c); + final double size = FastMath.max(FastMath.abs(p), FastMath.abs(c)); + return difference <= size * getRelativeThreshold() || + difference <= getAbsoluteThreshold(); + } +} diff --git a/src/main/java/org/apache/commons/math3/optimization/univariate/UnivariateMultiStartOptimizer.java b/src/main/java/org/apache/commons/math3/optimization/univariate/UnivariateMultiStartOptimizer.java new file mode 100644 index 0000000..f63beb2 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/optimization/univariate/UnivariateMultiStartOptimizer.java @@ -0,0 +1,203 @@ +/* + * 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 java.util.Arrays; +import java.util.Comparator; + +import org.apache.commons.math3.analysis.UnivariateFunction; +import org.apache.commons.math3.exception.MathIllegalStateException; +import org.apache.commons.math3.exception.NotStrictlyPositiveException; +import org.apache.commons.math3.exception.NullArgumentException; +import org.apache.commons.math3.exception.util.LocalizedFormats; +import org.apache.commons.math3.random.RandomGenerator; +import org.apache.commons.math3.optimization.GoalType; +import org.apache.commons.math3.optimization.ConvergenceChecker; + +/** + * Special implementation of the {@link UnivariateOptimizer} interface + * adding multi-start features to an existing optimizer. + * + * This class wraps a classical optimizer to use it several times in + * turn with different starting points in order to avoid being trapped + * into a local extremum when looking for a global one. + * + * @param <FUNC> Type of the objective function to be optimized. + * + * @deprecated As of 3.1 (to be removed in 4.0). + * @since 3.0 + */ +@Deprecated +public class UnivariateMultiStartOptimizer<FUNC extends UnivariateFunction> + implements BaseUnivariateOptimizer<FUNC> { + /** Underlying classical optimizer. */ + private final BaseUnivariateOptimizer<FUNC> optimizer; + /** Maximal number of evaluations allowed. */ + private int maxEvaluations; + /** Number of evaluations already performed for all starts. */ + private int totalEvaluations; + /** Number of starts to go. */ + private int starts; + /** Random generator for multi-start. */ + private RandomGenerator generator; + /** Found optima. */ + private UnivariatePointValuePair[] optima; + + /** + * Create a multi-start optimizer from a single-start optimizer. + * + * @param optimizer Single-start optimizer to wrap. + * @param starts Number of starts to perform. If {@code starts == 1}, + * the {@code optimize} methods will return the same solution as + * {@code optimizer} would. + * @param generator Random generator to use for restarts. + * @throws NullArgumentException if {@code optimizer} or {@code generator} + * is {@code null}. + * @throws NotStrictlyPositiveException if {@code starts < 1}. + */ + public UnivariateMultiStartOptimizer(final BaseUnivariateOptimizer<FUNC> optimizer, + final int starts, + final RandomGenerator generator) { + if (optimizer == null || + generator == null) { + throw new NullArgumentException(); + } + if (starts < 1) { + throw new NotStrictlyPositiveException(starts); + } + + this.optimizer = optimizer; + this.starts = starts; + this.generator = generator; + } + + /** + * {@inheritDoc} + */ + public ConvergenceChecker<UnivariatePointValuePair> getConvergenceChecker() { + return optimizer.getConvergenceChecker(); + } + + /** {@inheritDoc} */ + public int getMaxEvaluations() { + return maxEvaluations; + } + + /** {@inheritDoc} */ + public int getEvaluations() { + return totalEvaluations; + } + + /** + * Get all the optima found during the last call to {@link + * #optimize(int,UnivariateFunction,GoalType,double,double) optimize}. + * The optimizer stores all the optima found during a set of + * restarts. The {@link #optimize(int,UnivariateFunction,GoalType,double,double) optimize} + * method returns the best point only. This method returns all the points + * found at the end of each starts, including the best one already + * returned by the {@link #optimize(int,UnivariateFunction,GoalType,double,double) optimize} + * method. + * <br/> + * The returned array as one element for each start as specified + * in the constructor. It is ordered with the results from the + * runs that did converge first, sorted from best to worst + * objective value (i.e in ascending order if minimizing and in + * descending order if maximizing), followed by {@code null} elements + * corresponding to the runs that did not converge. This means all + * elements will be {@code null} if the {@link + * #optimize(int,UnivariateFunction,GoalType,double,double) optimize} + * method did throw an exception. + * This also means that if the first element is not {@code null}, it is + * the best point found across all starts. + * + * @return an array containing the optima. + * @throws MathIllegalStateException if {@link + * #optimize(int,UnivariateFunction,GoalType,double,double) optimize} + * has not been called. + */ + public UnivariatePointValuePair[] getOptima() { + if (optima == null) { + throw new MathIllegalStateException(LocalizedFormats.NO_OPTIMUM_COMPUTED_YET); + } + return optima.clone(); + } + + /** {@inheritDoc} */ + public UnivariatePointValuePair optimize(int maxEval, final FUNC f, + final GoalType goal, + final double min, final double max) { + return optimize(maxEval, f, goal, min, max, min + 0.5 * (max - min)); + } + + /** {@inheritDoc} */ + public UnivariatePointValuePair optimize(int maxEval, final FUNC f, + final GoalType goal, + final double min, final double max, + final double startValue) { + RuntimeException lastException = null; + optima = new UnivariatePointValuePair[starts]; + totalEvaluations = 0; + + // Multi-start loop. + for (int i = 0; i < starts; ++i) { + // CHECKSTYLE: stop IllegalCatch + try { + final double s = (i == 0) ? startValue : min + generator.nextDouble() * (max - min); + optima[i] = optimizer.optimize(maxEval - totalEvaluations, f, goal, min, max, s); + } catch (RuntimeException mue) { + lastException = mue; + optima[i] = null; + } + // CHECKSTYLE: resume IllegalCatch + + totalEvaluations += optimizer.getEvaluations(); + } + + sortPairs(goal); + + if (optima[0] == null) { + throw lastException; // cannot be null if starts >=1 + } + + // Return the point with the best objective function value. + return optima[0]; + } + + /** + * Sort the optima from best to worst, followed by {@code null} elements. + * + * @param goal Goal type. + */ + private void sortPairs(final GoalType goal) { + Arrays.sort(optima, new Comparator<UnivariatePointValuePair>() { + /** {@inheritDoc} */ + public int compare(final UnivariatePointValuePair o1, + final UnivariatePointValuePair o2) { + if (o1 == null) { + return (o2 == null) ? 0 : 1; + } else if (o2 == null) { + return -1; + } + final double v1 = o1.getValue(); + final double v2 = o2.getValue(); + return (goal == GoalType.MINIMIZE) ? + Double.compare(v1, v2) : Double.compare(v2, v1); + } + }); + } +} diff --git a/src/main/java/org/apache/commons/math3/optimization/univariate/UnivariateOptimizer.java b/src/main/java/org/apache/commons/math3/optimization/univariate/UnivariateOptimizer.java new file mode 100644 index 0000000..e3ebbb3 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/optimization/univariate/UnivariateOptimizer.java @@ -0,0 +1,29 @@ +/* + * 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.analysis.UnivariateFunction; + +/** + * Interface for univariate optimization algorithms. + * + * @deprecated As of 3.1 (to be removed in 4.0). + * @since 3.0 + */ +@Deprecated +public interface UnivariateOptimizer + extends BaseUnivariateOptimizer<UnivariateFunction> {} diff --git a/src/main/java/org/apache/commons/math3/optimization/univariate/UnivariatePointValuePair.java b/src/main/java/org/apache/commons/math3/optimization/univariate/UnivariatePointValuePair.java new file mode 100644 index 0000000..eee931c --- /dev/null +++ b/src/main/java/org/apache/commons/math3/optimization/univariate/UnivariatePointValuePair.java @@ -0,0 +1,68 @@ +/* + * 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 java.io.Serializable; + +/** + * This class holds a point and the value of an objective function at this + * point. + * This is a simple immutable container. + * + * @deprecated As of 3.1 (to be removed in 4.0). + * @since 3.0 + */ +@Deprecated +public class UnivariatePointValuePair implements Serializable { + /** Serializable version identifier. */ + private static final long serialVersionUID = 1003888396256744753L; + /** Point. */ + private final double point; + /** Value of the objective function at the point. */ + private final double value; + + /** + * Build a point/objective function value pair. + * + * @param point Point. + * @param value Value of an objective function at the point + */ + public UnivariatePointValuePair(final double point, + final double value) { + this.point = point; + this.value = value; + } + + /** + * Get the point. + * + * @return the point. + */ + public double getPoint() { + return point; + } + + /** + * Get the value of the objective function. + * + * @return the stored value of the objective function. + */ + public double getValue() { + return value; + } +} diff --git a/src/main/java/org/apache/commons/math3/optimization/univariate/package-info.java b/src/main/java/org/apache/commons/math3/optimization/univariate/package-info.java new file mode 100644 index 0000000..04feb33 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/optimization/univariate/package-info.java @@ -0,0 +1,22 @@ +/* + * 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. + */ +/** + * + * Univariate real functions minimum finding algorithms. + * + */ +package org.apache.commons.math3.optimization.univariate; |