ENH: biteopt global optimization algorithm

dschmitz89 commented 2 years ago

Is your feature request related to a problem? Please describe.

biteopt is an actively maintained and according to recent benchmarks very capable stochastic global optimization algorithm implemented in C++. biteopt solves significantly more problems of scipy's own global optimization test suite than scipy's solvers at the moment (see benchmark). A few months back, a feature request issue was already created and there seemed to be a concensus that it would be a valuable addition to scipy. As the old thread had to be closed due to code of conduct violations, I am reopening another one now.

Describe the solution you'd like.

A new function scipy.optimize.biteopt which wraps the C++ source.

In the old thread it was pointed out that biteopt should accept a seed coming from a numpy.random.RandomGenerator so that users have a uniform API for random seeds across scipy. Support for custom PRNGs via C style pointers was added to biteopt a few weeks ago as the last two arguments of the main optimizer function:

int biteopt_minimize( const int N, biteopt_func f, void* data,
    const double* lb, const double* ub, double* x, double* minf,
    const int iter, const int M = 1, const int attc = 10,
    const int stopc = 0, biteopt_rng rf = 0, void* rdata = 0)

Describe alternatives you've considered.

A scipy.optimize style API for biteopt exists in Python in the project scipybiteopt. This one is not tested in CI though and does not provide wheels, so the user needs a working C++ compiler. Also, supplying the seed is not supported.

Additional context (e.g. screenshots, GIFs)

I would love to help bring this to life in scipy but am a bit lost in the low level stuff, precisely at how to link to numpy's RNG from a C/Cython wrapper for the biteopt function. Maybe a C++ expert can chip in. @andyfaff had expressed a preference for the wrapper to be written in Cython.

CC @rgommers who had closed the old thread AFAIK and CC @czgdp1807 in case you are interested in another optimize project ;) .

tupui commented 2 years ago

Thank you @dschmitz89 for reviving this. As said on the previous issue, I am +1 on adding new global optimisers. The move to Cython is not mandatory at all for a first version which could just be a wrapper. Similar to what we did with DIRECT.

lesshaste commented 1 year ago

Is anyone currently working on this?

tupui commented 1 year ago

@lesshaste not that we are aware of. Anyone is welcome to make PRs or team up 😃

dschmitz89 commented 1 year ago

@lesshaste : thanks for your interest, you are very much welcome to work on this. :)

As this can become a quite intense (but very much worthwhile ;) ) undertaking, I thought I would list a few resources that could help you.

So far, scipy.optimize wraps two optimizers written in C: TNC and direct. They use two different wrapping approaches: TNC goes the Cython way, direct uses Python's C API. Another possibility would be pybind11 which is used in other modules in scipy (for example fft, see here). Looking into the codes of these can be helpful to avoid common pitfalls.

Currently, scipy supports two build systems: numpy.distutils and meson. distutils is going to be dropped for the next release though, so supporting meson would be sufficient here (thanks @tupui for the correction).

To see which type of tests are necessary, you could check out the tests for direct here. One typical problem with C/C++ calling Python functions is for example that Python errors must not crash the C program but instead be propagated back to the user/scipy code. That is not the case for the scipybiteopt wrapper. Any Python Exception/Error kills biteopt there.

Lastly, an example for calling Numpy's RNG in Cython/C within SciPy can be found here.

tupui commented 1 year ago

Correction for distutil, the goal is to move away from it before the next release. Since this new function would probably not make it before the release (realistically), then I suggest to just not bother with anything else than meson.

dschmitz89 commented 1 year ago

CC @melissawm

dschmitz89 commented 6 months ago

CC @czgdp1807 any chance you would have bandwidth to look at this? Once an initial wrapper is done, I could take over. Thanks in advance!

czgdp1807 commented 6 months ago

I will be more than happy to work on this algorithm. I am always interested in such projects.

CC: @rgommers

rgommers commented 6 months ago

I will be more than happy to work on this algorithm. I am always interested in such projects. CC: @rgommers

For context of others: the question here was more or less "do we have funding to work on this". Which is unfortunately "no" right now. I'm all for adding biteopt if the benchmarks show it's better than our other algorithms, but we currently don't have a grant for this nor can I quite justify requesting sponsorship from Quansight Labs for this. Maybe we can include this in some plan in the future, but no promises.

scipy / scipy