001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.math3.optim.nonlinear.scalar;
018
019import org.apache.commons.math3.optim.univariate.UnivariateOptimizer;
020import org.apache.commons.math3.optim.univariate.BrentOptimizer;
021import org.apache.commons.math3.optim.univariate.BracketFinder;
022import org.apache.commons.math3.optim.univariate.UnivariatePointValuePair;
023import org.apache.commons.math3.optim.univariate.SimpleUnivariateValueChecker;
024import org.apache.commons.math3.optim.univariate.SearchInterval;
025import org.apache.commons.math3.optim.univariate.UnivariateObjectiveFunction;
026import org.apache.commons.math3.analysis.UnivariateFunction;
027import org.apache.commons.math3.optim.MaxEval;
028
029/**
030 * Class for finding the minimum of the objective function along a given
031 * direction.
032 *
033 * @since 3.3
034 */
035public class LineSearch {
036    /**
037     * Value that will pass the precondition check for {@link BrentOptimizer}
038     * but will not pass the convergence check, so that the custom checker
039     * will always decide when to stop the line search.
040     */
041    private static final double REL_TOL_UNUSED = 1e-15;
042    /**
043     * Value that will pass the precondition check for {@link BrentOptimizer}
044     * but will not pass the convergence check, so that the custom checker
045     * will always decide when to stop the line search.
046     */
047    private static final double ABS_TOL_UNUSED = Double.MIN_VALUE;
048    /**
049     * Optimizer used for line search.
050     */
051    private final UnivariateOptimizer lineOptimizer;
052    /**
053     * Automatic bracketing.
054     */
055    private final BracketFinder bracket = new BracketFinder();
056    /**
057     * Extent of the initial interval used to find an interval that
058     * brackets the optimum.
059     */
060    private final double initialBracketingRange;
061    /**
062     * Optimizer on behalf of which the line search must be performed.
063     */
064    private final MultivariateOptimizer mainOptimizer;
065
066    /**
067     * The {@code BrentOptimizer} default stopping criterion uses the
068     * tolerances to check the domain (point) values, not the function
069     * values.
070     * The {@code relativeTolerance} and {@code absoluteTolerance}
071     * arguments are thus passed to a {@link SimpleUnivariateValueChecker
072     * custom checker} that will use the function values.
073     *
074     * @param optimizer Optimizer on behalf of which the line search
075     * be performed.
076     * Its {@link MultivariateOptimizer#computeObjectiveValue(double[])
077     * computeObjectiveValue} method will be called by the
078     * {@link #search(double[],double[]) search} method.
079     * @param relativeTolerance Search will stop when the function relative
080     * difference between successive iterations is below this value.
081     * @param absoluteTolerance Search will stop when the function absolute
082     * difference between successive iterations is below this value.
083     * @param initialBracketingRange Extent of the initial interval used to
084     * find an interval that brackets the optimum.
085     * If the optimized function varies a lot in the vicinity of the optimum,
086     * it may be necessary to provide a value lower than the distance between
087     * successive local minima.
088     */
089    public LineSearch(MultivariateOptimizer optimizer,
090                      double relativeTolerance,
091                      double absoluteTolerance,
092                      double initialBracketingRange) {
093        mainOptimizer = optimizer;
094        lineOptimizer = new BrentOptimizer(REL_TOL_UNUSED,
095                                           ABS_TOL_UNUSED,
096                                           new SimpleUnivariateValueChecker(relativeTolerance,
097                                                                            absoluteTolerance));
098        this.initialBracketingRange = initialBracketingRange;
099    }
100
101    /**
102     * Finds the number {@code alpha} that optimizes
103     * {@code f(startPoint + alpha * direction)}.
104     *
105     * @param startPoint Starting point.
106     * @param direction Search direction.
107     * @return the optimum.
108     * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
109     * if the number of evaluations is exceeded.
110     */
111    public UnivariatePointValuePair search(final double[] startPoint,
112                                           final double[] direction) {
113        final int n = startPoint.length;
114        final UnivariateFunction f = new UnivariateFunction() {
115                /** {@inheritDoc} */
116                public double value(double alpha) {
117                    final double[] x = new double[n];
118                    for (int i = 0; i < n; i++) {
119                        x[i] = startPoint[i] + alpha * direction[i];
120                    }
121                    final double obj = mainOptimizer.computeObjectiveValue(x);
122                    return obj;
123                }
124            };
125
126        final GoalType goal = mainOptimizer.getGoalType();
127        bracket.search(f, goal, 0, initialBracketingRange);
128        // Passing "MAX_VALUE" as a dummy value because it is the enclosing
129        // class that counts the number of evaluations (and will eventually
130        // generate the exception).
131        return lineOptimizer.optimize(new MaxEval(Integer.MAX_VALUE),
132                                      new UnivariateObjectiveFunction(f),
133                                      goal,
134                                      new SearchInterval(bracket.getLo(),
135                                                         bracket.getHi(),
136                                                         bracket.getMid()));
137    }
138}