MultivariateOptimizer.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.optim.nonlinear.scalar;

  19. import org.apache.commons.math4.legacy.analysis.MultivariateFunction;
  20. import org.apache.commons.math4.legacy.analysis.UnivariateFunction;
  21. import org.apache.commons.math4.legacy.optim.BaseMultivariateOptimizer;
  22. import org.apache.commons.math4.legacy.optim.ConvergenceChecker;
  23. import org.apache.commons.math4.legacy.optim.OptimizationData;
  24. import org.apache.commons.math4.legacy.optim.PointValuePair;
  25. import org.apache.commons.math4.legacy.optim.MaxEval;
  26. import org.apache.commons.math4.legacy.optim.univariate.BracketFinder;
  27. import org.apache.commons.math4.legacy.optim.univariate.BrentOptimizer;
  28. import org.apache.commons.math4.legacy.optim.univariate.SearchInterval;
  29. import org.apache.commons.math4.legacy.optim.univariate.SimpleUnivariateValueChecker;
  30. import org.apache.commons.math4.legacy.optim.univariate.UnivariateObjectiveFunction;
  31. import org.apache.commons.math4.legacy.optim.univariate.UnivariateOptimizer;
  32. import org.apache.commons.math4.legacy.optim.univariate.UnivariatePointValuePair;

  34. /**
  35.  * Base class for a multivariate scalar function optimizer.
  36.  *
  37.  * @since 3.1
  38.  */
  39. public abstract class MultivariateOptimizer
  40.     extends BaseMultivariateOptimizer<PointValuePair> {
  41.     /** Objective function. */
  42.     private MultivariateFunction function;
  43.     /** Type of optimization. */
  44.     private GoalType goal;
  45.     /** Line search relative tolerance. */
  46.     private double lineSearchRelativeTolerance = 1e-8;
  47.     /** Line search absolute tolerance. */
  48.     private double lineSearchAbsoluteTolerance = 1e-8;
  49.     /** Line serach initial bracketing range. */
  50.     private double lineSearchInitialBracketingRange = 1d;
  51.     /** Line search. */
  52.     private LineSearch lineSearch;

  54.     /**
  55.      * @param checker Convergence checker.
  56.      */
  57.     protected MultivariateOptimizer(ConvergenceChecker<PointValuePair> checker) {
  58.         super(checker);
  59.     }

  61.     /**
  62.      * {@inheritDoc}
  63.      *
  64.      * @param optData Optimization data. In addition to those documented in
  65.      * {@link BaseMultivariateOptimizer#parseOptimizationData(OptimizationData[])
  66.      * BaseMultivariateOptimizer}, this method will register the following data:
  67.      * <ul>
  68.      *  <li>{@link ObjectiveFunction}</li>
  69.      *  <li>{@link GoalType}</li>
  70.      *  <li>{@link LineSearchTolerance}</li>
  71.      * </ul>
  72.      * @return {@inheritDoc}
  73.      * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException
  74.      * if the maximal number of evaluations is exceeded.
  75.      */
  76.     @Override
  77.     public PointValuePair optimize(OptimizationData... optData) {
  78.         // Set up base class and perform computation.
  79.         return super.optimize(optData);
  80.     }

  82.     /**
  83.      * Scans the list of (required and optional) optimization data that
  84.      * characterize the problem.
  85.      *
  86.      * @param optData Optimization data.
  87.      * The following data will be looked for:
  88.      * <ul>
  89.      *  <li>{@link ObjectiveFunction}</li>
  90.      *  <li>{@link GoalType}</li>
  91.      *  <li>{@link LineSearchTolerance}</li>
  92.      * </ul>
  93.      */
  94.     @Override
  95.     protected void parseOptimizationData(OptimizationData... optData) {
  96.         // Allow base class to register its own data.
  97.         super.parseOptimizationData(optData);

  99.         // The existing values (as set by the previous call) are reused if
  100.         // not provided in the argument list.
  101.         for (OptimizationData data : optData) {
  102.             if (data instanceof GoalType) {
  103.                 goal = (GoalType) data;
  104.                 continue;
  105.             }
  106.             if (data instanceof ObjectiveFunction) {
  107.                 final MultivariateFunction delegate = ((ObjectiveFunction) data).getObjectiveFunction();
  108.                 function = new MultivariateFunction() {
  109.                         @Override
  110.                         public double value(double[] point) {
  111.                             incrementEvaluationCount();
  112.                             return delegate.value(point);
  113.                         }
  114.                     };
  115.                 continue;
  116.             }
  117.             if (data instanceof LineSearchTolerance) {
  118.                 final LineSearchTolerance tol = (LineSearchTolerance) data;
  119.                 lineSearchRelativeTolerance = tol.getRelativeTolerance();
  120.                 lineSearchAbsoluteTolerance = tol.getAbsoluteTolerance();
  121.                 lineSearchInitialBracketingRange = tol.getInitialBracketingRange();
  122.                 continue;
  123.             }
  124.         }
  125.     }

  127.     /**
  128.      * Intantiate the line search implementation.
  129.      */
  130.     protected void createLineSearch() {
  131.         lineSearch = new LineSearch(this,
  132.                                     lineSearchRelativeTolerance,
  133.                                     lineSearchAbsoluteTolerance,
  134.                                     lineSearchInitialBracketingRange);
  135.     }

  137.     /**
  138.      * Finds the number {@code alpha} that optimizes
  139.      * {@code f(startPoint + alpha * direction)}.
  140.      *
  141.      * @param startPoint Starting point.
  142.      * @param direction Search direction.
  143.      * @return the optimum.
  144.      * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException
  145.      * if the number of evaluations is exceeded.
  146.      */
  147.     protected UnivariatePointValuePair lineSearch(final double[] startPoint,
  148.                                                   final double[] direction) {
  149.         return lineSearch.search(startPoint, direction);
  150.     }

  152.     /**
  153.      * @return the optimization type.
  154.      */
  155.     protected GoalType getGoalType() {
  156.         return goal;
  157.     }

  159.     /**
  160.      * @return a wrapper that delegates to the user-supplied function,
  161.      * and counts the number of evaluations.
  162.      */
  163.     protected MultivariateFunction getObjectiveFunction() {
  164.         return function;
  165.     }

  167.     /**
  168.      * Computes the objective function value.
  169.      * This method <em>must</em> be called by subclasses to enforce the
  170.      * evaluation counter limit.
  171.      *
  172.      * @param params Point at which the objective function must be evaluated.
  173.      * @return the objective function value at the specified point.
  174.      * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException
  175.      * if the maximal number of evaluations is exceeded.
  176.      *
  177.      * @deprecated Use {@link #getObjectiveFunction()} instead.
  178.      */
  179.     @Deprecated
  180.     public double computeObjectiveValue(double[] params) {
  181.         return function.value(params);
  182.     }

  184.     /**
  185.      * Find the minimum of the objective function along a given direction.
  186.      *
  187.      * @since 4.0
  188.      */
  189.     private static class LineSearch {
  190.         /**
  191.          * Value that will pass the precondition check for {@link BrentOptimizer}
  192.          * but will not pass the convergence check, so that the custom checker
  193.          * will always decide when to stop the line search.
  194.          */
  195.         private static final double REL_TOL_UNUSED = 1e-15;
  196.         /**
  197.          * Value that will pass the precondition check for {@link BrentOptimizer}
  198.          * but will not pass the convergence check, so that the custom checker
  199.          * will always decide when to stop the line search.
  200.          */
  201.         private static final double ABS_TOL_UNUSED = Double.MIN_VALUE;
  202.         /**
  203.          * Optimizer used for line search.
  204.          */
  205.         private final UnivariateOptimizer lineOptimizer;
  206.         /**
  207.          * Automatic bracketing.
  208.          */
  209.         private final BracketFinder bracket = new BracketFinder();
  210.         /**
  211.          * Extent of the initial interval used to find an interval that
  212.          * brackets the optimum.
  213.          */
  214.         private final double initialBracketingRange;
  215.         /**
  216.          * Optimizer on behalf of which the line search must be performed.
  217.          */
  218.         private final MultivariateOptimizer mainOptimizer;

  220.         /**
  221.          * The {@code BrentOptimizer} default stopping criterion uses the
  222.          * tolerances to check the domain (point) values, not the function
  223.          * values.
  224.          * The {@code relativeTolerance} and {@code absoluteTolerance}
  225.          * arguments are thus passed to a {@link SimpleUnivariateValueChecker
  226.          * custom checker} that will use the function values.
  227.          *
  228.          * @param optimizer Optimizer on behalf of which the line search
  229.          * be performed.
  230.          * Its {@link MultivariateOptimizer#getObjectiveFunction() objective
  231.          * function} will be called by the {@link #search(double[],double[])
  232.          * search} method.
  233.          * @param relativeTolerance Search will stop when the function relative
  234.          * difference between successive iterations is below this value.
  235.          * @param absoluteTolerance Search will stop when the function absolute
  236.          * difference between successive iterations is below this value.
  237.          * @param initialBracketingRange Extent of the initial interval used to
  238.          * find an interval that brackets the optimum.
  239.          * If the optimized function varies a lot in the vicinity of the optimum,
  240.          * it may be necessary to provide a value lower than the distance between
  241.          * successive local minima.
  242.          */
  243.         /* package-private */ LineSearch(MultivariateOptimizer optimizer,
  244.                                          double relativeTolerance,
  245.                                          double absoluteTolerance,
  246.                                          double initialBracketingRange) {
  247.             mainOptimizer = optimizer;
  248.             lineOptimizer = new BrentOptimizer(REL_TOL_UNUSED,
  249.                                                ABS_TOL_UNUSED,
  250.                                                new SimpleUnivariateValueChecker(relativeTolerance,
  251.                                                                                 absoluteTolerance));
  252.             this.initialBracketingRange = initialBracketingRange;
  253.         }

  255.         /**
  256.          * Finds the number {@code alpha} that optimizes
  257.          * {@code f(startPoint + alpha * direction)}.
  258.          *
  259.          * @param startPoint Starting point.
  260.          * @param direction Search direction.
  261.          * @return the optimum.
  262.          * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException
  263.          * if the number of evaluations is exceeded.
  264.          */
  265.         /* package-private */ UnivariatePointValuePair search(final double[] startPoint,
  266.                                                               final double[] direction) {
  267.             final int n = startPoint.length;
  268.             final MultivariateFunction func = mainOptimizer.getObjectiveFunction();
  269.             final UnivariateFunction f = new UnivariateFunction() {
  270.                     /** {@inheritDoc} */
  271.                     @Override
  272.                     public double value(double alpha) {
  273.                         final double[] x = new double[n];
  274.                         for (int i = 0; i < n; i++) {
  275.                             x[i] = startPoint[i] + alpha * direction[i];
  276.                         }
  277.                         return func.value(x);
  278.                     }
  279.                 };

  281.             final GoalType goal = mainOptimizer.getGoalType();
  282.             bracket.search(f, goal, 0, initialBracketingRange);
  283.             // Passing "MAX_VALUE" as a dummy value because it is the enclosing
  284.             // class that counts the number of evaluations (and will eventually
  285.             // generate the exception).
  286.             return lineOptimizer.optimize(new MaxEval(Integer.MAX_VALUE),
  287.                                           new UnivariateObjectiveFunction(f),
  288.                                           goal,
  289.                                           new SearchInterval(bracket.getLo(),
  290.                                                              bracket.getHi(),
  291.                                                              bracket.getMid()));
  292.         }
  293.     }
  294. }
Created with JaCoCo 0.8.10.202304240956Code Coverage Report for Apache Commons Math 4.0-SNAPSHOT