This is an automated email from the ASF dual-hosted git repository. erans pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/commons-math.git
The following commit(s) were added to refs/heads/master by this push: new aaa39b8fd MATH-1666: Hide "LineSearch". new d961ff2f4 Merge branch 'master' of https://gitbox.apache.org/repos/asf/commons-math aaa39b8fd is described below commit aaa39b8fd5a2b1dbe4e883e027e932aa8703e55d Author: Gilles Sadowski <gillese...@gmail.com> AuthorDate: Wed Nov 22 02:25:27 2023 +0100 MATH-1666: Hide "LineSearch". --- .../commons/math4/legacy/optim/BaseOptimizer.java | 27 +++- .../commons/math4/legacy/optim/Tolerance.java | 53 +++++++ .../legacy/optim/nonlinear/scalar/LineSearch.java | 5 + .../nonlinear/scalar/LineSearchTolerance.java | 56 +++++++ .../nonlinear/scalar/MultivariateOptimizer.java | 164 ++++++++++++++++++++- .../NonLinearConjugateGradientOptimizer.java | 59 +------- .../nonlinear/scalar/noderiv/PowellOptimizer.java | 35 ++--- .../MultiStartMultivariateOptimizerTest.java | 12 +- .../NonLinearConjugateGradientOptimizerTest.java | 77 +++++----- 9 files changed, 368 insertions(+), 120 deletions(-) diff --git a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/BaseOptimizer.java b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/BaseOptimizer.java index 3e16d7b28..bd1f938e2 100644 --- a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/BaseOptimizer.java +++ b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/BaseOptimizer.java @@ -23,8 +23,10 @@ import org.apache.commons.math4.legacy.core.IntegerSequence; /** * Base class for implementing optimizers. * It contains the boiler-plate code for counting the number of evaluations - * of the objective function and the number of iterations of the algorithm, - * and storing the convergence checker. + * of the objective function and the number of iterations of the algorithm. + * It also stores a {@link ConvergenceChecker convergence checker}, as well + * as {@link Tolerance default tolerances} (how the checker and tolerances + * are used is determined by subclasses). * <em>It is not a "user" class.</em> * * @param <PAIR> Type of the point/value pair returned by the optimization @@ -48,6 +50,10 @@ public abstract class BaseOptimizer<PAIR> { private IntegerSequence.Incrementor evaluations; /** Iterations counter. */ private IntegerSequence.Incrementor iterations; + /** Relative tolerance. */ + private double relativeTolerance = 1e-6; + /** Absolute tolerance. */ + private double absoluteTolerance = 1e-6; /** * @param checker Convergence checker. @@ -69,6 +75,16 @@ public abstract class BaseOptimizer<PAIR> { this.maxIterations = maxIter; } + /** @return the relative tolerance. */ + protected double getRelativeTolerance() { + return relativeTolerance; + } + + /** @return the absolute tolerance. */ + protected double getAbsoluteTolerance() { + return absoluteTolerance; + } + /** * Gets the maximal number of function evaluations. * @@ -142,6 +158,7 @@ public abstract class BaseOptimizer<PAIR> { * <li>{@link MaxEval}</li> * <li>{@link MaxIter}</li> * <li>{@link ConvergenceChecker}</li> + * <li>{@link Tolerance}</li> * </ul> * @return a point/value pair that satisfies the convergence criteria. * @throws TooManyEvaluationsException if the maximal number of @@ -230,6 +247,12 @@ public abstract class BaseOptimizer<PAIR> { checker = (ConvergenceChecker<PAIR>) data; continue; } + if (data instanceof Tolerance) { + final Tolerance tol = (Tolerance) data; + relativeTolerance = tol.getRelativeTolerance(); + absoluteTolerance = tol.getAbsoluteTolerance(); + continue; + } } } diff --git a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/Tolerance.java b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/Tolerance.java new file mode 100644 index 000000000..de115cf28 --- /dev/null +++ b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/Tolerance.java @@ -0,0 +1,53 @@ +/* + * 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.math4.legacy.optim; + +/** + * Default tolerances values. + * + * @since 4.0 + */ +public class Tolerance implements OptimizationData { + /** Relative tolerance. */ + private final double relativeTolerance; + /** Absolute tolerance. */ + private final double absoluteTolerance; + + /** + * @param relative Relative tolerance. + * @param absolute Abolute tolerance. + */ + public Tolerance(double relative, + double absolute) { + relativeTolerance = relative; + absoluteTolerance = absolute; + } + + /** + * @return the retlative tolerance. + */ + public double getRelativeTolerance() { + return relativeTolerance; + } + + /** + * @return the absolute tolerance. + */ + public double getAbsoluteTolerance() { + return absoluteTolerance; + } +} diff --git a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/LineSearch.java b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/LineSearch.java index 6e674c364..0cc8e5931 100644 --- a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/LineSearch.java +++ b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/LineSearch.java @@ -32,7 +32,12 @@ import org.apache.commons.math4.legacy.optim.univariate.UnivariatePointValuePair * direction. * * @since 3.3 + * @deprecated as of 4.0-beta2. + * Class is now encapsulated in {@link MultivariateOptimizer}. + * Subclasses should call {@link MultivariateOptimizer#createLineSearch()} + * and {@link MultivariateOptimizer#lineSearch(double[],double[])} instead. */ +@Deprecated public class LineSearch { /** * Value that will pass the precondition check for {@link BrentOptimizer} diff --git a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/LineSearchTolerance.java b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/LineSearchTolerance.java new file mode 100644 index 000000000..e6df1e784 --- /dev/null +++ b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/LineSearchTolerance.java @@ -0,0 +1,56 @@ +/* + * 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.math4.legacy.optim.nonlinear.scalar; + +import org.apache.commons.math4.legacy.exception.NotStrictlyPositiveException; +import org.apache.commons.math4.legacy.optim.Tolerance; + +/** + * Tolerances for line search. + * + * @since 4.0 + */ +public class LineSearchTolerance extends Tolerance { + /** Range. */ + private final double initialBracketingRange; + + /** + * @param relative Relative tolerance. + * @param absolute Absolute tolerance. + * @param range Extent of the initial interval used to find an interval + * that brackets the optimum. + * If the optimized function varies a lot in the vicinity of the optimum, + * it may be necessary to provide a value lower than the distance between + * successive local minima. + */ + public LineSearchTolerance(double relative, + double absolute, + double range) { + super(relative, absolute); + + if (range <= 0) { + throw new NotStrictlyPositiveException(range); + } + + initialBracketingRange = range; + } + + /** @return the initial bracketing range. */ + public double getInitialBracketingRange() { + return initialBracketingRange; + } +} diff --git a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/MultivariateOptimizer.java b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/MultivariateOptimizer.java index 2cd72d83b..35a954bff 100644 --- a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/MultivariateOptimizer.java +++ b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/MultivariateOptimizer.java @@ -17,10 +17,19 @@ package org.apache.commons.math4.legacy.optim.nonlinear.scalar; import org.apache.commons.math4.legacy.analysis.MultivariateFunction; +import org.apache.commons.math4.legacy.analysis.UnivariateFunction; import org.apache.commons.math4.legacy.optim.BaseMultivariateOptimizer; import org.apache.commons.math4.legacy.optim.ConvergenceChecker; import org.apache.commons.math4.legacy.optim.OptimizationData; import org.apache.commons.math4.legacy.optim.PointValuePair; +import org.apache.commons.math4.legacy.optim.MaxEval; +import org.apache.commons.math4.legacy.optim.univariate.BracketFinder; +import org.apache.commons.math4.legacy.optim.univariate.BrentOptimizer; +import org.apache.commons.math4.legacy.optim.univariate.SearchInterval; +import org.apache.commons.math4.legacy.optim.univariate.SimpleUnivariateValueChecker; +import org.apache.commons.math4.legacy.optim.univariate.UnivariateObjectiveFunction; +import org.apache.commons.math4.legacy.optim.univariate.UnivariateOptimizer; +import org.apache.commons.math4.legacy.optim.univariate.UnivariatePointValuePair; /** * Base class for a multivariate scalar function optimizer. @@ -33,6 +42,14 @@ public abstract class MultivariateOptimizer private MultivariateFunction function; /** Type of optimization. */ private GoalType goal; + /** Line search relative tolerance. */ + private double lineSearchRelativeTolerance = 1e-8; + /** Line search absolute tolerance. */ + private double lineSearchAbsoluteTolerance = 1e-8; + /** Line serach initial bracketing range. */ + private double lineSearchInitialBracketingRange = 1d; + /** Line search. */ + private LineSearch lineSearch; /** * @param checker Convergence checker. @@ -50,6 +67,7 @@ public abstract class MultivariateOptimizer * <ul> * <li>{@link ObjectiveFunction}</li> * <li>{@link GoalType}</li> + * <li>{@link LineSearchTolerance}</li> * </ul> * @return {@inheritDoc} * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException @@ -70,6 +88,7 @@ public abstract class MultivariateOptimizer * <ul> * <li>{@link ObjectiveFunction}</li> * <li>{@link GoalType}</li> + * <li>{@link LineSearchTolerance}</li> * </ul> */ @Override @@ -95,13 +114,45 @@ public abstract class MultivariateOptimizer }; continue; } + if (data instanceof LineSearchTolerance) { + final LineSearchTolerance tol = (LineSearchTolerance) data; + lineSearchRelativeTolerance = tol.getRelativeTolerance(); + lineSearchAbsoluteTolerance = tol.getAbsoluteTolerance(); + lineSearchInitialBracketingRange = tol.getInitialBracketingRange(); + continue; + } } } + /** + * Intantiate the line search implementation. + */ + protected void createLineSearch() { + lineSearch = new LineSearch(this, + lineSearchRelativeTolerance, + lineSearchAbsoluteTolerance, + lineSearchInitialBracketingRange); + } + + /** + * Finds the number {@code alpha} that optimizes + * {@code f(startPoint + alpha * direction)}. + * + * @param startPoint Starting point. + * @param direction Search direction. + * @return the optimum. + * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException + * if the number of evaluations is exceeded. + */ + protected UnivariatePointValuePair lineSearch(final double[] startPoint, + final double[] direction) { + return lineSearch.search(startPoint, direction); + } + /** * @return the optimization type. */ - public GoalType getGoalType() { + protected GoalType getGoalType() { return goal; } @@ -129,4 +180,115 @@ public abstract class MultivariateOptimizer public double computeObjectiveValue(double[] params) { return function.value(params); } + + /** + * Find the minimum of the objective function along a given direction. + * + * @since 4.0 + */ + private static class LineSearch { + /** + * Value that will pass the precondition check for {@link BrentOptimizer} + * but will not pass the convergence check, so that the custom checker + * will always decide when to stop the line search. + */ + private static final double REL_TOL_UNUSED = 1e-15; + /** + * Value that will pass the precondition check for {@link BrentOptimizer} + * but will not pass the convergence check, so that the custom checker + * will always decide when to stop the line search. + */ + private static final double ABS_TOL_UNUSED = Double.MIN_VALUE; + /** + * Optimizer used for line search. + */ + private final UnivariateOptimizer lineOptimizer; + /** + * Automatic bracketing. + */ + private final BracketFinder bracket = new BracketFinder(); + /** + * Extent of the initial interval used to find an interval that + * brackets the optimum. + */ + private final double initialBracketingRange; + /** + * Optimizer on behalf of which the line search must be performed. + */ + private final MultivariateOptimizer mainOptimizer; + + /** + * The {@code BrentOptimizer} default stopping criterion uses the + * tolerances to check the domain (point) values, not the function + * values. + * The {@code relativeTolerance} and {@code absoluteTolerance} + * arguments are thus passed to a {@link SimpleUnivariateValueChecker + * custom checker} that will use the function values. + * + * @param optimizer Optimizer on behalf of which the line search + * be performed. + * Its {@link MultivariateOptimizer#getObjectiveFunction() objective + * function} will be called by the {@link #search(double[],double[]) + * search} method. + * @param relativeTolerance Search will stop when the function relative + * difference between successive iterations is below this value. + * @param absoluteTolerance Search will stop when the function absolute + * difference between successive iterations is below this value. + * @param initialBracketingRange Extent of the initial interval used to + * find an interval that brackets the optimum. + * If the optimized function varies a lot in the vicinity of the optimum, + * it may be necessary to provide a value lower than the distance between + * successive local minima. + */ + /* package-private */ LineSearch(MultivariateOptimizer optimizer, + double relativeTolerance, + double absoluteTolerance, + double initialBracketingRange) { + mainOptimizer = optimizer; + lineOptimizer = new BrentOptimizer(REL_TOL_UNUSED, + ABS_TOL_UNUSED, + new SimpleUnivariateValueChecker(relativeTolerance, + absoluteTolerance)); + this.initialBracketingRange = initialBracketingRange; + } + + /** + * Finds the number {@code alpha} that optimizes + * {@code f(startPoint + alpha * direction)}. + * + * @param startPoint Starting point. + * @param direction Search direction. + * @return the optimum. + * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException + * if the number of evaluations is exceeded. + */ + /* package-private */ UnivariatePointValuePair search(final double[] startPoint, + final double[] direction) { + final int n = startPoint.length; + final MultivariateFunction func = mainOptimizer.getObjectiveFunction(); + final UnivariateFunction f = new UnivariateFunction() { + /** {@inheritDoc} */ + @Override + public double value(double alpha) { + final double[] x = new double[n]; + for (int i = 0; i < n; i++) { + x[i] = startPoint[i] + alpha * direction[i]; + } + return func.value(x); + } + }; + + final GoalType goal = mainOptimizer.getGoalType(); + bracket.search(f, goal, 0, initialBracketingRange); + // Passing "MAX_VALUE" as a dummy value because it is the enclosing + // class that counts the number of evaluations (and will eventually + // generate the exception). + return lineOptimizer.optimize(new MaxEval(Integer.MAX_VALUE), + new UnivariateObjectiveFunction(f), + goal, + new SearchInterval(bracket.getLo(), + bracket.getHi(), + bracket.getMid())); + } + } } diff --git a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/gradient/NonLinearConjugateGradientOptimizer.java b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/gradient/NonLinearConjugateGradientOptimizer.java index f22eaf309..3589fd0f4 100644 --- a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/gradient/NonLinearConjugateGradientOptimizer.java +++ b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/gradient/NonLinearConjugateGradientOptimizer.java @@ -27,8 +27,6 @@ import org.apache.commons.math4.legacy.optim.OptimizationData; import org.apache.commons.math4.legacy.optim.PointValuePair; import org.apache.commons.math4.legacy.optim.nonlinear.scalar.GoalType; import org.apache.commons.math4.legacy.optim.nonlinear.scalar.GradientMultivariateOptimizer; -import org.apache.commons.math4.legacy.optim.nonlinear.scalar.LineSearch; - /** * Non-linear conjugate gradient optimizer. @@ -37,6 +35,8 @@ import org.apache.commons.math4.legacy.optim.nonlinear.scalar.LineSearch; * update formulas for the conjugate search directions. * It also supports optional preconditioning. * <br> + * Line search must be setup via {@link org.apache.commons.math4.legacy.optim.nonlinear.scalar.LineSearchTolerance}. + * <br> * Constraints are not supported: the call to * {@link #optimize(OptimizationData[]) optimize} will throw * {@link MathUnsupportedOperationException} if bounds are passed to it. @@ -49,8 +49,6 @@ public class NonLinearConjugateGradientOptimizer private final Formula updateFormula; /** Preconditioner (may be null). */ private final Preconditioner preconditioner; - /** Line search algorithm. */ - private final LineSearch line; /** * Available choices of update formulas for the updating the parameter @@ -77,25 +75,6 @@ public class NonLinearConjugateGradientOptimizer POLAK_RIBIERE } - /** - * Constructor with default tolerances for the line search (1e-8) and - * {@link IdentityPreconditioner preconditioner}. - * - * @param updateFormula formula to use for updating the β parameter, - * must be one of {@link Formula#FLETCHER_REEVES} or - * {@link Formula#POLAK_RIBIERE}. - * @param checker Convergence checker. - */ - public NonLinearConjugateGradientOptimizer(final Formula updateFormula, - ConvergenceChecker<PointValuePair> checker) { - this(updateFormula, - checker, - 1e-8, - 1e-8, - 1e-8, - new IdentityPreconditioner()); - } - /** * Constructor with default {@link IdentityPreconditioner preconditioner}. * @@ -103,25 +82,13 @@ public class NonLinearConjugateGradientOptimizer * must be one of {@link Formula#FLETCHER_REEVES} or * {@link Formula#POLAK_RIBIERE}. * @param checker Convergence checker. - * @param relativeTolerance Relative threshold for line search. - * @param absoluteTolerance Absolute threshold for line search. - * @param initialBracketingRange Extent of the initial interval used to - * find an interval that brackets the optimum in order to perform the - * line search. * - * @see LineSearch#LineSearch(org.apache.commons.math4.legacy.optim.nonlinear.scalar.MultivariateOptimizer,double,double,double) * @since 3.3 */ public NonLinearConjugateGradientOptimizer(final Formula updateFormula, - ConvergenceChecker<PointValuePair> checker, - double relativeTolerance, - double absoluteTolerance, - double initialBracketingRange) { + ConvergenceChecker<PointValuePair> checker) { this(updateFormula, checker, - relativeTolerance, - absoluteTolerance, - initialBracketingRange, new IdentityPreconditioner()); } @@ -131,29 +98,16 @@ public class NonLinearConjugateGradientOptimizer * {@link Formula#POLAK_RIBIERE}. * @param checker Convergence checker. * @param preconditioner Preconditioner. - * @param relativeTolerance Relative threshold for line search. - * @param absoluteTolerance Absolute threshold for line search. - * @param initialBracketingRange Extent of the initial interval used to - * find an interval that brackets the optimum in order to perform the - * line search. * - * @see LineSearch#LineSearch(org.apache.commons.math4.legacy.optim.nonlinear.scalar.MultivariateOptimizer, double, double, double) * @since 3.3 */ public NonLinearConjugateGradientOptimizer(final Formula updateFormula, ConvergenceChecker<PointValuePair> checker, - double relativeTolerance, - double absoluteTolerance, - double initialBracketingRange, final Preconditioner preconditioner) { super(checker); this.updateFormula = updateFormula; this.preconditioner = preconditioner; - line = new LineSearch(this, - relativeTolerance, - absoluteTolerance, - initialBracketingRange); } /** @@ -190,6 +144,8 @@ public class NonLinearConjugateGradientOptimizer delta += r[i] * searchDirection[i]; } + createLineSearch(); + PointValuePair current = null; while (true) { incrementIterationCount(); @@ -197,12 +153,13 @@ public class NonLinearConjugateGradientOptimizer final double objective = func.value(point); PointValuePair previous = current; current = new PointValuePair(point, objective); - if (previous != null && checker.converged(getIterations(), previous, current)) { + if (previous != null && + checker.converged(getIterations(), previous, current)) { // We have found an optimum. return current; } - final double step = line.search(point, searchDirection).getPoint(); + final double step = lineSearch(point, searchDirection).getPoint(); // Validate new point. for (int i = 0; i < point.length; ++i) { diff --git a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/noderiv/PowellOptimizer.java b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/noderiv/PowellOptimizer.java index 405c70349..62cc2c745 100644 --- a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/noderiv/PowellOptimizer.java +++ b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/noderiv/PowellOptimizer.java @@ -25,7 +25,6 @@ import org.apache.commons.math4.legacy.exception.util.LocalizedFormats; import org.apache.commons.math4.legacy.optim.ConvergenceChecker; import org.apache.commons.math4.legacy.optim.PointValuePair; import org.apache.commons.math4.legacy.optim.nonlinear.scalar.GoalType; -import org.apache.commons.math4.legacy.optim.nonlinear.scalar.LineSearch; import org.apache.commons.math4.legacy.optim.nonlinear.scalar.MultivariateOptimizer; import org.apache.commons.math4.legacy.optim.univariate.UnivariatePointValuePair; import org.apache.commons.math4.core.jdkmath.JdkMath; @@ -41,8 +40,6 @@ import org.apache.commons.math4.core.jdkmath.JdkMath; * to define a custom convergence checker that might terminate the algorithm * earlier. * <br> - * Line search is performed by the {@link LineSearch} class. - * <br> * Constraints are not supported: the call to * {@link #optimize(org.apache.commons.math4.legacy.optim.OptimizationData...)} will throw * {@link MathUnsupportedOperationException} if bounds are passed to it. @@ -61,18 +58,14 @@ public class PowellOptimizer * Minimum relative tolerance. */ private static final double MIN_RELATIVE_TOLERANCE = 2 * JdkMath.ulp(1d); - /** - * Relative threshold. - */ + /** Relative threshold. */ private final double relativeThreshold; - /** - * Absolute threshold. - */ + /** Absolute threshold. */ private final double absoluteThreshold; - /** - * Line search. - */ - private final LineSearch line; + /** Relative threshold. */ + private final double lineSearchRelativeThreshold; + /** Absolute threshold. */ + private final double lineSearchAbsoluteThreshold; /** * This constructor allows to specify a user-defined convergence checker, @@ -120,14 +113,11 @@ public class PowellOptimizer if (abs <= 0) { throw new NotStrictlyPositiveException(abs); } + relativeThreshold = rel; absoluteThreshold = abs; - - // Create the line search optimizer. - line = new LineSearch(this, - lineRel, - lineAbs, - 1d); + lineSearchRelativeThreshold = lineRel; + lineSearchAbsoluteThreshold = lineAbs; } /** @@ -168,6 +158,9 @@ public class PowellOptimizer protected PointValuePair doOptimize() { checkParameters(); + // Line search optimizer. + createLineSearch(); + final GoalType goal = getGoalType(); final double[] guess = getStartPoint(); final MultivariateFunction func = getObjectiveFunction(); @@ -198,7 +191,7 @@ public class PowellOptimizer fX2 = fVal; - final UnivariatePointValuePair optimum = line.search(x, d); + final UnivariatePointValuePair optimum = lineSearch(x, d); fVal = optimum.getValue(); alphaMin = optimum.getPoint(); final double[][] result = newPointAndDirection(x, d, alphaMin); @@ -246,7 +239,7 @@ public class PowellOptimizer t -= delta * temp * temp; if (t < 0.0) { - final UnivariatePointValuePair optimum = line.search(x, d); + final UnivariatePointValuePair optimum = lineSearch(x, d); fVal = optimum.getValue(); alphaMin = optimum.getPoint(); final double[][] result = newPointAndDirection(x, d, alphaMin); diff --git a/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/MultiStartMultivariateOptimizerTest.java b/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/MultiStartMultivariateOptimizerTest.java index 2e1137248..114c48cc7 100644 --- a/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/MultiStartMultivariateOptimizerTest.java +++ b/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/MultiStartMultivariateOptimizerTest.java @@ -44,10 +44,7 @@ public class MultiStartMultivariateOptimizerTest { circle.addPoint(110.0, -20.0); circle.addPoint( 35.0, 15.0); circle.addPoint( 45.0, 97.0); - // TODO: the wrapper around NonLinearConjugateGradientOptimizer is a temporary hack for - // version 3.1 of the library. It should be removed when NonLinearConjugateGradientOptimizer - // will officially be declared as implementing MultivariateDifferentiableOptimizer - GradientMultivariateOptimizer underlying + final GradientMultivariateOptimizer underlying = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE, new SimpleValueChecker(1e-10, 1e-10)); final Supplier<double[]> generator = gaussianRandom(new double[] { 50, 50 }, @@ -62,12 +59,13 @@ public class MultiStartMultivariateOptimizerTest { circle.getObjectiveFunctionGradient(), new NelderMeadTransform(), GoalType.MINIMIZE, - new InitialGuess(new double[] { 98.680, 47.345 })); + new InitialGuess(new double[] { 98.680, 47.345 }), + new LineSearchTolerance(1e-10, 1e-10, 1)); Assert.assertEquals(1000, optimizer.getMaxEvaluations()); - PointValuePair[] optima = optimizer.getOptima(); + final PointValuePair[] optima = optimizer.getOptima(); Assert.assertEquals(nbStarts, optima.length); for (PointValuePair o : optima) { - // we check the results of all intermediate restarts here (there are 10 such results) + // Check the results of all intermediate restarts. Vector2D center = Vector2D.of(o.getPointRef()[0], o.getPointRef()[1]); Assert.assertEquals(69.9597, circle.getRadius(center), 1e-3); Assert.assertEquals(96.07535, center.getX(), 1.4e-3); diff --git a/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/gradient/NonLinearConjugateGradientOptimizerTest.java b/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/gradient/NonLinearConjugateGradientOptimizerTest.java index 9864fcb3d..29820c21b 100644 --- a/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/gradient/NonLinearConjugateGradientOptimizerTest.java +++ b/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/gradient/NonLinearConjugateGradientOptimizerTest.java @@ -31,6 +31,7 @@ import org.apache.commons.math4.legacy.optim.SimpleValueChecker; import org.apache.commons.math4.legacy.optim.nonlinear.scalar.GoalType; import org.apache.commons.math4.legacy.optim.nonlinear.scalar.ObjectiveFunction; import org.apache.commons.math4.legacy.optim.nonlinear.scalar.ObjectiveFunctionGradient; +import org.apache.commons.math4.legacy.optim.nonlinear.scalar.LineSearchTolerance; import org.junit.Assert; import org.junit.Test; @@ -104,15 +105,15 @@ public class NonLinearConjugateGradientOptimizerTest { = new LinearProblem(new double[][] { { 2 } }, new double[] { 3 }); NonLinearConjugateGradientOptimizer optimizer = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE, - new SimpleValueChecker(1e-6, 1e-6), - 1e-3, 1e-3, 1); + new SimpleValueChecker(1e-6, 1e-6)); optimizer.optimize(new MaxEval(100), problem.getObjectiveFunction(), problem.getObjectiveFunctionGradient(), GoalType.MINIMIZE, new InitialGuess(new double[] { 0 }), new SimpleBounds(new double[] { -1 }, - new double[] { 1 })); + new double[] { 1 }), + new LineSearchTolerance(1e-3, 1e-3, 1)); } @Test @@ -121,14 +122,14 @@ public class NonLinearConjugateGradientOptimizerTest { = new LinearProblem(new double[][] { { 2 } }, new double[] { 3 }); NonLinearConjugateGradientOptimizer optimizer = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE, - new SimpleValueChecker(1e-6, 1e-6), - 1e-3, 1e-3, 1); + new SimpleValueChecker(1e-6, 1e-6)); PointValuePair optimum = optimizer.optimize(new MaxEval(100), problem.getObjectiveFunction(), problem.getObjectiveFunctionGradient(), GoalType.MINIMIZE, - new InitialGuess(new double[] { 0 })); + new InitialGuess(new double[] { 0 }), + new LineSearchTolerance(1e-3, 1e-3, 1)); Assert.assertEquals(1.5, optimum.getPoint()[0], 1.0e-10); Assert.assertEquals(0.0, optimum.getValue(), 1.0e-10); @@ -144,14 +145,14 @@ public class NonLinearConjugateGradientOptimizerTest { NonLinearConjugateGradientOptimizer optimizer = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE, - new SimpleValueChecker(1e-6, 1e-6), - 1e-3, 1e-3, 1); + new SimpleValueChecker(1e-6, 1e-6)); PointValuePair optimum = optimizer.optimize(new MaxEval(100), problem.getObjectiveFunction(), problem.getObjectiveFunctionGradient(), GoalType.MINIMIZE, - new InitialGuess(new double[] { 0, 0 })); + new InitialGuess(new double[] { 0, 0 }), + new LineSearchTolerance(1e-3, 1e-3, 1)); Assert.assertEquals(7.0, optimum.getPoint()[0], 1.0e-10); Assert.assertEquals(3.0, optimum.getPoint()[1], 1.0e-10); Assert.assertEquals(0.0, optimum.getValue(), 1.0e-10); @@ -169,14 +170,14 @@ public class NonLinearConjugateGradientOptimizerTest { }, new double[] { 0.0, 1.1, 2.2, 3.3, 4.4, 5.5 }); NonLinearConjugateGradientOptimizer optimizer = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE, - new SimpleValueChecker(1e-6, 1e-6), - 1e-3, 1e-3, 1); + new SimpleValueChecker(1e-6, 1e-6)); PointValuePair optimum = optimizer.optimize(new MaxEval(100), problem.getObjectiveFunction(), problem.getObjectiveFunctionGradient(), GoalType.MINIMIZE, - new InitialGuess(new double[] { 0, 0, 0, 0, 0, 0 })); + new InitialGuess(new double[] { 0, 0, 0, 0, 0, 0 }), + new LineSearchTolerance(1e-3, 1e-3, 1)); for (int i = 0; i < problem.target.length; ++i) { Assert.assertEquals(0.55 * i, optimum.getPoint()[i], 1.0e-10); } @@ -191,14 +192,14 @@ public class NonLinearConjugateGradientOptimizerTest { }, new double[] { 1, 1, 1}); NonLinearConjugateGradientOptimizer optimizer = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE, - new SimpleValueChecker(1e-6, 1e-6), - 1e-3, 1e-3, 1); + new SimpleValueChecker(1e-6, 1e-6)); PointValuePair optimum = optimizer.optimize(new MaxEval(100), problem.getObjectiveFunction(), problem.getObjectiveFunctionGradient(), GoalType.MINIMIZE, - new InitialGuess(new double[] { 0, 0, 0 })); + new InitialGuess(new double[] { 0, 0, 0 }), + new LineSearchTolerance(1e-3, 1e-3, 1)); Assert.assertEquals(1.0, optimum.getPoint()[0], 1.0e-10); Assert.assertEquals(2.0, optimum.getPoint()[1], 1.0e-10); Assert.assertEquals(3.0, optimum.getPoint()[2], 1.0e-10); @@ -234,7 +235,6 @@ public class NonLinearConjugateGradientOptimizerTest { NonLinearConjugateGradientOptimizer optimizer = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE, new SimpleValueChecker(1e-13, 1e-13), - 1e-7, 1e-7, 1, preconditioner); PointValuePair optimum @@ -242,7 +242,8 @@ public class NonLinearConjugateGradientOptimizerTest { problem.getObjectiveFunction(), problem.getObjectiveFunctionGradient(), GoalType.MINIMIZE, - new InitialGuess(new double[] { 0, 0, 0, 0, 0, 0 })); + new InitialGuess(new double[] { 0, 0, 0, 0, 0, 0 }), + new LineSearchTolerance(1e-7, 1e-7, 1)); final double[] result = optimum.getPoint(); final double[] expected = {3, 4, -1, -2, 1 + epsilon, 1 - epsilon}; @@ -264,14 +265,14 @@ public class NonLinearConjugateGradientOptimizerTest { }, new double[] { 1, 1, 1 }); NonLinearConjugateGradientOptimizer optimizer = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE, - new SimpleValueChecker(1e-6, 1e-6), - 1e-3, 1e-3, 1); + new SimpleValueChecker(1e-6, 1e-6)); PointValuePair optimum = optimizer.optimize(new MaxEval(100), problem.getObjectiveFunction(), problem.getObjectiveFunctionGradient(), GoalType.MINIMIZE, - new InitialGuess(new double[] { 0, 0, 0 })); + new InitialGuess(new double[] { 0, 0, 0 }), + new LineSearchTolerance(1e-3, 1e-3, 1)); Assert.assertTrue(optimum.getValue() > 0.5); } @@ -285,14 +286,14 @@ public class NonLinearConjugateGradientOptimizerTest { }, new double[] { 32, 23, 33, 31 }); NonLinearConjugateGradientOptimizer optimizer = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE, - new SimpleValueChecker(1e-13, 1e-13), - 1e-15, 1e-15, 1); + new SimpleValueChecker(1e-13, 1e-13)); PointValuePair optimum1 = optimizer.optimize(new MaxEval(200), problem1.getObjectiveFunction(), problem1.getObjectiveFunctionGradient(), GoalType.MINIMIZE, - new InitialGuess(new double[] { 0, 1, 2, 3 })); + new InitialGuess(new double[] { 0, 1, 2, 3 }), + new LineSearchTolerance(1e-15, 1e-15, 1)); Assert.assertEquals(1.0, optimum1.getPoint()[0], 1.0e-4); Assert.assertEquals(1.0, optimum1.getPoint()[1], 1.0e-3); Assert.assertEquals(1.0, optimum1.getPoint()[2], 1.0e-4); @@ -330,14 +331,14 @@ public class NonLinearConjugateGradientOptimizerTest { NonLinearConjugateGradientOptimizer optimizer = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE, - new SimpleValueChecker(1e-6, 1e-6), - 1e-3, 1e-3, 1); + new SimpleValueChecker(1e-6, 1e-6)); PointValuePair optimum = optimizer.optimize(new MaxEval(100), problem.getObjectiveFunction(), problem.getObjectiveFunctionGradient(), GoalType.MINIMIZE, - new InitialGuess(new double[] { 7, 6, 5, 4 })); + new InitialGuess(new double[] { 7, 6, 5, 4 }), + new LineSearchTolerance(1e-3, 1e-3, 1)); Assert.assertEquals(0, optimum.getValue(), 1.0e-10); } @@ -352,14 +353,14 @@ public class NonLinearConjugateGradientOptimizerTest { }, new double[] { 3.0, 12.0, -1.0, 7.0, 1.0 }); NonLinearConjugateGradientOptimizer optimizer = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE, - new SimpleValueChecker(1e-6, 1e-6), - 1e-3, 1e-3, 1); + new SimpleValueChecker(1e-6, 1e-6)); PointValuePair optimum = optimizer.optimize(new MaxEval(100), problem.getObjectiveFunction(), problem.getObjectiveFunctionGradient(), GoalType.MINIMIZE, - new InitialGuess(new double[] { 2, 2, 2, 2, 2, 2 })); + new InitialGuess(new double[] { 2, 2, 2, 2, 2, 2 }), + new LineSearchTolerance(1e-3, 1e-3, 1)); Assert.assertEquals(0, optimum.getValue(), 1.0e-10); } @@ -373,14 +374,14 @@ public class NonLinearConjugateGradientOptimizerTest { NonLinearConjugateGradientOptimizer optimizer = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE, - new SimpleValueChecker(1e-6, 1e-6), - 1e-3, 1e-3, 1); + new SimpleValueChecker(1e-6, 1e-6)); PointValuePair optimum = optimizer.optimize(new MaxEval(100), problem.getObjectiveFunction(), problem.getObjectiveFunctionGradient(), GoalType.MINIMIZE, - new InitialGuess(new double[] { 1, 1 })); + new InitialGuess(new double[] { 1, 1 }), + new LineSearchTolerance(1e-3, 1e-3, 1)); Assert.assertEquals(2.0, optimum.getPoint()[0], 1.0e-8); Assert.assertEquals(1.0, optimum.getPoint()[1], 1.0e-8); } @@ -395,14 +396,14 @@ public class NonLinearConjugateGradientOptimizerTest { NonLinearConjugateGradientOptimizer optimizer = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE, - new SimpleValueChecker(1e-6, 1e-6), - 1e-3, 1e-3, 1); + new SimpleValueChecker(1e-6, 1e-6)); PointValuePair optimum = optimizer.optimize(new MaxEval(100), problem.getObjectiveFunction(), problem.getObjectiveFunctionGradient(), GoalType.MINIMIZE, - new InitialGuess(new double[] { 1, 1 })); + new InitialGuess(new double[] { 1, 1 }), + new LineSearchTolerance(1e-3, 1e-3, 1)); Assert.assertTrue(optimum.getValue() > 0.1); } @@ -416,14 +417,14 @@ public class NonLinearConjugateGradientOptimizerTest { problem.addPoint( 45.0, 97.0); NonLinearConjugateGradientOptimizer optimizer = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE, - new SimpleValueChecker(1e-30, 1e-30), - 1e-15, 1e-13, 1); + new SimpleValueChecker(1e-30, 1e-30)); PointValuePair optimum = optimizer.optimize(new MaxEval(100), problem.getObjectiveFunction(), problem.getObjectiveFunctionGradient(), GoalType.MINIMIZE, - new InitialGuess(new double[] { 98.680, 47.345 })); + new InitialGuess(new double[] { 98.680, 47.345 }), + new LineSearchTolerance(1e-15, 1e-13, 1)); Vector2D center = Vector2D.of(optimum.getPointRef()[0], optimum.getPointRef()[1]); Assert.assertEquals(69.960161753, problem.getRadius(center), 1.0e-8); Assert.assertEquals(96.075902096, center.getX(), 1.0e-7);