commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/MultivariateOptimizer.java

/*
 * 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.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.
 *
 * @since 3.1
 */
public abstract class MultivariateOptimizer
    extends BaseMultivariateOptimizer<PointValuePair> {
    /** Objective function. */
    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.
     */
    protected MultivariateOptimizer(ConvergenceChecker<PointValuePair> checker) {
        super(checker);
    }

    /**
     * {@inheritDoc}
     *
     * @param optData Optimization data. In addition to those documented in
     * {@link BaseMultivariateOptimizer#parseOptimizationData(OptimizationData[])
     * BaseMultivariateOptimizer}, this method will register the following data:
     * <ul>
     *  <li>{@link ObjectiveFunction}</li>
     *  <li>{@link GoalType}</li>
     *  <li>{@link LineSearchTolerance}</li>
     * </ul>
     * @return {@inheritDoc}
     * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException
     * if the maximal number of evaluations is exceeded.
     */
    @Override
    public PointValuePair optimize(OptimizationData... optData) {
        // Set up base class and perform computation.
        return super.optimize(optData);
    }

    /**
     * Scans the list of (required and optional) optimization data that
     * characterize the problem.
     *
     * @param optData Optimization data.
     * The following data will be looked for:
     * <ul>
     *  <li>{@link ObjectiveFunction}</li>
     *  <li>{@link GoalType}</li>
     *  <li>{@link LineSearchTolerance}</li>
     * </ul>
     */
    @Override
    protected void parseOptimizationData(OptimizationData... optData) {
        // Allow base class to register its own data.
        super.parseOptimizationData(optData);

        // The existing values (as set by the previous call) are reused if
        // not provided in the argument list.
        for (OptimizationData data : optData) {
            if (data instanceof GoalType) {
                goal = (GoalType) data;
                continue;
            }
            if (data instanceof ObjectiveFunction) {
                final MultivariateFunction delegate = ((ObjectiveFunction) data).getObjectiveFunction();
                function = new MultivariateFunction() {
                        @Override
                        public double value(double[] point) {
                            incrementEvaluationCount();
                            return delegate.value(point);
                        }
                    };
                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.
     */
    protected GoalType getGoalType() {
        return goal;
    }

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

    /**
     * Computes the objective function value.
     * This method <em>must</em> be called by subclasses to enforce the
     * evaluation counter limit.
     *
     * @param params Point at which the objective function must be evaluated.
     * @return the objective function value at the specified point.
     * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException
     * if the maximal number of evaluations is exceeded.
     *
     * @deprecated Use {@link #getObjectiveFunction()} instead.
     */
    @Deprecated
    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()));
        }
    }
}