Handling singular Jacobians in `MultiVarNewtonFD`

[angadn]

@AzeezDa, thanks for a great library! Would be interested in contributing to the project via GitHub Sponsors if you're open to it 🙂

I was wondering about handling singular Jacobians that led to the BadJacobian errors in MultiVarNewtonFD, and whether you had any intuitions around handling these within the solver with perturbations, pseudo-inverses, etc.? Alternatively, if you've come across a gradient-free technique to experiment with, that'd be helpful too

[AzeezDa]

Hello @angadn, Thank you for your kind words and the contribution offer. I will set up the GitHub Sponsorship account, it should be done in a few days.

Regarding singular Jacobian matrices, other algorithms can be used to acquire better results. These include Trust Region Methods such as Levenberg-Marquardt's method, and randomised algorithms such as Simulated Annealing and Particle Swarm Optimisation. The latter two are derivative/gradient-free. I don't have much practical experience with them, but I can try implementing them and experimenting with them. Do you have equation systems that you found problematic (led to BadJacobian)? I would appreciate it if you could share them to make the process smoother and more targeted towards your issue.

Thanks again!🙂

[angadn]

The latter two are derivative/gradient-free.

Yes, I found this to be a great resource for inspiration, and that would be my first instinct too.

I've found the multi-function property of Newton-Raphson very helpful to model constraints for the solver - I wonder if the gradient-free techniques allow for passing multiple functions outputs, and if not, how we'd allow the consumer to inform the solver of constraints during its iteration step

Do you have equation systems that you found problematic (led to BadJacobian)? I would appreciate it if you could share them to make the process smoother and more targeted towards your issue.

Unfortunately, my use-case is general-purpose - I'm using the library as a solver for a spreadsheet, which can vary significantly from one user to another. Replicating the solvability problem will require running a proprietary evaluation tool for debugging. If you would be willing to consult with us, we could set something up for you - please let me know what you think!

[AzeezDa]

Hi @angadn, The derivative/gradient-free optimisers in the link you provided seem to be aimed at optimising objective functions that output a one-dimensional value. Thus, from what you describe, I suggest using the Gauss-Newton or Levenberg-Marquardt solvers/optimisers.

The Gauss-Newton optimiser is already available in version 0.1.3 of eqsolver but can lead to BadJacobian for certain ill-posed problems. If the Jacobian of the system you are solving is unavailable you can use the finite-difference version of Gauss-Newton. I refer to this test for an example of how to use it.

I have also implemented the Levenberg-Marquardt optimiser which can be found in the singular-jacobian-system-solvers branch of eqsolver. It is usually better than Gauss-Newton in terms having to encounter singular matrices. It is interfaced identically to the Gauss-Newton optimiser. I refer to this test for how it is used.

I will merge that branch in a few days once I properly test the changes and polish their documentation further.

Replicating the solvability problem will require running a proprietary evaluation tool for debugging.

I understand. As a first step, I suggest trying the optimisers I referred to above. Please let me know if you encounter any problems with them so we can discuss this further.

[angadn]

Thanks @AzeezDa, I'll give these a go and record my findings here!