Comparison to other least-squares solvers

[ivan-pi]

While minpack is an important package among the Fortran legacy codes it's age is apparent.

The Ceres Solver is a non-linear least squares package written in C++ and developed at Google. They also performed a comparison of some solvers in their release note: https://groups.google.com/g/ceres-solver/c/UcicgMPgbXw

The comparison is performed using a set of 54 test problems compiled by NIST: https://www.itl.nist.gov/div898/strd/nls/nls_info.shtml

Both Ceres and HBN (not sure if this is equal to immoptibox?) have a higher total score than minpack.

How should we aim to promote minpack when better solvers are available (at least for some problems)?

Does it make sense to "restart" minpack development and bring the new algorithms into minpack? (Ceres is BSD-licensed.)

[jacobwilliams]

For me, step 1 is to modernize the code (coding style, comments, autodeployment of docs, CI, unit tests, FPM integration), then step 2 is to see about improving the algorithms that are already there (e.g. explore the ideas in #1 and #2). Then after that I wanted to see it makes sense to add new algorithms. But don't let me stop you if you want to go ahead and start doing that! :)

[arjenmarkus]

I remember reading a post about adding new algorithms but could not find it anymore, hence I use this issue to share my thoughts:

• I think it would be worthwhile to include the various methods developed by Mike Powell, such as BOBYQA and NEWUOA
• It might be useful to include probabilistic algorithms, such as differential evolution, particle swarm optimisation and shuffled complexes evolution, and some form of genetic algorithm. Not that I am very fond of them, my experience with these algorithms is ambiguous at the very least, but they turn up from time to time and it might be an opportunity to have a "canonical" implementation of them for reference.
• A completely different algoirthm is LIPO - global optimisation of Lipschitz functions. See https://arxiv.org/pdf/1703.02628.pdf
• Then there is the classical Nelder-Mead algorithm They all have their pros and possibly many cons, but it would give users a choice.

[certik]

The main advantage of minpack is that it is in Fortran. Pure Fortran. Yes, there are now better libraries in other languages for almost everything. And we can and should provide Fortran wrappers to such libraries and make them available via fpm. But having a Fortran solution is good, especially if we can improve upon it and bring it closer to the state of the art, and in the long run ideally matching the state of the art.

[arjenmarkus]

The algorithms by Powell were developed in FORTRAN77. I suggest first of all providing a modern interface and then modernising the source code itself. As for the other algorithms: implement them in Fortran too ;).

[jacobwilliams]

Unfortunately, the license on the Powell solvers is somewhat clouded now. See this thread. I think it would be better to stick with MIT/BSD for this library and not risk GPL/LGPL code getting in there. Those solvers can always be a separate library.

[arjenmarkus]

Oh, that is a shame! Well, a separate library then.

Op do 3 feb. 2022 om 16:55 schreef Jacob Williams @.***

:

Unfortunately, the license on the Powell solvers is somewhat clouded now. See this thread https://github.com/jacobwilliams/PowellOpt/issues/3. I think it would be better to stick with MIT/BSD for this library and not risk GPL/LGPL code getting in there. Those solvers can always be a separate library.

— Reply to this email directly, view it on GitHub https://github.com/fortran-lang/minpack/issues/3#issuecomment-1029133630, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAN6YRYQUCTRLJVNP42P6CLUZKQOPANCNFSM5EL5FGXQ . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

You are receiving this because you commented.Message ID: @.***>

[ivan-pi]

@arjenmarkus, personally, I'd prefer to keep the scope of MINPACK limited (at least initially) to non-linear least squares and systems of non-linear equation. While least squares is a form of optimization problem, it uses special algorithms like Levenberg-Marquadt and Trust-Region methods. Keeping the focus narrow also makes the library easier to maintain.

Furthermore, Powell's remaining optimization codes already have their development repository at PDFO. Whether we like the license conditions or not, I don't think duplicate modernization efforts help anyone.

What does fall in the scope of an upgraded MINPACK are the algorithms and methods in:

Madsen, K., Nielsen, H. B., & Tingleff, O. (2004). Methods for non-linear least squares problems. https://orbit.dtu.dk/en/publications/methods-for-non-linear-least-squares-problems-2nd-ed

which is the source followed by the authors of Ceres.

[arjenmarkus]

I was not aware of PDFO - and I probably should have been :). Well, the most important thing is that these algorithms are available.

The other ones I mentioned: I have implemntations of them, but not in Fortran. That is something I can work on and put them in a separate library as they do constitute a different class of algorithms altogether.

Op do 3 feb. 2022 om 19:25 schreef Ivan Pribec @.***>:

