Improve inner iteration step acceptance.
Normally, in a trust region algorithm the quality of a trust region step
is measured by the ratio
nonlinear_cost_change
r = ---------------------
model_cost_change
All the change in the nonlinear objective is due to the trust region step
so this ratio is a good measure of the quality of the trust region radius.
However, when inner iterations are being used, nonlinear_cost_change
includes the contribution of the inner iterations and its not fair to
credit it all to the trust region algorithm. So we change the ratio to be
nonlinear_cost_change
r = ------------------------------------------------
(model_cost_change + inner_iteration_cost_change)
In most cases this is fine, but it can be the case that the
change in solution quality due to inner iterations is so large
and the trust region step is so bad, that this ratio can become
quite small.
This can cause the trust region loop to reject this step.
This change, fixes this problem by looking at the inner_iteration_cost_change
explicitly and accepting a step if the inner iterations led to a net
decrease in the objective function value.
Along the way it also fixes the way model_cost_change is computed.
Changing to a more numerically robust way of computing it.
The last and final change is to ensure that inner iterations and the
non-monotonic version of the trust region algorithm interact correctly.
This addresses part 2 of
https://code.google.com/p/ceres-solver/issues/detail?id=115
As an illustration of the change.
Before this change
[master] build: ./bin/bundle_adjuster --input ~/Downloads/problem-245-198739-pre.txt -num_iterations 10 -translation_sigma 0.01 -rotation_sigma 0.001 -point_sigma 0.1 -inner_iterations -num_threads 4
0: f: 7.731660e+15 d: 0.00e+00 g: 3.51e+12 h: 0.00e+00 rho: 0.00e+00 mu: 1.00e+04 li: 0 it: 5.87e-01 tt: 9.37e+00
1: f: 7.731660e+15 d: 7.73e+15 g: 0.00e+00 h: 1.20e+10 rho: 2.43e-11 mu: 5.00e+03 li: 1 it: 1.41e+01 tt: 2.35e+01
2: f: 7.731660e+15 d: 7.73e+15 g: 0.00e+00 h: 1.25e+10 rho: 1.70e-07 mu: 1.25e+03 li: 1 it: 1.86e+01 tt: 4.22e+01
3: f: 7.731660e+15 d:-2.39e+40 g: 0.00e+00 h: 3.53e+10 rho:-2.63e-13 mu: 1.56e+02 li: 1 it: 3.35e+01 tt: 7.57e+01
4: f: 7.731660e+15 d:-1.66e+39 g: 0.00e+00 h: 1.21e+11 rho:-6.58e-15 mu: 9.77e+00 li: 1 it: 3.86e+01 tt: 1.14e+02
5: f: 7.731660e+15 d:-3.57e+55 g: 0.00e+00 h: 5.00e+12 rho:-1.89e-14 mu: 3.05e-01 li: 1 it: 3.84e+01 tt: 1.53e+02
6: f: 7.731660e+15 d:-2.26e+35 g: 0.00e+00 h: 3.82e+12 rho:-1.77e-20 mu: 4.77e-03 li: 1 it: 3.45e+01 tt: 1.87e+02
7: f: 7.731660e+15 d:-5.31e+19 g: 0.00e+00 h: 1.22e+11 rho:-9.96e-21 mu: 3.73e-05 li: 1 it: 2.77e+01 tt: 2.15e+02
8: f: 1.784990e+08 d: 7.73e+15 g: 4.13e+07 h: 1.20e+10 rho: 1.00e+00 mu: 1.12e-04 li: 1 it: 1.13e+01 tt: 2.26e+02
9: f: 1.524025e+08 d: 2.61e+07 g: 5.81e+10 h: 2.41e+08 rho: 1.00e+00 mu: 3.35e-04 li: 1 it: 1.13e+01 tt: 2.37e+02
10: f: 1.488524e+08 d: 3.55e+06 g: 2.79e+09 h: 5.01e+08 rho: 1.00e+00 mu: 1.01e-03 li: 1 it: 1.09e+01 tt: 2.48e+02
After this change
[inner] build: ./bin/bundle_adjuster --input ~/Downloads/problem-245-198739-pre.txt -num_iterations 10 -translation_sigma 0.01 -rotation_sigma 0.001 -point_sigma 0.1 -inner_iterations -num_threads 4
0: f: 7.731660e+15 d: 0.00e+00 g: 3.51e+12 h: 0.00e+00 rho: 0.00e+00 mu: 1.00e+04 li: 0 it: 5.66e-01 tt: 9.31e+00
1: f: 5.941477e+09 d: 7.73e+15 g: 1.20e+18 h: 1.20e+10 rho: 2.43e-11 mu: 5.00e+03 li: 1 it: 1.38e+01 tt: 2.32e+01
2: f: 3.341986e+08 d: 5.61e+09 g: 1.42e+14 h: 1.37e+09 rho: 9.38e-08 mu: 2.50e+03 li: 1 it: 1.30e+01 tt: 3.61e+01
3: f: 3.241492e+08 d: 1.00e+07 g: 3.64e+13 h: 8.26e+08 rho: 6.12e-08 mu: 1.25e+03 li: 1 it: 1.15e+01 tt: 4.77e+01
4: f: 3.152280e+08 d: 8.92e+06 g: 2.02e+13 h: 2.95e+08 rho: 1.56e-05 mu: 6.25e+02 li: 1 it: 1.11e+01 tt: 5.88e+01
5: f: 3.078535e+08 d: 7.37e+06 g: 9.72e+12 h: 4.57e+08 rho: 6.55e-09 mu: 3.13e+02 li: 1 it: 1.16e+01 tt: 7.04e+01
6: f: 3.025353e+08 d: 5.32e+06 g: 1.33e+13 h: 2.14e+08 rho: 7.21e-01 mu: 3.42e+02 li: 1 it: 1.14e+01 tt: 8.18e+01
7: f: 2.908298e+08 d: 1.17e+07 g: 5.97e+12 h: 7.25e+08 rho: 5.73e-01 mu: 3.43e+02 li: 1 it: 1.08e+01 tt: 9.26e+01
8: f: 2.803927e+08 d: 1.04e+07 g: 1.07e+12 h: 9.72e+07 rho: 5.27e-01 mu: 3.43e+02 li: 1 it: 1.03e+01 tt: 1.03e+02
9: f: 2.767074e+08 d: 3.69e+06 g: 2.10e+11 h: 7.35e+07 rho: 7.37e-01 mu: 3.84e+02 li: 1 it: 1.03e+01 tt: 1.13e+02
10: f: 2.744282e+08 d: 2.28e+06 g: 2.17e+11 h: 1.23e+08 rho: 3.11e-01 mu: 3.64e+02 li: 1 it: 9.61e+00 tt: 1.23e+02
Change-Id: I7c3b132f7ce62719795bfa489ec2276d0455cc97
1 file changed
