1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 package org.apache.commons.math4.legacy.optim.nonlinear.scalar.gradient;
19
20 import org.apache.commons.geometry.euclidean.twod.Vector2D;
21 import org.apache.commons.math4.legacy.analysis.MultivariateFunction;
22 import org.apache.commons.math4.legacy.analysis.MultivariateVectorFunction;
23 import org.apache.commons.math4.legacy.exception.MathUnsupportedOperationException;
24 import org.apache.commons.math4.legacy.linear.BlockRealMatrix;
25 import org.apache.commons.math4.legacy.linear.RealMatrix;
26 import org.apache.commons.math4.legacy.optim.InitialGuess;
27 import org.apache.commons.math4.legacy.optim.MaxEval;
28 import org.apache.commons.math4.legacy.optim.PointValuePair;
29 import org.apache.commons.math4.legacy.optim.SimpleBounds;
30 import org.apache.commons.math4.legacy.optim.SimpleValueChecker;
31 import org.apache.commons.math4.legacy.optim.nonlinear.scalar.GoalType;
32 import org.apache.commons.math4.legacy.optim.nonlinear.scalar.ObjectiveFunction;
33 import org.apache.commons.math4.legacy.optim.nonlinear.scalar.ObjectiveFunctionGradient;
34 import org.apache.commons.math4.legacy.optim.nonlinear.scalar.LineSearchTolerance;
35 import org.junit.Assert;
36 import org.junit.Test;
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101 public class NonLinearConjugateGradientOptimizerTest {
102 @Test(expected=MathUnsupportedOperationException.class)
103 public void testBoundsUnsupported() {
104 LinearProblem problem
105 = new LinearProblem(new double[][] { { 2 } }, new double[] { 3 });
106 NonLinearConjugateGradientOptimizer optimizer
107 = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
108 new SimpleValueChecker(1e-6, 1e-6));
109 optimizer.optimize(new MaxEval(100),
110 problem.getObjectiveFunction(),
111 problem.getObjectiveFunctionGradient(),
112 GoalType.MINIMIZE,
113 new InitialGuess(new double[] { 0 }),
114 new SimpleBounds(new double[] { -1 },
115 new double[] { 1 }),
116 new LineSearchTolerance(1e-3, 1e-3, 1));
117 }
118
119 @Test
120 public void testTrivial() {
121 LinearProblem problem
122 = new LinearProblem(new double[][] { { 2 } }, new double[] { 3 });
123 NonLinearConjugateGradientOptimizer optimizer
124 = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
125 new SimpleValueChecker(1e-6, 1e-6));
126 PointValuePair optimum
127 = optimizer.optimize(new MaxEval(100),
128 problem.getObjectiveFunction(),
129 problem.getObjectiveFunctionGradient(),
130 GoalType.MINIMIZE,
131 new InitialGuess(new double[] { 0 }),
132 new LineSearchTolerance(1e-3, 1e-3, 1));
133 Assert.assertEquals(1.5, optimum.getPoint()[0], 1.0e-10);
134 Assert.assertEquals(0.0, optimum.getValue(), 1.0e-10);
135
136
137 Assert.assertTrue(optimizer.getIterations() > 0);
138 }
139
140 @Test
141 public void testColumnsPermutation() {
142 LinearProblem problem
143 = new LinearProblem(new double[][] { { 1.0, -1.0 }, { 0.0, 2.0 }, { 1.0, -2.0 } },
144 new double[] { 4.0, 6.0, 1.0 });
145
146 NonLinearConjugateGradientOptimizer optimizer
147 = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
148 new SimpleValueChecker(1e-6, 1e-6));
149 PointValuePair optimum
150 = optimizer.optimize(new MaxEval(100),
151 problem.getObjectiveFunction(),
152 problem.getObjectiveFunctionGradient(),
153 GoalType.MINIMIZE,
154 new InitialGuess(new double[] { 0, 0 }),
155 new LineSearchTolerance(1e-3, 1e-3, 1));
156 Assert.assertEquals(7.0, optimum.getPoint()[0], 1.0e-10);
157 Assert.assertEquals(3.0, optimum.getPoint()[1], 1.0e-10);
158 Assert.assertEquals(0.0, optimum.getValue(), 1.0e-10);
159 }
160
161 @Test
162 public void testNoDependency() {
163 LinearProblem problem = new LinearProblem(new double[][] {
164 { 2, 0, 0, 0, 0, 0 },
165 { 0, 2, 0, 0, 0, 0 },
166 { 0, 0, 2, 0, 0, 0 },
167 { 0, 0, 0, 2, 0, 0 },
168 { 0, 0, 0, 0, 2, 0 },
169 { 0, 0, 0, 0, 0, 2 }
170 }, new double[] { 0.0, 1.1, 2.2, 3.3, 4.4, 5.5 });
171 NonLinearConjugateGradientOptimizer optimizer
172 = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
173 new SimpleValueChecker(1e-6, 1e-6));
174 PointValuePair optimum
175 = optimizer.optimize(new MaxEval(100),
176 problem.getObjectiveFunction(),
177 problem.getObjectiveFunctionGradient(),
178 GoalType.MINIMIZE,
179 new InitialGuess(new double[] { 0, 0, 0, 0, 0, 0 }),
180 new LineSearchTolerance(1e-3, 1e-3, 1));
181 for (int i = 0; i < problem.target.length; ++i) {
182 Assert.assertEquals(0.55 * i, optimum.getPoint()[i], 1.0e-10);
183 }
184 }
185
186 @Test
187 public void testOneSet() {
188 LinearProblem problem = new LinearProblem(new double[][] {
189 { 1, 0, 0 },
190 { -1, 1, 0 },
191 { 0, -1, 1 }
192 }, new double[] { 1, 1, 1});
193 NonLinearConjugateGradientOptimizer optimizer
194 = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
195 new SimpleValueChecker(1e-6, 1e-6));
196 PointValuePair optimum
197 = optimizer.optimize(new MaxEval(100),
198 problem.getObjectiveFunction(),
199 problem.getObjectiveFunctionGradient(),
200 GoalType.MINIMIZE,
201 new InitialGuess(new double[] { 0, 0, 0 }),
202 new LineSearchTolerance(1e-3, 1e-3, 1));
203 Assert.assertEquals(1.0, optimum.getPoint()[0], 1.0e-10);
204 Assert.assertEquals(2.0, optimum.getPoint()[1], 1.0e-10);
205 Assert.assertEquals(3.0, optimum.getPoint()[2], 1.0e-10);
206 }
207
208 @Test
209 public void testTwoSets() {
210 final double epsilon = 1.0e-7;
211 LinearProblem problem = new LinearProblem(new double[][] {
212 { 2, 1, 0, 4, 0, 0 },
213 { -4, -2, 3, -7, 0, 0 },
214 { 4, 1, -2, 8, 0, 0 },
215 { 0, -3, -12, -1, 0, 0 },
216 { 0, 0, 0, 0, epsilon, 1 },
217 { 0, 0, 0, 0, 1, 1 }
218 }, new double[] { 2, -9, 2, 2, 1 + epsilon * epsilon, 2});
219
220 final Preconditioner preconditioner
221 = new Preconditioner() {
222 @Override
223 public double[] precondition(double[] point, double[] r) {
224 double[] d = r.clone();
225 d[0] /= 72.0;
226 d[1] /= 30.0;
227 d[2] /= 314.0;
228 d[3] /= 260.0;
229 d[4] /= 2 * (1 + epsilon * epsilon);
230 d[5] /= 4.0;
231 return d;
232 }
233 };
234
235 NonLinearConjugateGradientOptimizer optimizer
236 = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
237 new SimpleValueChecker(1e-13, 1e-13),
238 preconditioner);
239
240 PointValuePair optimum
241 = optimizer.optimize(new MaxEval(100),
242 problem.getObjectiveFunction(),
243 problem.getObjectiveFunctionGradient(),
244 GoalType.MINIMIZE,
245 new InitialGuess(new double[] { 0, 0, 0, 0, 0, 0 }),
246 new LineSearchTolerance(1e-7, 1e-7, 1));
247
248 final double[] result = optimum.getPoint();
249 final double[] expected = {3, 4, -1, -2, 1 + epsilon, 1 - epsilon};
250
251 Assert.assertEquals(expected[0], result[0], 1.0e-7);
252 Assert.assertEquals(expected[1], result[1], 1.0e-7);
253 Assert.assertEquals(expected[2], result[2], 1.0e-9);
254 Assert.assertEquals(expected[3], result[3], 1.0e-8);
255 Assert.assertEquals(expected[4] + epsilon, result[4], 1.0e-6);
256 Assert.assertEquals(expected[5] - epsilon, result[5], 1.0e-6);
257 }
258
259 @Test
260 public void testNonInversible() {
261 LinearProblem problem = new LinearProblem(new double[][] {
262 { 1, 2, -3 },
263 { 2, 1, 3 },
264 { -3, 0, -9 }
265 }, new double[] { 1, 1, 1 });
266 NonLinearConjugateGradientOptimizer optimizer
267 = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
268 new SimpleValueChecker(1e-6, 1e-6));
269 PointValuePair optimum
270 = optimizer.optimize(new MaxEval(100),
271 problem.getObjectiveFunction(),
272 problem.getObjectiveFunctionGradient(),
273 GoalType.MINIMIZE,
274 new InitialGuess(new double[] { 0, 0, 0 }),
275 new LineSearchTolerance(1e-3, 1e-3, 1));
276 Assert.assertTrue(optimum.getValue() > 0.5);
277 }
278
279 @Test
280 public void testIllConditioned() {
281 LinearProblem problem1 = new LinearProblem(new double[][] {
282 { 10.0, 7.0, 8.0, 7.0 },
283 { 7.0, 5.0, 6.0, 5.0 },
284 { 8.0, 6.0, 10.0, 9.0 },
285 { 7.0, 5.0, 9.0, 10.0 }
286 }, new double[] { 32, 23, 33, 31 });
287 NonLinearConjugateGradientOptimizer optimizer
288 = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
289 new SimpleValueChecker(1e-13, 1e-13));
290 PointValuePair optimum1
291 = optimizer.optimize(new MaxEval(200),
292 problem1.getObjectiveFunction(),
293 problem1.getObjectiveFunctionGradient(),
294 GoalType.MINIMIZE,
295 new InitialGuess(new double[] { 0, 1, 2, 3 }),
296 new LineSearchTolerance(1e-15, 1e-15, 1));
297 Assert.assertEquals(1.0, optimum1.getPoint()[0], 1.0e-4);
298 Assert.assertEquals(1.0, optimum1.getPoint()[1], 1.0e-3);
299 Assert.assertEquals(1.0, optimum1.getPoint()[2], 1.0e-4);
300 Assert.assertEquals(1.0, optimum1.getPoint()[3], 1.0e-4);
301
302 LinearProblem problem2 = new LinearProblem(new double[][] {
303 { 10.00, 7.00, 8.10, 7.20 },
304 { 7.08, 5.04, 6.00, 5.00 },
305 { 8.00, 5.98, 9.89, 9.00 },
306 { 6.99, 4.99, 9.00, 9.98 }
307 }, new double[] { 32, 23, 33, 31 });
308 PointValuePair optimum2
309 = optimizer.optimize(new MaxEval(200),
310 problem2.getObjectiveFunction(),
311 problem2.getObjectiveFunctionGradient(),
312 GoalType.MINIMIZE,
313 new InitialGuess(new double[] { 0, 1, 2, 3 }));
314
315 final double[] result2 = optimum2.getPoint();
316 final double[] expected2 = {-81, 137, -34, 22};
317
318 Assert.assertEquals(expected2[0], result2[0], 2);
319 Assert.assertEquals(expected2[1], result2[1], 4);
320 Assert.assertEquals(expected2[2], result2[2], 1);
321 Assert.assertEquals(expected2[3], result2[3], 1);
322 }
323
324 @Test
325 public void testMoreEstimatedParametersSimple() {
326 LinearProblem problem = new LinearProblem(new double[][] {
327 { 3.0, 2.0, 0.0, 0.0 },
328 { 0.0, 1.0, -1.0, 1.0 },
329 { 2.0, 0.0, 1.0, 0.0 }
330 }, new double[] { 7.0, 3.0, 5.0 });
331
332 NonLinearConjugateGradientOptimizer optimizer
333 = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
334 new SimpleValueChecker(1e-6, 1e-6));
335 PointValuePair optimum
336 = optimizer.optimize(new MaxEval(100),
337 problem.getObjectiveFunction(),
338 problem.getObjectiveFunctionGradient(),
339 GoalType.MINIMIZE,
340 new InitialGuess(new double[] { 7, 6, 5, 4 }),
341 new LineSearchTolerance(1e-3, 1e-3, 1));
342 Assert.assertEquals(0, optimum.getValue(), 1.0e-10);
343 }
344
345 @Test
346 public void testMoreEstimatedParametersUnsorted() {
347 LinearProblem problem = new LinearProblem(new double[][] {
348 { 1.0, 1.0, 0.0, 0.0, 0.0, 0.0 },
349 { 0.0, 0.0, 1.0, 1.0, 1.0, 0.0 },
350 { 0.0, 0.0, 0.0, 0.0, 1.0, -1.0 },
351 { 0.0, 0.0, -1.0, 1.0, 0.0, 1.0 },
352 { 0.0, 0.0, 0.0, -1.0, 1.0, 0.0 }
353 }, new double[] { 3.0, 12.0, -1.0, 7.0, 1.0 });
354 NonLinearConjugateGradientOptimizer optimizer
355 = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
356 new SimpleValueChecker(1e-6, 1e-6));
357 PointValuePair optimum
358 = optimizer.optimize(new MaxEval(100),
359 problem.getObjectiveFunction(),
360 problem.getObjectiveFunctionGradient(),
361 GoalType.MINIMIZE,
362 new InitialGuess(new double[] { 2, 2, 2, 2, 2, 2 }),
363 new LineSearchTolerance(1e-3, 1e-3, 1));
364 Assert.assertEquals(0, optimum.getValue(), 1.0e-10);
365 }
366
367 @Test
368 public void testRedundantEquations() {
369 LinearProblem problem = new LinearProblem(new double[][] {
370 { 1.0, 1.0 },
371 { 1.0, -1.0 },
372 { 1.0, 3.0 }
373 }, new double[] { 3.0, 1.0, 5.0 });
374
375 NonLinearConjugateGradientOptimizer optimizer
376 = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
377 new SimpleValueChecker(1e-6, 1e-6));
378 PointValuePair optimum
379 = optimizer.optimize(new MaxEval(100),
380 problem.getObjectiveFunction(),
381 problem.getObjectiveFunctionGradient(),
382 GoalType.MINIMIZE,
383 new InitialGuess(new double[] { 1, 1 }),
384 new LineSearchTolerance(1e-3, 1e-3, 1));
385 Assert.assertEquals(2.0, optimum.getPoint()[0], 1.0e-8);
386 Assert.assertEquals(1.0, optimum.getPoint()[1], 1.0e-8);
387 }
388
389 @Test
390 public void testInconsistentEquations() {
391 LinearProblem problem = new LinearProblem(new double[][] {
392 { 1.0, 1.0 },
393 { 1.0, -1.0 },
394 { 1.0, 3.0 }
395 }, new double[] { 3.0, 1.0, 4.0 });
396
397 NonLinearConjugateGradientOptimizer optimizer
398 = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
399 new SimpleValueChecker(1e-6, 1e-6));
400 PointValuePair optimum
401 = optimizer.optimize(new MaxEval(100),
402 problem.getObjectiveFunction(),
403 problem.getObjectiveFunctionGradient(),
404 GoalType.MINIMIZE,
405 new InitialGuess(new double[] { 1, 1 }),
406 new LineSearchTolerance(1e-3, 1e-3, 1));
407 Assert.assertTrue(optimum.getValue() > 0.1);
408 }
409
410 @Test
411 public void testCircleFitting() {
412 CircleScalar problem = new CircleScalar();
413 problem.addPoint( 30.0, 68.0);
414 problem.addPoint( 50.0, -6.0);
415 problem.addPoint(110.0, -20.0);
416 problem.addPoint( 35.0, 15.0);
417 problem.addPoint( 45.0, 97.0);
418 NonLinearConjugateGradientOptimizer optimizer
419 = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
420 new SimpleValueChecker(1e-30, 1e-30));
421 PointValuePair optimum
422 = optimizer.optimize(new MaxEval(100),
423 problem.getObjectiveFunction(),
424 problem.getObjectiveFunctionGradient(),
425 GoalType.MINIMIZE,
426 new InitialGuess(new double[] { 98.680, 47.345 }),
427 new LineSearchTolerance(1e-15, 1e-13, 1));
428 Vector2D center = Vector2D.of(optimum.getPointRef()[0], optimum.getPointRef()[1]);
429 Assert.assertEquals(69.960161753, problem.getRadius(center), 1.0e-8);
430 Assert.assertEquals(96.075902096, center.getX(), 1.0e-7);
431 Assert.assertEquals(48.135167894, center.getY(), 1.0e-6);
432 }
433
434 private static final class LinearProblem {
435 private final RealMatrix factors;
436 private final double[] target;
437
438 LinearProblem(double[][] factors,
439 double[] target) {
440 this.factors = new BlockRealMatrix(factors);
441 this.target = target;
442 }
443
444 public ObjectiveFunction getObjectiveFunction() {
445 return new ObjectiveFunction(new MultivariateFunction() {
446 @Override
447 public double value(double[] point) {
448 double[] y = factors.operate(point);
449 double sum = 0;
450 for (int i = 0; i < y.length; ++i) {
451 double ri = y[i] - target[i];
452 sum += ri * ri;
453 }
454 return sum;
455 }
456 });
457 }
458
459 public ObjectiveFunctionGradient getObjectiveFunctionGradient() {
460 return new ObjectiveFunctionGradient(new MultivariateVectorFunction() {
461 @Override
462 public double[] value(double[] point) {
463 double[] r = factors.operate(point);
464 for (int i = 0; i < r.length; ++i) {
465 r[i] -= target[i];
466 }
467 double[] p = factors.transpose().operate(r);
468 for (int i = 0; i < p.length; ++i) {
469 p[i] *= 2;
470 }
471 return p;
472 }
473 });
474 }
475 }
476 }