1 /*
2 * Copyright (C) 2012 Alberto Irurueta Carro (alberto@irurueta.com)
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 package com.irurueta.numerical.optimization;
17
18 import com.irurueta.numerical.DirectionalEvaluator;
19 import com.irurueta.numerical.EvaluationException;
20 import com.irurueta.numerical.LockedException;
21 import com.irurueta.numerical.MultiDimensionFunctionEvaluatorListener;
22 import com.irurueta.numerical.NotAvailableException;
23 import com.irurueta.numerical.NumericalException;
24
25 /**
26 * Abstract class to search for a local minimum on a multidimensional function
27 * along a given line of input parameters.
28 * Line minimization implementations exist such as Powell's method or conjugate
29 * gradients. Among those, usually conjugate gradients provide faster
30 * convergence because search directions during the estimation don't need to be
31 * perpendicular.
32 */
33 public abstract class LineMultiOptimizer extends MultiOptimizer {
34 /**
35 * n-dimensional point containing a minimum in a given line.
36 */
37 protected double[] p;
38
39 /**
40 * Direction to make the search.
41 */
42 protected double[] xi;
43
44 /**
45 * Number of dimensions on function being evaluated.
46 */
47 private int n;
48
49 /**
50 * Class in charge of evaluating a function through a given line.
51 */
52 private DirectionalEvaluator evaluator;
53
54 /**
55 * Internal optimizer to find a minimum of a function along a line of
56 * input values. Hence, input is converted to a single dimension using a
57 * DirectionalEvaluator.
58 */
59 private BrentSingleOptimizer brent;
60
61 /**
62 * Empty constructor.
63 */
64 protected LineMultiOptimizer() {
65 super();
66 p = xi = null;
67 n = 0;
68 evaluator = null;
69 brent = null;
70 }
71
72 /**
73 * Constructor.
74 *
75 * @param listener Listener to evaluate a multi-dimension function.
76 */
77 protected LineMultiOptimizer(final MultiDimensionFunctionEvaluatorListener listener) {
78 super(listener);
79 p = xi = null;
80 n = 0;
81 evaluator = null;
82 brent = null;
83 }
84
85 /**
86 * Constructor.
87 *
88 * @param listener Listener to evaluate a multi-dimension function.
89 * @param point Start point where algorithm will be started. Start point
90 * should be close to the local minimum to be found. Provided array must
91 * have a length equal to the number of dimensions of the function being
92 * evaluated, otherwise and exception will be raised when searching for the
93 * minimum.
94 * @param direction Direction to start looking for a minimum. Provided array
95 * must have the same length as the number of dimensions of the function
96 * being evaluated. Provided direction is considered as a vector pointing
97 * to the minimum to be found.
98 * @throws IllegalArgumentException Raised if provided point and direction
99 * don't have the same length.
100 */
101 protected LineMultiOptimizer(
102 final MultiDimensionFunctionEvaluatorListener listener, final double[] point, final double[] direction) {
103 super(listener);
104 internalSetStartPointAndDirection(point, direction);
105 n = 0;
106 evaluator = null;
107 brent = null;
108 }
109
110 /**
111 * Returns boolean indicating whether start point has already been provided
112 * and is ready for retrieval.
113 *
114 * @return True if available, false otherwise.
115 */
116 public boolean isStartPointAvailable() {
117 return p != null;
118 }
119
120 /**
121 * Returns start point where algorithm will be started. Start point should
122 * be close to the local minimum to be found.
123 *
124 * @return Start point where algorithm will be started.
125 * @throws NotAvailableException Raised if start point has not yet been
126 * provided and is not available.
127 */
128 public double[] getStartPoint() throws NotAvailableException {
129 if (!isStartPointAvailable()) {
130 throw new NotAvailableException();
131 }
132 return p;
133 }
134
135 /**
136 * Returns boolean indicating whether direction has already been provided
137 * and is ready for retrieval.
138 *
139 * @return True if available, false otherwise.
140 */
141 public boolean isDirectionAvailable() {
142 return xi != null;
143 }
144
145 /**
146 * Returns direction to start looking for a minimum. Provided array must
147 * have the same length as the number of dimensions of the function being
148 * evaluated. Provided direction is considered as a vector pointing to the
149 * minimum to be found.
150 *
151 * @return Direction to start looking for a minimum.
152 * @throws NotAvailableException Raised if direction has not yet been
153 * provided and is not available.
154 */
155 public double[] getDirection() throws NotAvailableException {
156 if (!isDirectionAvailable()) {
157 throw new NotAvailableException();
158 }
159 return xi;
160 }
161
162 /**
163 * Internal method to set start point and direction to start the search for
164 * a local minimum.
165 *
166 * @param point Start point where algorithm will be started. Start point
167 * should be close to the local minimum to be found. Provided array must
168 * have a length equal to the number of dimensions of the function being
169 * evaluated, otherwise and exception will be raised when searching for the
170 * minimum.
171 * @param direction Direction to start looking for a minimum. Provided array
172 * must have the same length as the number of dimensions of the function
173 * being evaluated. Provided direction is considered as a vector pointing
174 * to the minimum to be found.
175 * @throws LockedException Raised if this instance is locked.
176 * @throws IllegalArgumentException Raised if provided point and direction
177 * don't have the same length.
178 */
179 public void setStartPointAndDirection(final double[] point, final double[] direction) throws LockedException {
180 if (isLocked()) {
181 throw new LockedException();
182 }
183 internalSetStartPointAndDirection(point, direction);
184 }
185
186 /**
187 * Returns boolean indicating whether this instance is considered to be
188 * ready to start the estimation of a minimum.
189 * This instance is considered to be ready once a listener, start point and
190 * direction are provided.
191 *
192 * @return True if this instance is ready, false otherwise.
193 */
194 @Override
195 public boolean isReady() {
196 return isListenerAvailable() && isStartPointAvailable() && isDirectionAvailable();
197 }
198
199 /**
200 * Searches for a minimum along a given line of input values.
201 * The line being searched is obtained by using a start point and direction.
202 *
203 * @return Returns function evaluation at minimum that has been found.
204 */
205 @SuppressWarnings("Duplicates")
206 protected double linmin() {
207 final double ax;
208 final double xx;
209 final double linxmin;
210 n = p.length;
211
212 if (evaluator == null) {
213 // attempt to reuse evaluator
214 evaluator = new DirectionalEvaluator(listener, p, xi);
215 }
216 if (evaluator.getListener() != listener) {
217 // update listener
218 evaluator.setListener(listener);
219 }
220 if (evaluator.getPoint() != p || evaluator.getDirection() != xi) {
221 evaluator.setPointAndDirection(p, xi);
222 }
223
224 ax = 0.0;
225 xx = 1.0;
226
227 try {
228 if (brent == null) {
229 // attempt to reuse brent single optimizer
230 brent = new BrentSingleOptimizer(
231 point -> evaluator.evaluateAt(point),
232 BracketedSingleOptimizer.DEFAULT_MIN_EVAL_POINT,
233 BracketedSingleOptimizer.DEFAULT_MIDDLE_EVAL_POINT,
234 BracketedSingleOptimizer.DEFAULT_MAX_EVAL_POINT,
235 BrentSingleOptimizer.DEFAULT_TOLERANCE);
236 }
237
238 brent.computeBracket(ax, xx);
239 brent.minimize();
240 linxmin = brent.getResult();
241
242 for (var j = 0; j < n; j++) {
243 xi[j] *= linxmin;
244 p[j] += xi[j];
245 }
246
247 return brent.getEvaluationAtResult();
248 } catch (final NumericalException e) {
249 // if minimization fails, try to evaluate at best point found so far
250 try {
251 return listener.evaluate(p);
252 } catch (EvaluationException e2) {
253 // if minimization fails here we assume that obtained result is
254 // the worst possible one
255 return Double.MAX_VALUE;
256 }
257 }
258 }
259
260 /**
261 * Internal method to set start point and direction to start the search for
262 * a local minimum.
263 * This method does not check whether this instance is locked.
264 *
265 * @param point Start point where algorithm will be started. Start point
266 * should be close to the local minimum to be found. Provided array must
267 * have a length equal to the number of dimensions of the function being
268 * evaluated, otherwise and exception will be raised when searching for the
269 * minimum.
270 * @param direction Direction to start looking for a minimum. Provided array
271 * must have the same length as the number of dimensions of the function
272 * being evaluated. Provided direction is considered as a vector pointing
273 * to the minimum to be found.
274 * @throws IllegalArgumentException Raised if provided point and direction
275 * don't have the same length.
276 */
277 private void internalSetStartPointAndDirection(final double[] point, final double[] direction) {
278 if (point.length != direction.length) {
279 throw new IllegalArgumentException();
280 }
281 p = point;
282 xi = direction;
283 }
284 }