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 * https://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
18 /*
19 * This is not the original file distributed by the Apache Software Foundation
20 * It has been modified by the Hipparchus project
21 */
22 package org.hipparchus.optim.nonlinear.scalar;
23
24 import org.hipparchus.analysis.UnivariateFunction;
25 import org.hipparchus.optim.MaxEval;
26 import org.hipparchus.optim.univariate.BracketFinder;
27 import org.hipparchus.optim.univariate.BrentOptimizer;
28 import org.hipparchus.optim.univariate.SearchInterval;
29 import org.hipparchus.optim.univariate.SimpleUnivariateValueChecker;
30 import org.hipparchus.optim.univariate.UnivariateObjectiveFunction;
31 import org.hipparchus.optim.univariate.UnivariateOptimizer;
32 import org.hipparchus.optim.univariate.UnivariatePointValuePair;
33
34 /**
35 * Class for finding the minimum of the objective function along a given
36 * direction.
37 *
38 */
39 public class LineSearch {
40 /**
41 * Value that will pass the precondition check for {@link BrentOptimizer}
42 * but will not pass the convergence check, so that the custom checker
43 * will always decide when to stop the line search.
44 */
45 private static final double REL_TOL_UNUSED = 1e-15;
46 /**
47 * Value that will pass the precondition check for {@link BrentOptimizer}
48 * but will not pass the convergence check, so that the custom checker
49 * will always decide when to stop the line search.
50 */
51 private static final double ABS_TOL_UNUSED = Double.MIN_VALUE;
52 /**
53 * Optimizer used for line search.
54 */
55 private final UnivariateOptimizer lineOptimizer;
56 /**
57 * Automatic bracketing.
58 */
59 private final BracketFinder bracket = new BracketFinder();
60 /**
61 * Extent of the initial interval used to find an interval that
62 * brackets the optimum.
63 */
64 private final double initialBracketingRange;
65 /**
66 * Optimizer on behalf of which the line search must be performed.
67 */
68 private final MultivariateOptimizer mainOptimizer;
69
70 /**
71 * The {@code BrentOptimizer} default stopping criterion uses the
72 * tolerances to check the domain (point) values, not the function
73 * values.
74 * The {@code relativeTolerance} and {@code absoluteTolerance}
75 * arguments are thus passed to a {@link SimpleUnivariateValueChecker
76 * custom checker} that will use the function values.
77 *
78 * @param optimizer Optimizer on behalf of which the line search
79 * be performed.
80 * Its {@link MultivariateOptimizer#computeObjectiveValue(double[])
81 * computeObjectiveValue} method will be called by the
82 * {@link #search(double[],double[]) search} method.
83 * @param relativeTolerance Search will stop when the function relative
84 * difference between successive iterations is below this value.
85 * @param absoluteTolerance Search will stop when the function absolute
86 * difference between successive iterations is below this value.
87 * @param initialBracketingRange Extent of the initial interval used to
88 * find an interval that brackets the optimum.
89 * If the optimized function varies a lot in the vicinity of the optimum,
90 * it may be necessary to provide a value lower than the distance between
91 * successive local minima.
92 */
93 public LineSearch(MultivariateOptimizer optimizer,
94 double relativeTolerance,
95 double absoluteTolerance,
96 double initialBracketingRange) {
97 mainOptimizer = optimizer;
98 lineOptimizer = new BrentOptimizer(REL_TOL_UNUSED,
99 ABS_TOL_UNUSED,
100 new SimpleUnivariateValueChecker(relativeTolerance,
101 absoluteTolerance));
102 this.initialBracketingRange = initialBracketingRange;
103 }
104
105 /**
106 * Finds the number {@code alpha} that optimizes
107 * {@code f(startPoint + alpha * direction)}.
108 *
109 * @param startPoint Starting point.
110 * @param direction Search direction.
111 * @return the optimum.
112 * @throws org.hipparchus.exception.MathIllegalStateException
113 * if the number of evaluations is exceeded.
114 */
115 public UnivariatePointValuePair search(final double[] startPoint,
116 final double[] direction) {
117 final int n = startPoint.length;
118 final UnivariateFunction f = new UnivariateFunction() {
119 /** {@inheritDoc} */
120 @Override
121 public double value(double alpha) {
122 final double[] x = new double[n];
123 for (int i = 0; i < n; i++) {
124 x[i] = startPoint[i] + alpha * direction[i];
125 }
126 return mainOptimizer.computeObjectiveValue(x);
127 }
128 };
129
130 final GoalType goal = mainOptimizer.getGoalType();
131 bracket.search(f, goal, 0, initialBracketingRange);
132 // Passing "MAX_VALUE" as a dummy value because it is the enclosing
133 // class that counts the number of evaluations (and will eventually
134 // generate the exception).
135 return lineOptimizer.optimize(new MaxEval(Integer.MAX_VALUE),
136 new UnivariateObjectiveFunction(f),
137 goal,
138 new SearchInterval(bracket.getLo(),
139 bracket.getHi(),
140 bracket.getMid()));
141 }
142 }