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.

ExampleUnconstrainedMinimization.java

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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
public static void main(String[] args) {

    UnconstrainedMinimization optimizer = FactoryOptimization.quasiNewtonBfgs(null);

    // Send to standard out progress information
    optimizer.setVerbose(System.out,0);

    // Provide an analytical gradient to the Rosenbrock function.
    optimizer.setFunction(new Rosenbrock(),new Gradient(),0);

    // [-1.2,  1] is the recommended starting point for testing
    optimizer.initialize(new double[]{-1.2,1},1e-12,1e-12);

    // iterate 500 times or until it converges.
    // Manually iteration is possible too if more control over is required
    UtilOptimize.process(optimizer,500);

    double found[] = optimizer.getParameters();

    // see how accurately it found the solution
    System.out.println("Final Error = "+optimizer.getFunctionValue());

    // Compare the actual parameters to the found parameters
    System.out.printf("x[0]: expected=1.00  found=%5.2f\n",found[0]);
    System.out.printf("x[1]: expected=1.00  found=%5.2f\n",found[1]);
}

/**
 * A classic function used to test optimization routines
 */
public static class Rosenbrock implements FunctionNtoS {

    @Override
    public int getNumOfInputsN() { return 2; }

    @Override
    public double process(double[] input) {
        double x1 = input[0];
        double x2 = input[1];
        double f1 = 10*(x2 - x1*x1);
        double f2 = 1-x1;
        return f1*f1 + f2*f2;
    }
}

/**
 * Gradient of the Rosenbrock function. You can check analytical gradients using the DerivativeChecker class.
 */
public static class Gradient implements FunctionNtoN {

    @Override
    public int getN() { return 2; }

    @Override
    public void process(double[] input, double[] output) {
        double x1 = input[0];
        double x2 = input[1];

        output[0] = -400*(x2-x1*x1)*x1 - 2*(1-x1);
        output[1] = 200*(x2-x1*x1);
    }
}

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