What is a proper way of solving a multibody nonlinear problem?
OK, I finally fixed this issue, the right thing to do in such non-linear situation is to use simulated annealing. I am implementing a gradient guided simulated annealing, which works pretty efficiently.

Thanks for everyone who gave me suggestions and guidance to the right path!

Have fun (mixed with a lot of frustrations) with modeling!