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.MultivariateFunction;
20 import org.apache.commons.math4.legacy.analysis.UnivariateFunction;
21 import org.apache.commons.math4.legacy.optim.BaseMultivariateOptimizer;
22 import org.apache.commons.math4.legacy.optim.ConvergenceChecker;
23 import org.apache.commons.math4.legacy.optim.OptimizationData;
24 import org.apache.commons.math4.legacy.optim.PointValuePair;
25 import org.apache.commons.math4.legacy.optim.MaxEval;
26 import org.apache.commons.math4.legacy.optim.univariate.BracketFinder;
27 import org.apache.commons.math4.legacy.optim.univariate.BrentOptimizer;
28 import org.apache.commons.math4.legacy.optim.univariate.SearchInterval;
29 import org.apache.commons.math4.legacy.optim.univariate.SimpleUnivariateValueChecker;
30 import org.apache.commons.math4.legacy.optim.univariate.UnivariateObjectiveFunction;
31 import org.apache.commons.math4.legacy.optim.univariate.UnivariateOptimizer;
32 import org.apache.commons.math4.legacy.optim.univariate.UnivariatePointValuePair;
33
34 /**
35 * Base class for a multivariate scalar function optimizer.
36 *
37 * @since 3.1
38 */
39 public abstract class MultivariateOptimizer
40 extends BaseMultivariateOptimizer<PointValuePair> {
41 /** Objective function. */
42 private MultivariateFunction function;
43 /** Type of optimization. */
44 private GoalType goal;
45 /** Line search relative tolerance. */
46 private double lineSearchRelativeTolerance = 1e-8;
47 /** Line search absolute tolerance. */
48 private double lineSearchAbsoluteTolerance = 1e-8;
49 /** Line serach initial bracketing range. */
50 private double lineSearchInitialBracketingRange = 1d;
51 /** Line search. */
52 private LineSearch lineSearch;
53
54 /**
55 * @param checker Convergence checker.
56 */
57 protected MultivariateOptimizer(ConvergenceChecker<PointValuePair> checker) {
58 super(checker);
59 }
60
61 /**
62 * {@inheritDoc}
63 *
64 * @param optData Optimization data. In addition to those documented in
65 * {@link BaseMultivariateOptimizer#parseOptimizationData(OptimizationData[])
66 * BaseMultivariateOptimizer}, this method will register the following data:
67 * <ul>
68 * <li>{@link ObjectiveFunction}</li>
69 * <li>{@link GoalType}</li>
70 * <li>{@link LineSearchTolerance}</li>
71 * </ul>
72 * @return {@inheritDoc}
73 * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException
74 * if the maximal number of evaluations is exceeded.
75 */
76 @Override
77 public PointValuePair optimize(OptimizationData... optData) {
78 // Set up base class and perform computation.
79 return super.optimize(optData);
80 }
81
82 /**
83 * Scans the list of (required and optional) optimization data that
84 * characterize the problem.
85 *
86 * @param optData Optimization data.
87 * The following data will be looked for:
88 * <ul>
89 * <li>{@link ObjectiveFunction}</li>
90 * <li>{@link GoalType}</li>
91 * <li>{@link LineSearchTolerance}</li>
92 * </ul>
93 */
94 @Override
95 protected void parseOptimizationData(OptimizationData... optData) {
96 // Allow base class to register its own data.
97 super.parseOptimizationData(optData);
98
99 // The existing values (as set by the previous call) are reused if
100 // not provided in the argument list.
101 for (OptimizationData data : optData) {
102 if (data instanceof GoalType) {
103 goal = (GoalType) data;
104 continue;
105 }
106 if (data instanceof ObjectiveFunction) {
107 final MultivariateFunction delegate = ((ObjectiveFunction) data).getObjectiveFunction();
108 function = new MultivariateFunction() {
109 @Override
110 public double value(double[] point) {
111 incrementEvaluationCount();
112 return delegate.value(point);
113 }
114 };
115 continue;
116 }
117 if (data instanceof LineSearchTolerance) {
118 final LineSearchTolerance tol = (LineSearchTolerance) data;
119 lineSearchRelativeTolerance = tol.getRelativeTolerance();
120 lineSearchAbsoluteTolerance = tol.getAbsoluteTolerance();
121 lineSearchInitialBracketingRange = tol.getInitialBracketingRange();
122 continue;
123 }
124 }
125 }
126
127 /**
128 * Intantiate the line search implementation.
129 */
130 protected void createLineSearch() {
131 lineSearch = new LineSearch(this,
132 lineSearchRelativeTolerance,
133 lineSearchAbsoluteTolerance,
134 lineSearchInitialBracketingRange);
135 }
136
137 /**
138 * Finds the number {@code alpha} that optimizes
139 * {@code f(startPoint + alpha * direction)}.
140 *
141 * @param startPoint Starting point.
142 * @param direction Search direction.
143 * @return the optimum.
144 * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException
145 * if the number of evaluations is exceeded.
146 */
147 protected UnivariatePointValuePair lineSearch(final double[] startPoint,
148 final double[] direction) {
149 return lineSearch.search(startPoint, direction);
150 }
151
152 /**
153 * @return the optimization type.
154 */
155 protected GoalType getGoalType() {
156 return goal;
157 }
158
159 /**
160 * @return a wrapper that delegates to the user-supplied function,
161 * and counts the number of evaluations.
162 */
163 protected MultivariateFunction getObjectiveFunction() {
164 return function;
165 }
166
167 /**
168 * Computes the objective function value.
169 * This method <em>must</em> be called by subclasses to enforce the
170 * evaluation counter limit.
171 *
172 * @param params Point at which the objective function must be evaluated.
173 * @return the objective function value at the specified point.
174 * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException
175 * if the maximal number of evaluations is exceeded.
176 *
177 * @deprecated Use {@link #getObjectiveFunction()} instead.
178 */
179 @Deprecated
180 public double computeObjectiveValue(double[] params) {
181 return function.value(params);
182 }
183
184 /**
185 * Find the minimum of the objective function along a given direction.
186 *
187 * @since 4.0
188 */
189 private static class LineSearch {
190 /**
191 * Value that will pass the precondition check for {@link BrentOptimizer}
192 * but will not pass the convergence check, so that the custom checker
193 * will always decide when to stop the line search.
194 */
195 private static final double REL_TOL_UNUSED = 1e-15;
196 /**
197 * Value that will pass the precondition check for {@link BrentOptimizer}
198 * but will not pass the convergence check, so that the custom checker
199 * will always decide when to stop the line search.
200 */
201 private static final double ABS_TOL_UNUSED = Double.MIN_VALUE;
202 /**
203 * Optimizer used for line search.
204 */
205 private final UnivariateOptimizer lineOptimizer;
206 /**
207 * Automatic bracketing.
208 */
209 private final BracketFinder bracket = new BracketFinder();
210 /**
211 * Extent of the initial interval used to find an interval that
212 * brackets the optimum.
213 */
214 private final double initialBracketingRange;
215 /**
216 * Optimizer on behalf of which the line search must be performed.
217 */
218 private final MultivariateOptimizer mainOptimizer;
219
220 /**
221 * The {@code BrentOptimizer} default stopping criterion uses the
222 * tolerances to check the domain (point) values, not the function
223 * values.
224 * The {@code relativeTolerance} and {@code absoluteTolerance}
225 * arguments are thus passed to a {@link SimpleUnivariateValueChecker
226 * custom checker} that will use the function values.
227 *
228 * @param optimizer Optimizer on behalf of which the line search
229 * be performed.
230 * Its {@link MultivariateOptimizer#getObjectiveFunction() objective
231 * function} will be called by the {@link #search(double[],double[])
232 * search} method.
233 * @param relativeTolerance Search will stop when the function relative
234 * difference between successive iterations is below this value.
235 * @param absoluteTolerance Search will stop when the function absolute
236 * difference between successive iterations is below this value.
237 * @param initialBracketingRange Extent of the initial interval used to
238 * find an interval that brackets the optimum.
239 * If the optimized function varies a lot in the vicinity of the optimum,
240 * it may be necessary to provide a value lower than the distance between
241 * successive local minima.
242 */
243 /* package-private */ LineSearch(MultivariateOptimizer optimizer,
244 double relativeTolerance,
245 double absoluteTolerance,
246 double initialBracketingRange) {
247 mainOptimizer = optimizer;
248 lineOptimizer = new BrentOptimizer(REL_TOL_UNUSED,
249 ABS_TOL_UNUSED,
250 new SimpleUnivariateValueChecker(relativeTolerance,
251 absoluteTolerance));
252 this.initialBracketingRange = initialBracketingRange;
253 }
254
255 /**
256 * Finds the number {@code alpha} that optimizes
257 * {@code f(startPoint + alpha * direction)}.
258 *
259 * @param startPoint Starting point.
260 * @param direction Search direction.
261 * @return the optimum.
262 * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException
263 * if the number of evaluations is exceeded.
264 */
265 /* package-private */ UnivariatePointValuePair search(final double[] startPoint,
266 final double[] direction) {
267 final int n = startPoint.length;
268 final MultivariateFunction func = mainOptimizer.getObjectiveFunction();
269 final UnivariateFunction f = new UnivariateFunction() {
270 /** {@inheritDoc} */
271 @Override
272 public double value(double alpha) {
273 final double[] x = new double[n];
274 for (int i = 0; i < n; i++) {
275 x[i] = startPoint[i] + alpha * direction[i];
276 }
277 return func.value(x);
278 }
279 };
280
281 final GoalType goal = mainOptimizer.getGoalType();
282 bracket.search(f, goal, 0, initialBracketingRange);
283 // Passing "MAX_VALUE" as a dummy value because it is the enclosing
284 // class that counts the number of evaluations (and will eventually
285 // generate the exception).
286 return lineOptimizer.optimize(new MaxEval(Integer.MAX_VALUE),
287 new UnivariateObjectiveFunction(f),
288 goal,
289 new SearchInterval(bracket.getLo(),
290 bracket.getHi(),
291 bracket.getMid()));
292 }
293 }
294 }