Non-Linear MinimizationΒΆ
The following code demonstrates non-linear minimization by minimizing a classic test problem, Rosenbrock. See the optimization manual for an overview of all optimization techniques available in DDogleg. Unconstrained minimization solves problems which can be described by a function of the form:
\[\min\limits_{\boldsymbol{x} \in \Re^N} f(\boldsymbol{x})\]
where \(f(\boldsymbol{x})\) is a function with a scalar output but takes in m variables. The actual formula being minimized is:
\[f(\boldsymbol{x}) = 100(x_2 - x_1^2)^2 + (1-x_1)^2\]
We will use Quasi-Newton BFGS to solve this problem. There are other options available. See the manual referenced above for a list.
Here it is shown how to set up and perform the optimization. DDogleg is a bit unusual in that it allows you to invoke each step of the optimization manually. The advantage of that is that it is very easy to abort your optimization early if you run out of time. For sake of brevity, we use UtilProcess.optimize() to handle the iterations.
1public static void main( String[] args ) {
2
3 UnconstrainedMinimization optimizer = FactoryOptimization.quasiNewtonBfgs(null);
4
5 // Send to standard out progress information
6 optimizer.setVerbose(System.out, 0);
7
8 // Provide an analytical gradient to the Rosenbrock function.
9 optimizer.setFunction(new Rosenbrock(), new Gradient(), 0);
10
11 // [-1.2, 1] is the recommended starting point for testing
12 optimizer.initialize(new double[]{-1.2, 1}, 1e-12, 1e-12);
13
14 // iterate 500 times or until it converges.
15 // Manually iteration is possible too if more control over is required
16 UtilOptimize.process(optimizer, 500);
17
18 double[] found = optimizer.getParameters();
19
20 // see how accurately it found the solution
21 System.out.println("Final Error = " + optimizer.getFunctionValue());
22
23 // Compare the actual parameters to the found parameters
24 System.out.printf("x[0]: expected=1.00 found=%5.2f\n", found[0]);
25 System.out.printf("x[1]: expected=1.00 found=%5.2f\n", found[1]);
26}
27
28/**
29 * A classic function used to test optimization routines
30 */
31public static class Rosenbrock implements FunctionNtoS {
32
33 @Override
34 public int getNumOfInputsN() {return 2;}
35
36 @Override
37 public double process( double[] input ) {
38 double x1 = input[0];
39 double x2 = input[1];
40 double f1 = 10*(x2 - x1*x1);
41 double f2 = 1 - x1;
42 return f1*f1 + f2*f2;
43 }
44}
45
46/**
47 * Gradient of the Rosenbrock function. You can check analytical gradients using the DerivativeChecker class.
48 */
49public static class Gradient implements FunctionNtoN {
50
51 @Override
52 public int getN() {return 2;}
53
54 @Override
55 public void process( double[] input, double[] output ) {
56 double x1 = input[0];
57 double x2 = input[1];
58
59 output[0] = -400*(x2 - x1*x1)*x1 - 2*(1 - x1);
60 output[1] = 200*(x2 - x1*x1);
61 }
62}
When you run this example you should see something like the following:
Steps fx change |step| f-test g-test max-step
0 2.420E+01 0.000E+00 0.000E+00 0.000E+00 0.000E+00 0.00
1 6.668E+00 -1.753E+01 1.155E-01 7.245E-01 5.423E+04 0.000
2 5.971E+00 -6.970E-01 5.935E-01 1.045E-01 8.881E+00 0.834
3 4.464E+00 -1.507E+00 5.147E-01 2.524E-01 4.427E+00 1.499
4 3.786E+00 -6.783E-01 2.724E-01 1.520E-01 1.793E+00 2.766
5 3.522E+00 -2.631E-01 2.041E-01 6.951E-02 2.653E+00 1.585
6 3.435E+00 -8.726E-02 1.235E-01 2.477E-02 1.359E-01 28.790
7 3.268E+00 -1.675E-01 9.137E-02 4.877E-02 1.905E-01 20.038
8 2.673E+00 -5.949E-01 2.624E-01 1.821E-01 8.482E-01 4.280
9 2.230E+00 -4.424E-01 1.366E-01 1.655E-01 5.993E-01 4.955
10 2.073E+00 -1.569E-01 1.235E-01 7.034E-02 1.032E+00 2.401
11 1.846E+00 -2.275E-01 2.121E-01 1.097E-01 4.803E-01 4.797
12 1.483E+00 -3.628E-01 4.316E-02 1.965E-01 5.765E-01 3.558
13 1.202E+00 -2.808E-01 1.700E-01 1.893E-01 3.936E-01 4.187
14 1.022E+00 -1.804E-01 1.021E-01 1.501E-01 2.538E-01 5.264
15 7.432E-01 -2.788E-01 1.210E-01 2.728E-01 5.720E-01 1.985
16 5.855E-01 -1.576E-01 9.319E-02 2.121E-01 6.269E-01 1.317
17 5.435E-01 -4.203E-02 5.386E-02 7.178E-02 2.352E-01 2.766
18 4.885E-01 -5.499E-02 5.700E-02 1.012E-01 6.820E-02 8.855
19 3.546E-01 -1.340E-01 1.241E-01 2.742E-01 1.875E-01 2.895
20 2.481E-01 -1.064E-01 1.025E-01 3.002E-01 1.542E-01 2.554
21 2.047E-01 -4.349E-02 8.608E-02 1.753E-01 2.001E-01 1.378
22 1.626E-01 -4.202E-02 1.435E-01 2.053E-01 8.241E-02 2.759
23 1.011E-01 -6.157E-02 5.607E-02 3.786E-01 9.326E-02 1.938
24 6.181E-02 -3.925E-02 1.554E-01 3.884E-01 5.910E-02 1.900
25 3.614E-02 -2.567E-02 9.138E-02 4.153E-01 3.412E-02 2.013
26 1.792E-02 -1.822E-02 9.033E-02 5.042E-01 2.615E-02 1.536
27 1.300E-02 -4.922E-03 6.171E-02 2.747E-01 3.139E-02 0.634
28 5.615E-03 -7.383E-03 8.493E-02 5.680E-01 1.078E-02 1.340
29 1.897E-03 -3.719E-03 4.135E-02 6.622E-01 7.170E-03 0.870
30 5.239E-04 -1.373E-03 5.140E-02 7.238E-01 3.208E-03 0.657
31 1.269E-04 -3.969E-04 2.623E-02 7.577E-01 6.748E-04 0.863
32 2.780E-05 -9.911E-05 7.687E-03 7.810E-01 2.288E-04 0.616
33 5.694E-06 -2.210E-05 5.876E-03 7.952E-01 5.209E-05 0.593
34 1.141E-06 -4.553E-06 2.386E-03 7.996E-01 1.090E-05 0.581
35 2.268E-07 -9.144E-07 1.150E-03 8.012E-01 2.233E-06 0.568
36 4.493E-08 -1.819E-07 4.986E-04 8.019E-01 4.492E-07 0.561
37 8.885E-09 -3.604E-08 2.261E-04 8.022E-01 8.945E-08 0.558
38 1.756E-09 -7.129E-09 9.970E-05 8.024E-01 1.773E-08 0.557
39 3.469E-10 -1.409E-09 4.456E-05 8.024E-01 3.509E-09 0.556
40 6.854E-11 -2.784E-10 1.976E-05 8.024E-01 6.936E-10 0.556
41 1.354E-11 -5.500E-11 8.795E-06 8.025E-01 1.371E-10 0.556
42 2.674E-12 -1.086E-11 3.906E-06 8.025E-01 2.708E-11 0.556
43 5.283E-13 -2.146E-12 1.737E-06 8.025E-01 5.349E-12 0.556
44 1.044E-13 -4.239E-13 7.717E-07 8.025E-01 1.057E-12 0.556
finished select direction, gtest=2.087077e-13
Final Error = 1.0435458524039463E-13
x[0]: expected=1.00 found= 1.00
x[1]: expected=1.00 found= 1.00