@arjenmarkus https://github.com/arjenmarkus, personally, I'd prefer to keep the scope of MINPACK limited (at least initially) to non-linear least squares and systems of non-linear equation. While least squares is a form of optimization problem, it uses special algorithms like Levenberg-Marquadt and Trust-Region methods. Keeping the focus narrow also makes the library easier to maintain.

Furthermore, Powell's remaining optimization codes already have their development repository at PDFO https://github.com/pdfo/pdfo. Whether we like the license conditions or not, I don't think duplicate modernization efforts help anyone.

What does fall in the scope of an upgraded MINPACK are the algorithms and methods in:

Madsen, K., Nielsen, H. B., & Tingleff, O. (2004). Methods for non-linear least squares problems. https://orbit.dtu.dk/en/publications/methods-for-non-linear-least-squares-problems-2nd-ed

which is the source followed by the authors of Ceres.

— Reply to this email directly, view it on GitHub https://github.com/fortran-lang/minpack/issues/3#issuecomment-1029275931, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAN6YR2XHG4VEHL6D5I7S6LUZLCDDANCNFSM5EL5FGXQ . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

You are receiving this because you were mentioned.Message ID: @.***>

[ivan-pi]

After a bit of digging, I've found a few more interesting (nonlinear) least squares solvers that could be added to the comparison:

• RALFit is a recent Fortran code, algorithm is described in the Preprint RAL-P-2017-010
• levmar, this is a derivative of MINPACK in C with a few extras such as box constraints
• Knitro is a proprietary solver that also includes solvers for nonlinear least squares
• GSL also includes implementations of the MINPACK algorithms in C
• Algorithm 573: NL2SOL is an older Fortran routine published in TOMS. It appears to be in use in several third-party projects such as NL2sol.jl, COPASI, and DAKOTA
• GN.FOR - GN (Gauss Newton) algorithm for nonlinear least squares minimization with finite-difference derivatives. This code is hidden in an obscure netlib folder. The readme is located in GN_ReadMe.pdf. The authors are Kenneth Klare and Guthrie Miller.
• Algorithm 768: TENSOLVE by Ali Bouaricha (Argonne National Lab) and Robert B. Schnabel (Univ. of Colorado at Boulder). This is a solver for nonlinear systems of equations. Sources are available via ACM or netlib (/toms/768).
• lmfit, a rewrite of the Levenberg-Marquadt from MINPACK in C with a focus on least-squares fitting
• NewtonLib, contains codes for nonlinear systems of equations, particularly NLEQ and NLEQ2

Edits: (10/02/2022) I added two more solvers to the list, (26/02/2022) added lmfit and the nonlinear system solver NewtonLib.

[ivan-pi]

One more NLS solver I could find is libdogleg by @dkogan. An older version can be installed directly through the Debian/Ubuntu package manager (see https://tracker.debian.org/pkg/libdogleg) (not tested yet). The advantage of libdogleg is it supports both sparse and dense problems.

A Fortran wrapper is available at my repo libdogleg-f. Currently, only the dense optimizer interface is supported, but I'm planning to prepare the sparse version too. Compared to MINPACK, the dense version uses the opposite storage pattern for the Jacobian.

[dkogan]

Hi. Two notes about libdogleg:

• The packages in Debian and Ubuntu are up-to-date (I'm both upstream and the package maintainer)

• libdogleg isn't abandoned, and I do use it in my projects. But this is largely out of inertia. I built libdogleg before libceres was available. Today there is little reason to use it in favor of libceres (based on reading the libceres docs; I haven't actually used it)

[ivan-pi]

Thanks for the reply. On the few examples I tested, libdogleg produced results matching other tools. When I try to upgrade with apt I don't get the latest version (>=0.15):

$ sudo apt-get upgrade libdogleg2
[sudo] password for ivan: 
Reading package lists... Done
Building dependency tree       
Reading state information... Done
libdogleg2 is already the newest version (0.14-1).

I have plans to build a Fortran binding to Ceres too, but the effort involved is larger. One needs to build a C bridge in both directions. There is a rudimentary C API for Ceres in https://github.com/ceres-solver/ceres-solver/blob/master/include/ceres/c_api.h, but it's not as complete as the C++ version.

[dkogan]

Hi. If you're getting 0.14-1, you must be using an old distro. 0.14-1 is latest in Debian/buster and Ubuntu/focal (not TOO old, but not the latest). But I just looked at the changelog, and you're not missing anything super important is you use 0.14-1.

In my opinion, the extra work to hook into libceres would be worth it. libdogleg is a one man show, while libceres has many users and many developers. Consequently it has more features, more/better algorithms and so on.

If you do decide to use my library, feel free to ask me stuff.