tree 4e0a181c1728c15c11cc4b1b1de1870bf97d1c3f
parent 3e6ef29be6f3cd672a73cefb52838832a49e5427
author Sameer Agarwal <sameeragarwal@google.com> 1376979209 -0700
committer Keir Mierle <mierle@gmail.com> 1377029363 +0000

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