Including Powell's derivative-free optimization methods?

[zaikunzhang]

Dear BlackBoxOpim.jl maintainers,

This is Dr. Zaikun Zhang from The Hong Kong Polytechnic University. Together with Professor N.I.M. Gould, I am responsible for maintaining the renowned derivative-free optimization solvers of the late Professor M.J.D. Powell, namely COBYLA, UOBYQA, NEWUOA, BOBYQA, and LINCOA. I am the author of PRIMA, which provides the reference implementation for these solvers. They are widely used by engineers and scientists. For instance, see Section 1 of a recent paper on Powell's solvers as well as the Google searches of COBYLA and BOBYQA.

Since your package is exactly oriented to derivative-free / black-box optimization, it might be desirable to include the PRIMA solvers. It should be fairly easy to do so, since PRIMA has a Julia interface:

https://github.com/libprima/prima.jl https://github.com/JuliaRegistries/General/tree/master/P/PRIMA

Besides, I note that you refer to LN_COBYLA, LN_BOBYQA, and LN_NEWUOA in your code. They are based on the unmaintained Fortran 77 implementation of COBYLA, BOBYQA, and NEWUOA. Even though the old Fortran 77 implementation of these solvers is truly a masterpiece, it contains many bugs (mostly due to the language itself), which can lead to segmentation faults or infinite loops. For example, see Section 4.4 of the above paper and many GitHub issues. It is strongly discouraged to use the Fortran 77 version of these solvers anymore.

For more information, you may check libprima / prima.

Thanks and regards, Zaikun ZHANG Ph.D. and Assistant Professor Dept. App. Math., Hong Kong Polytechnic University

[robertfeldt]

Thanks Dr. Zhang, for reaching out and for your work on these libs and packages. This is great stuff and I'm sure many users og BlackBoxOptim might be as or better served by using the algorithms here. I doubt many people that want to use these algorithms do it through BBO though, possibly they just use Optim.jl or other solutions. So I think a better solution is if I just delete the possiblity to call these algs from BBO. If people want to use them they can just go to your PRIMA package directly. Thoughts?

[zaikunzhang]

Thanks Dr. Zhang, for reaching out and for your work on these libs and packages. This is great stuff and I'm sure many users og BlackBoxOptim might be as or better served by using the algorithms here. I doubt many people that want to use these algorithms do it through BBO though, possibly they just use Optim.jl or other solutions. So I think a better solution is if I just delete the possiblity to call these algs from BBO. If people want to use them they can just go to your PRIMA package directly. Thoughts?

Practitioners of BBO will likely try BlackBoxOptim.jl as the first attempt. So I thought it might be a good idea to make sure that the state-of-the-art algorithms for continuous BBO are included in it. But this is only a suggestion for your consideration. Thank you.

[robertfeldt]

Hmm, the concern is to have a dependence on a non-julia library and to have more dependencies overall. This is not something I'd like to do without strong reason. Maybe for now, we can add a link and note to your PRIMA package in the README?

BTW, is there recent empirical evaluations supporting your claim that COBYLA et al are really state-of-the-art for a broad set of problem characteristics? In my experience, population-based methods can have an edge for complex, non-smooth problems but I haven't followed the recent literature on the topic. Any pointers to relevant papers are welcome, thanks.

[zaikunzhang]

Hmm, the concern is to have a dependence on a non-julia library and to have more dependencies overall. This is not something I'd like to do without strong reason.

Understood. I do not know the Julia ecosystem, but a package like PRIMA.jl available at the general registry is still considered a non-Julia library? Sure, it depends on the Fortran implementation of PRIMA, but the dependence is invisible to the end users due to Julia's wonderful way of handling libraries, right?

Maybe for now, we can add a link and note to your PRIMA package in the README?

This will be very kind of you and highly appreciated. Thank you very much.

BTW, is there recent empirical evaluations supporting your claim that COBYLA et al are really state-of-the-art for a broad set of problem characteristics? In my experience, population-based methods can have an edge for complex, non-smooth problems but I haven't followed the recent literature on the topic. Any pointers to relevant papers are welcome, thanks.

For example, you may refer to https://www.mcs.anl.gov/~wild/dfo/benchmarking/ceperf.pdf for a comparison between NEWUOA and some other methods (Nelder-Mead and appspack). It is not quite recent. However, as a researcher in this field, I am pretty confident to say that model-based methods like Powell's are the best choice for continuous problems of moderate size (up to several hundred). Of course, I have to point out that these methods are not designed for global optimization, although they often find high-quality local minimum, if not global.

You may check Section 1 of a recent paper on Powell's solvers for more information if you are interested. Section 5 of this paper also contains benchmarking against finite-difference BFGS and CG.

Thanks.

[robertfeldt]

Well, it is still a Julia package but since it depends on non-Julia code for building it this might restrict some people from using it on particular hardware etc, so there is still a (subtle) difference between pure-Julia packages and ones that rely on non-Julia code. Granted, in recent Julia versions the difference is much less pertinent given that even the non-Julia parts have been pre-compiled etc. But yeah, given Julia's "one language" focus, there is still a preference to having pure-Julia packages IMHO.

[robertfeldt]

Hmm, a paper from 2007 doesn't provide me strong confidence to claim that an algorithm is state-of-the-art but ok, I'll look deeper. My general interest is more in multi-objective optimization problems, are there plans to support this in PRIMA?

[robertfeldt]

Another question: How elaborate is the FORTAN code of your current implementation? Would it make sense to investigate implementing/porting it in/to Julia?

[zaikunzhang]

My general interest is more in multi-objective optimization problems, are there plans to support this in PRIMA?

It is definitely an interesting topic but not in the foreseeable future.

[zaikunzhang]

Another question: How elaborate is the FORTAN code of your current implementation? Would it make sense to investigate implementing/porting it in/to Julia?

This is one of the goals. The purpose of the Fortran code is to provide a reference implementation so that the solvers can be easily ported to other languages, e.g., Julia, Python, R, and MATLAB. Python and MATLAB have started, but Julia and R not yet.

BTW, the language is Fortran rather than FORTRAN since the 90s. PRIMA does not contain any FORTRAN code; in contrast, Powell's code is FORTRAN. Nobody should code FORTRAN in any new project. The very first (and most challenging) objective of PRIMA is to eliminate all the FORTRAN code, which took more than three years but was finally achieved.

[robertfeldt]

Link added up top in README now.

[zaikunzhang]

Link added up top in README now.

Thank you so much! Highly appreciated. We will also link to BlackBoxOptim.jl in the README of PRIMA.jl: https://github.com/libprima/PRIMA.jl/issues/16 . (I will wait for others to make changes before doing so. The project is young, so a lot of revisions are being made). Many thanks.