Optimization on rotation between two point sets not converge

[Rick Liu]

Hi,

I am trying to solving an ICP problem with rotation only, the source code are quite simple: https://paste.ubuntu.com/p/M2kdkBZfpc/ .

The problem is the optimization can not converge (see output in https://paste.ubuntu.com/p/5bbbvGH2PP/).

However, when i add one more redisual block as following:

problem.AddResidualBlock(CostFunctor::Create({0, 2, 2}, {0, 2, 2}), nullptr, q.coeffs().data());

The optimization converges properly. 

Thanks for explaining why the latter converges while the former not.

[Dmitriy Korchemkin]

Hi,

Ceres-solver is a local minimizer and is not expected to provide a globally-optimal solution.

I would suggest initializing the solver using some sort of closed-form least-squares solution (for example, utilizing part of umeyama algorithm) and then - polishing result using ceres-solver with robust loss functions and whats not.

In the first case optimization converges to quaternion (x=0,y=1,z=0,w=0), if you evaluate your cost-function at this point - you can see that gradient vanishes at this point.

Thus, first-order optimality condition is satisfied at this point; I suppose [suppose - since first order optimality condition is not a sufficient condition] that this point as well as (x=1,y=0,z=0,w=0) and (x=0,y=0,z=1,w=0) are local minimas of optimization problem from the first case.

In the second case first-order optimality conditions remain satisfied at (x=1,y=0,z=0,w=0) point, and there is also another "supposedly" local minima at (x=0, y=0.484768546026564, z=0.874642473690417, w=0).

Thus, the fact that you receive (0,0,0,w=1) as the answer is just a matter of "luck" and starting point being "closer" in some sense to this local minima than to another.

[Rick Liu]

The problem is that when I increase the residual blocks number from 3 to 4, the optimization will be not sensitive to initial value.

In other words, are there some methods to determine the converge region close to the global minimum point, or determine how many local minimum points in a specified region?

--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/9b6d0374-9439-413c-a17a-1749a490375an%40googlegroups.com.

[Dmitriy Korchemkin]

> The problem is that when I increase the residual blocks number from 3 to 4, the optimization will be not sensitive to initial value.

As I've mentioned before, there are still at least two local minimas [except the desired one at (x=0,y=0,z=0,w=1)]: (x=1,y=0,z=0,w=0) and (x=0, y=0.484768546026564, z=0.874642473690417, w=0).

You can reach the second one, for example, starting from point (x=0,y=0,z=1,w=0) (for clarity: it is Eigen::Quaterniond(0,0,0,1) )

Is there a specific reason why you want to solve this problem using local optimizer like ceres-solver, instead of utilizing closed-form globally-optimal solution from the Umeyama algorithm (rotation estimation step)?

You can use this globally-optimal solution for a regular (non-robustified) least-squares formulation of your problem as an initialization for robustified least-squares, if it is the ultimate goal.

> or determine how many local minimum points in a specified region?

If you're interested in obtaining all local minima/maxima points -- you can create a system of polynomial equations for first-order optimality conditions (using Lagrange multipliers); and then solve it using multivariate-polynomial system solving method (I suppose that applying conventional approach with observing quotient ring structure in Zp and applying these observations to real case might succeed).

But I will state one more time, that it seems to me that your particular problem has a globally-optimal closed-form solution given by a rotation-estimation part of Umeyama algorithm.