Levenberg Marquardt type method not converging

[Hariprasad Kannan]

I have an implementation of a trust region Newton method which is inspired by Levenberg-Marquardt. I add a damping matrix to my hessian and then solve the linear system, in each iteration. For some problems, this approach is not converging - the gradient norm reaches a small (~10 for a million variables) and keeps oscillating in that ball park, even though the function is slowly decreasing. The gradient l-infinity norm is of magnitude ~1 and never goes down below that, so there are still a few large components in that gradient. The damping parameter (lambda) is quite large (~20), which could be the reason. Usually, lambda becomes small, close to the optimum, but it is not the case for many problem instances. What could be going wrong here? Generally, how does L-M behave?

[Sameer Agarwal]

It means that the algorithm is unable to find a direction in which it can make significant progress. Because it was unable to make progress, the damping parameter became larger and larger so that it could try and take smaller and smaller steps to make some progress.

Sameer

On Wed, Jul 29, 2015 at 12:33 PM Hariprasad Kannan <hka...@gmail.com> wrote:

I have an implementation of a trust region Newton method which is inspired by Levenberg-Marquardt. I add a damping matrix to my hessian and then solve the linear system, in each iteration. For some problems, this approach is not converging - the gradient norm reaches a small (~10 for a million variables) and keeps oscillating in that ball park, even though the function is slowly decreasing. The gradient l-infinity norm is of magnitude ~1 and never goes down below that, so there are still a few large components in that gradient. The damping parameter (lambda) is quite large (~20), which could be the reason. Usually, lambda becomes small, close to the optimum, but it is not the case for many problem instances. What could be going wrong here? Generally, how does L-M behave?

--
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/d757d593-23d8-4ad1-a7cb-577ff9959686%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Hariprasad Kannan]

I am wondering why this condition should happen? It is known that the problem has a global optimum, why couldn't the algorithm converge? Is it because of some poor steps taken over many iterations, leading it to a suboptimal part of the problem? Why were the poor steps taken? Will better preconditioning help? Right now I am using only diagonal preconditioner.

--
You received this message because you are subscribed to a topic in the Google Groups "Ceres Solver" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ceres-solver/biStdTnbBO4/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ceres-solver...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/CABqdRUAcE5WWHEDcsSCXUGrSFpGDMDV6C2brB8MCiyQpgRZ0aw%40mail.gmail.com.

[Sameer Agarwal]

I am not sure to be honest. Could be a bug in your implementation, could be the way your tolerances are set, could be ill conditioning of the hessian, could be indefiniteness in the hessian that is not being handled correctly. Hard to say with this little information.

Sameer

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/CAN7sVgZOugSAO-f0rDf6i8NBkGXYg%2BK0NzVNU5VeCbrSryytMg%40mail.gmail.com.

[Hariprasad Kannan]

Yes, I understand. Thanks for your inputs and time.

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/CABqdRUBw4o0ZVHpmX3QKO1QJ4QiYxvNYrqXPS7YNzW%2BA25Ec%3DA%40mail.gmail.com.

[Hariprasad Kannan]

For sure, my hessian is highly ill-conditioned (I have even seen condition numbers of 10^19). At the same time it is not indefinite. It is positive definite. Probably, given the huge condition number, it is positive semi definite for all practical purposes.