)]}'
{
  "commit": "e45db9d05aaa26b1ddffa44c9190a1018aa2655f",
  "tree": "4e0a181c1728c15c11cc4b1b1de1870bf97d1c3f",
  "parents": [
    "3e6ef29be6f3cd672a73cefb52838832a49e5427"
  ],
  "author": {
    "name": "Sameer Agarwal",
    "email": "sameeragarwal@google.com",
    "time": "Mon Aug 19 23:13:29 2013 -0700"
  },
  "committer": {
    "name": "Keir Mierle",
    "email": "mierle@gmail.com",
    "time": "Tue Aug 20 20:09:23 2013 +0000"
  },
  "message": "Improve inner iteration step acceptance.\n\nNormally, in a trust region algorithm the quality of a trust region step\nis measured by the ratio\n\n          nonlinear_cost_change\n   r \u003d    ---------------------\n          model_cost_change\n\nAll the change in the nonlinear objective is due to the trust region step\nso this ratio is a good measure of the quality of the trust region radius.\n\nHowever, when inner iterations are being used, nonlinear_cost_change\nincludes the contribution of the inner iterations and its not fair to\ncredit it all to the trust region algorithm. So we change the ratio to be\n\n                     nonlinear_cost_change\n   r \u003d    ------------------------------------------------\n          (model_cost_change + inner_iteration_cost_change)\n\nIn most cases this is fine, but it can be the case that the\nchange in solution quality due to inner iterations is so large\nand the trust region step is so bad, that this ratio can become\nquite small.\n\nThis can cause the trust region loop to reject this step.\n\nThis change, fixes this problem by looking at the inner_iteration_cost_change\nexplicitly and accepting a step if the inner iterations led to a net\ndecrease in the objective function value.\n\nAlong the way it also fixes the way model_cost_change is computed.\nChanging to a more numerically robust way of computing it.\n\nThe last and final change is to ensure that inner iterations and the\nnon-monotonic version of the trust region algorithm interact correctly.\n\nThis addresses part 2 of\n\nhttps://code.google.com/p/ceres-solver/issues/detail?id\u003d115\n\nAs an illustration of the change.\n\nBefore this change\n\n[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\n   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\n   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\n   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\n   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\n   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\n   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\n   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\n   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\n   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\n   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\n  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\n\nAfter this change\n\n[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\n   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\n   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\n   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\n   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\n   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\n   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\n   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\n   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\n   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\n   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\n  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\n\nChange-Id: I7c3b132f7ce62719795bfa489ec2276d0455cc97\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "d6ae0ab1adf88b86e44b4f58e8e83efc403625cd",
      "old_mode": 33188,
      "old_path": "internal/ceres/trust_region_minimizer.cc",
      "new_id": "dc1d009907cbcbd880e78e238bdbbe58596a641c",
      "new_mode": 33188,
      "new_path": "internal/ceres/trust_region_minimizer.cc"
    }
  ]
}