Eigen's FullPivLu behaviour change causes line_search optimization to fail.

[sandwichmaker]

Hi, we found that for some of our optimization problems Ceres (using LINE_SEARCH) have failed to converge if we combine it with Eigen of versions after 3.2.8.

We looked into this problem and found that it is because the behavior of Eigen fullPivLu function has changed after 3.2.8 (You can check the change log of 3.2.8: http://eigen.tuxfamily.org/index.php?title=ChangeLog#Eigen_3.2.8 or more specifically:

(https://bitbucket.org/eigen/eigen/commits/84835f5f75c7a736e03a7e98a095f3ac7439defc?at=default)
) especially for matrix that is numerically rank deficient,

This caused very different behavior for FindInterpolatingPolynomial (line 373 in internal/ceres/polynomial.cc) when the matrix lhs becomes numerically rank deficient, we found that for many optimization problems they converge better with the previous behavior of Eigen fullPivLu (version 3.2.7 and before). So we temporarily fix this problem by changing line 373
return lhs.fullPivLu().solve(rhs);
to the following:
Eigen::FullPivLU lu_lhs( lhs );
return lu_lhs.setThreshold( 0.0 ).solve( rhs );

The fix above so far works well for us, however, we believe you guys have a better fix for this since probably the solution given by fullPivLU is not the solution you are looking for when the matrix becomes rank deficient.

For your reference, some people encountered similar issues while using Eigen ( https://forum.kde.org/viewtopic.php?f=74&t=129439 ), we tried the suggestions Gael provided, however, they either converge much slower or failed to converge for our testing problem.