patrick-kidger
Help with adding (quasi-newton) Davidon–Fletcher–Powell update method?
Dear optimistix team,
I'm looking into implementing the Minuit optimizer with optimistix. Python bindings for the (newer) C++ implementation can be found in iminuit.
This optimizer is a standard in high-energy physics research and commonly used by physicists at CERN. Our community is currently in the process of trying to port some of our statistical inference tools (e.g. pyhf) towards JAX, and thus like to re-implemented Minuit in JAX aswell.
My (best) understanding of Minuit is that it consists of 2 parts (that - if specified by a user - are automatically switched between):
- "MIGRAD": basically the same as
optimistix.BFGS, but the update of the hessian (or its inverse) is done by the Davidon-Fletcher-Powell formula instead. - "SIMPLEX": this looks to me exactly like
optimistix.NelderMead- so, perfect!
My wish is to implement MIGRAD in optimistix and for this I had a look at the BFGS code. As far as I understand I probably want to keep the whole code and only switch out bfgs_update by a new dfp_update function.
Is this assumption correct? If yes, could you give me some hints what things need to be changed? (I have some troubles understanding the PyTree manipulations in the existing bfgs_update code and connect them to the mathematical formula for BFGS.)
In addition, the termination of the minimization is determined in Minuit by the so-called "edm"-measure, which is calculated by: $\text{edm} =\nabla^T H^{-1} \nabla$, where $H^{-1}$ denotes the inverse hessian, see p. 348 in Minuit. I suppose I'd have to add this custom measure and the termination logic inside the step function aswell?
I'd be happy for any tips and help to make this happen, and contribute this (e.g. the dfp_update formula) to optimistix.
Best, Peter
cc @nsmith- and @matthewfeickert
We're also thinking about adding L-BFGS here: https://github.com/patrick-kidger/optimistix/issues/116
I think it would be best if we make the update formula a solver attribute? This now makes three different versions of update formulas that are useful in different contexts. Same could go for termination conditions, I'm experimenting with this for constrained solves where optimality error is the typical criterion. We could then default to cauchy_termination in classic BFGS, and make Minuit an extra solver that also inherits from AbstractBFGS.
Regarding the Pytree formulations - it took a little getting used to for me as well, happy to walk you through them anytime!
Hi @johannahaffner,
that sounds great! Making the update formula and termination criteria a choice would solve it and follows the composability design for solvers by optimistix (as far as I understood it) :)
Regarding the Pytree formulations - it took a little getting used to for me as well, happy to walk you through them anytime!
Thanks, that would be super helpful! Would you be up for a short (pair-programming) video call?
Yes, we could do that early next week! If you're at CERN right now, we could also meet up somewhere in Switzerland.
Great, I'll reach out to you via email 👍 Thank you already a lot in advance!