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;
18
19 import org.apache.commons.math4.legacy.analysis.UnivariateFunction;
20 import org.apache.commons.math4.legacy.analysis.MultivariateFunction;
21 import org.apache.commons.math4.legacy.optim.MaxEval;
22 import org.apache.commons.math4.legacy.optim.univariate.BracketFinder;
23 import org.apache.commons.math4.legacy.optim.univariate.BrentOptimizer;
24 import org.apache.commons.math4.legacy.optim.univariate.SearchInterval;
25 import org.apache.commons.math4.legacy.optim.univariate.SimpleUnivariateValueChecker;
26 import org.apache.commons.math4.legacy.optim.univariate.UnivariateObjectiveFunction;
27 import org.apache.commons.math4.legacy.optim.univariate.UnivariateOptimizer;
28 import org.apache.commons.math4.legacy.optim.univariate.UnivariatePointValuePair;
29
30 /**
31 * Class for finding the minimum of the objective function along a given
32 * direction.
33 *
34 * @since 3.3
35 * @deprecated as of 4.0-beta2.
36 * Class is now encapsulated in {@link MultivariateOptimizer}.
37 * Subclasses should call {@link MultivariateOptimizer#createLineSearch()}
38 * and {@link MultivariateOptimizer#lineSearch(double[],double[])} instead.
39 */
40 @Deprecated
41 public class LineSearch {
42 /**
43 * Value that will pass the precondition check for {@link BrentOptimizer}
44 * but will not pass the convergence check, so that the custom checker
45 * will always decide when to stop the line search.
46 */
47 private static final double REL_TOL_UNUSED = 1e-15;
48 /**
49 * Value that will pass the precondition check for {@link BrentOptimizer}
50 * but will not pass the convergence check, so that the custom checker
51 * will always decide when to stop the line search.
52 */
53 private static final double ABS_TOL_UNUSED = Double.MIN_VALUE;
54 /**
55 * Optimizer used for line search.
56 */
57 private final UnivariateOptimizer lineOptimizer;
58 /**
59 * Automatic bracketing.
60 */
61 private final BracketFinder bracket = new BracketFinder();
62 /**
63 * Extent of the initial interval used to find an interval that
64 * brackets the optimum.
65 */
66 private final double initialBracketingRange;
67 /**
68 * Optimizer on behalf of which the line search must be performed.
69 */
70 private final MultivariateOptimizer mainOptimizer;
71
72 /**
73 * The {@code BrentOptimizer} default stopping criterion uses the
74 * tolerances to check the domain (point) values, not the function
75 * values.
76 * The {@code relativeTolerance} and {@code absoluteTolerance}
77 * arguments are thus passed to a {@link SimpleUnivariateValueChecker
78 * custom checker} that will use the function values.
79 *
80 * @param optimizer Optimizer on behalf of which the line search
81 * be performed.
82 * Its {@link MultivariateOptimizer#getObjectiveFunction() objective
83 * function} will be called by the {@link #search(double[],double[])
84 * search} method.
85 * @param relativeTolerance Search will stop when the function relative
86 * difference between successive iterations is below this value.
87 * @param absoluteTolerance Search will stop when the function absolute
88 * difference between successive iterations is below this value.
89 * @param initialBracketingRange Extent of the initial interval used to
90 * find an interval that brackets the optimum.
91 * If the optimized function varies a lot in the vicinity of the optimum,
92 * it may be necessary to provide a value lower than the distance between
93 * successive local minima.
94 */
95 public LineSearch(MultivariateOptimizer optimizer,
96 double relativeTolerance,
97 double absoluteTolerance,
98 double initialBracketingRange) {
99 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 }