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.math4.legacy.optim.nonlinear.scalar;
018
019import org.apache.commons.math4.legacy.analysis.UnivariateFunction;
020import org.apache.commons.math4.legacy.analysis.MultivariateFunction;
021import org.apache.commons.math4.legacy.optim.MaxEval;
022import org.apache.commons.math4.legacy.optim.univariate.BracketFinder;
023import org.apache.commons.math4.legacy.optim.univariate.BrentOptimizer;
024import org.apache.commons.math4.legacy.optim.univariate.SearchInterval;
025import org.apache.commons.math4.legacy.optim.univariate.SimpleUnivariateValueChecker;
026import org.apache.commons.math4.legacy.optim.univariate.UnivariateObjectiveFunction;
027import org.apache.commons.math4.legacy.optim.univariate.UnivariateOptimizer;
028import org.apache.commons.math4.legacy.optim.univariate.UnivariatePointValuePair;
029
030/**
031 * Class for finding the minimum of the objective function along a given
032 * direction.
033 *
034 * @since 3.3
035 * @deprecated as of 4.0-beta2.
036 * Class is now encapsulated in {@link MultivariateOptimizer}.
037 * Subclasses should call {@link MultivariateOptimizer#createLineSearch()}
038 * and {@link MultivariateOptimizer#lineSearch(double[],double[])} instead.
039 */
040@Deprecated
041public class LineSearch {
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 REL_TOL_UNUSED = 1e-15;
048    /**
049     * Value that will pass the precondition check for {@link BrentOptimizer}
050     * but will not pass the convergence check, so that the custom checker
051     * will always decide when to stop the line search.
052     */
053    private static final double ABS_TOL_UNUSED = Double.MIN_VALUE;
054    /**
055     * Optimizer used for line search.
056     */
057    private final UnivariateOptimizer lineOptimizer;
058    /**
059     * Automatic bracketing.
060     */
061    private final BracketFinder bracket = new BracketFinder();
062    /**
063     * Extent of the initial interval used to find an interval that
064     * brackets the optimum.
065     */
066    private final double initialBracketingRange;
067    /**
068     * Optimizer on behalf of which the line search must be performed.
069     */
070    private final MultivariateOptimizer mainOptimizer;
071
072    /**
073     * The {@code BrentOptimizer} default stopping criterion uses the
074     * tolerances to check the domain (point) values, not the function
075     * values.
076     * The {@code relativeTolerance} and {@code absoluteTolerance}
077     * arguments are thus passed to a {@link SimpleUnivariateValueChecker
078     * custom checker} that will use the function values.
079     *
080     * @param optimizer Optimizer on behalf of which the line search
081     * be performed.
082     * Its {@link MultivariateOptimizer#getObjectiveFunction() objective
083     * function} will be called by the {@link #search(double[],double[])
084     * search} method.
085     * @param relativeTolerance Search will stop when the function relative
086     * difference between successive iterations is below this value.
087     * @param absoluteTolerance Search will stop when the function absolute
088     * difference between successive iterations is below this value.
089     * @param initialBracketingRange Extent of the initial interval used to
090     * find an interval that brackets the optimum.
091     * If the optimized function varies a lot in the vicinity of the optimum,
092     * it may be necessary to provide a value lower than the distance between
093     * successive local minima.
094     */
095    public LineSearch(MultivariateOptimizer optimizer,
096                      double relativeTolerance,
097                      double absoluteTolerance,
098                      double initialBracketingRange) {
099        mainOptimizer = optimizer;
100        lineOptimizer = new BrentOptimizer(REL_TOL_UNUSED,
101                                           ABS_TOL_UNUSED,
102                                           new SimpleUnivariateValueChecker(relativeTolerance,
103                                                                            absoluteTolerance));
104        this.initialBracketingRange = initialBracketingRange;
105    }
106
107    /**
108     * Finds the number {@code alpha} that optimizes
109     * {@code f(startPoint + alpha * direction)}.
110     *
111     * @param startPoint Starting point.
112     * @param direction Search direction.
113     * @return the optimum.
114     * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException
115     * if the number of evaluations is exceeded.
116     */
117    public UnivariatePointValuePair search(final double[] startPoint,
118                                           final double[] direction) {
119        final int n = startPoint.length;
120        final MultivariateFunction func = mainOptimizer.getObjectiveFunction();
121        final UnivariateFunction f = new UnivariateFunction() {
122            /** {@inheritDoc} */
123            @Override
124            public double value(double alpha) {
125                final double[] x = new double[n];
126                for (int i = 0; i < n; i++) {
127                    x[i] = startPoint[i] + alpha * direction[i];
128                }
129                return func.value(x);
130            }
131        };
132
133        final GoalType goal = mainOptimizer.getGoalType();
134        bracket.search(f, goal, 0, initialBracketingRange);
135        // Passing "MAX_VALUE" as a dummy value because it is the enclosing
136        // class that counts the number of evaluations (and will eventually
137        // generate the exception).
138        return lineOptimizer.optimize(new MaxEval(Integer.MAX_VALUE),
139                                      new UnivariateObjectiveFunction(f),
140                                      goal,
141                                      new SearchInterval(bracket.getLo(),
142                                                         bracket.getHi(),
143                                                         bracket.getMid()));
144    }
145}