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.EvaluationException;
19 import com.irurueta.numerical.InvalidBracketRangeException;
20 import com.irurueta.numerical.LockedException;
21 import com.irurueta.numerical.NotReadyException;
22 import com.irurueta.numerical.SingleDimensionFunctionEvaluatorListener;
23
24 /**
25 * This class for a single dimensional function's local minimum.
26 * This class is based in the Golden search algorithm found in
27 * Numerical Recipes 3rd ed. Section 10.2 page 492.
28 */
29 public class GoldenSingleOptimizer extends BracketedSingleOptimizer {
30
31 /**
32 * Golden ratio.
33 */
34 public static final double R = 0.61803399;
35
36 /**
37 * Golden ratio.
38 */
39 public static final double C = 1.0 - R;
40
41 /**
42 * Constant defining the default accuracy of the estimated minimum.
43 */
44 public static final double DEFAULT_TOLERANCE = 3e-8;
45
46 /**
47 * Minimum allowed tolerance.
48 */
49 public static final double MIN_TOLERANCE = 0.0;
50
51 /**
52 * Tolerance value. The algorithm will iterate until the result converges
53 * below this value of accuracy or until the maximum number of iterations is
54 * achieved (and in such case, convergence will be assumed to have failed).
55 */
56 private double tolerance;
57
58 /**
59 * Empty constructor.
60 */
61 public GoldenSingleOptimizer() {
62 super();
63 tolerance = DEFAULT_TOLERANCE;
64 }
65
66 /**
67 * Constructor. Creates an instance with provided bracket of values and a
68 * listener to get single dimension function evaluations.
69 *
70 * @param listener Listener to evaluate a function.
71 * @param minEvalPoint Minimum bracket evaluation point.
72 * @param middleEvalPoint Middle bracket evaluation point.
73 * @param maxEvalPoint Maximum bracket evaluation point.
74 * @param tolerance Tolerance or accuracy to be obtained in estimated
75 * minimum.
76 * @throws InvalidBracketRangeException Raised if the following condition is
77 * not met: minEvalPoint <= middleEvalPoint <= maxEvalPoint.
78 * @throws IllegalArgumentException Raised if tolerance is negative.
79 */
80 public GoldenSingleOptimizer(
81 final SingleDimensionFunctionEvaluatorListener listener, final double minEvalPoint,
82 final double middleEvalPoint, final double maxEvalPoint, final double tolerance)
83 throws InvalidBracketRangeException {
84 super(listener, minEvalPoint, middleEvalPoint, maxEvalPoint);
85 internalSetTolerance(tolerance);
86 }
87
88 /**
89 * Returns tolerance value, which is the accuracy to be obtained when a
90 * minimum is estimated.
91 * The algorithm will iterate until the result converges below this value of
92 * accuracy or until the maximum number of iterations is achieved (and in
93 * such case, convergence will be assumed to have failed).
94 *
95 * @return Tolerance value.
96 */
97 public double getTolerance() {
98 return tolerance;
99 }
100
101 /**
102 * Sets algorithm's tolerance.
103 * The algorithm will iterate until the result converges below this value of
104 * accuracy or until the maximum number of iterations is achieved (an in
105 * such case, convergence will be assumed to have failed).
106 *
107 * @param tolerance Tolerance or accuracy to be obtained in estimated
108 * minimum.
109 * @throws LockedException Raised if this instance is locked. This instance
110 * will be locked while doing some operations. Attempting to change any
111 * parameter while being locked will raise this exception.
112 * @throws IllegalArgumentException Raised if tolerance is negative.
113 */
114 public void setTolerance(final double tolerance) throws LockedException {
115 if (isLocked()) {
116 throw new LockedException();
117 }
118 internalSetTolerance(tolerance);
119 }
120
121 /**
122 * This function estimates a function minimum within provided or computed
123 * bracket of values.
124 * Given a function f, and given a bracketing triplet of abscissas "ax", "bx",
125 * "cx" (such that bx is between ax and cx, and f(bx) is less than both f(ax)
126 * and f(cx), this routine isolates the minimum to a fractional prevision of
127 * about tolerance using Brent's method. The abscissa of the minimum is
128 * returned as "xmin", and the function value of the minimum is returned as
129 * "fmin", the returned function value.
130 *
131 * @throws LockedException Raised if this instance is locked, because
132 * estimation is being computed.
133 * @throws NotReadyException Raised if this instance is not ready because
134 * either a listener or a bracket has not yet been provided or computed.
135 * @throws OptimizationException Raised if the algorithm failed because of
136 * lack of convergence or because function couldn't be evaluated.
137 */
138 @SuppressWarnings("DuplicatedCode")
139 @Override
140 public void minimize() throws LockedException, NotReadyException, OptimizationException {
141 if (isLocked()) {
142 throw new LockedException();
143 }
144 if (!isReady()) {
145 throw new NotReadyException();
146 }
147
148 locked = true;
149
150 final var v1 = new double[1];
151 final var v2 = new double[2];
152 final var v3 = new double[3];
153
154
155 try {
156 // At any given time we will keep track of four points x0, x1, x2, x3
157 double x1;
158 double x2;
159 var x0 = ax;
160 var x3 = cx;
161
162 // Make x0 to x1 the smaller segment, and fill in the new point to be
163 // tried
164 if (Math.abs(cx - bx) > Math.abs(bx - ax)) {
165 x1 = bx;
166 x2 = bx + C * (cx - bx);
167 } else {
168 x2 = bx;
169 x1 = bx - C * (bx - ax);
170 }
171
172 // The initial function evaluations. Note that we never need to
173 // evaluate the function at the original endpoints
174 var f1 = listener.evaluate(x1);
175 var f2 = listener.evaluate(x2);
176
177 var iter = 0;
178 while (Math.abs(x3 - x0) > tolerance * (Math.abs(x1) + Math.abs(x2))) {
179 if (f2 < f1) {
180 // One possible outcome, its housekeeping and a new function
181 // evaluation
182 v1[0] = x0;
183 v2[0] = x1;
184 v3[0] = x2;
185 shift3(v1, v2, v3, R * x2 + C * x3);
186 x0 = v1[0];
187 x1 = v2[0];
188 x2 = v3[0];
189
190 v1[0] = f1;
191 v2[0] = f2;
192 shift2(v1, v2, listener.evaluate(x2));
193 f1 = v1[0];
194 f2 = v2[0];
195 } else {
196 // The other outcome, and its new function evaluation
197 v1[0] = x3;
198 v2[0] = x2;
199 v3[0] = x1;
200 shift3(v1, v2, v3, R * x1 + C * x0);
201 x3 = v1[0];
202 x2 = v2[0];
203 x1 = v3[0];
204
205 v1[0] = f2;
206 v2[0] = f1;
207 shift2(v1, v2, listener.evaluate(x1));
208 f2 = v1[0];
209 f1 = v2[0];
210 }
211 // Back to see if we are done.
212
213 if (iterationCompletedListener != null) {
214 iterationCompletedListener.onIterationCompleted(this, iter, null);
215 iter++;
216 }
217 }
218
219 // We are done. Output the best of the current values
220 if (f1 < f2) {
221 xmin = x1;
222 fmin = f1;
223 } else {
224 xmin = x2;
225 fmin = f2;
226 }
227 } catch (final EvaluationException e) {
228 throw new OptimizationException(e);
229 } finally {
230 locked = false;
231 }
232
233 resultAvailable = true;
234 }
235
236 /**
237 * Returns boolean indicating whether this instance is ready to start the
238 * estimation of a minimum or not.
239 * The instance is ready when both the listener and the bracket are
240 * available.
241 *
242 * @return True if this instance is ready, false otherwise.
243 */
244 @Override
245 public boolean isReady() {
246 return isListenerAvailable() && isBracketAvailable();
247 }
248
249 /**
250 * Internal method to set algorithm tolerance. This method does not check
251 * whether this instance is locked or not.
252 * The algorithm will iterate until the result converges below this value of
253 * accuracy or until the maximum number of iterations is achieved (and in
254 * such case, convergence will be assumed to have failed).
255 *
256 * @param tolerance Tolerance or accuracy to be obtained in estimated
257 * minimum.
258 * @throws IllegalArgumentException Raised if tolerance is negative.
259 */
260 private void internalSetTolerance(final double tolerance) {
261 if (tolerance < MIN_TOLERANCE) {
262 throw new IllegalArgumentException();
263 }
264 this.tolerance = tolerance;
265 }
266 }