ENH: The Fortran 77 implementation of COBYLA is buggy and challenging to maintain. Switch to the PRIMA implementation?

zaikunzhang commented 1 year ago

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

Dear SciPy 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 derivative-free optimization solvers of the late Professor M.J.D. Powell.

Thank you for making COBYLA available in SciPy. I note that the current version is based on the original Fortran 77 implementation, which is not maintained anymore.

Although the Fortran 77 code is truly a masterpiece, it contains many bugs, most of which are due to the language itself. For example, see Section 4.4 of our recent paper and the GitHub issues / requests listed below (not all of them concern SciPy).

The Fortran 77 solvers may get stuck in infinite loops.
The Fortran 77 solvers may crash with segmentation faults due to uninitialized variables that are used as indices.
Fortran 77 COBYLA may not return the best point that is evaluated; sometimes, the returned point can have a large constraint violation even though the starting point is feasible.

Describe the solution you'd like.

To avoid the problems originating from the Fortran 77 code, I suggest you use the PRIMA implementation of Powell's solvers. PRIMA provides the reference implementation for Powell's renowned derivative-free optimization methods, namely COBYLA, UOBYQA, NEWUOA, BOBYQA, and LINCOA. The "P" in the name stands for Powell, and "RIMA" is an acronym for "Reference Implementation with Modernization and Amelioration".

PRIMA provides the modern implementation of the solvers in Fortran 2008. It fixes bugs in the original Fortran 77 code. In addition, it introduces improvements that boost the performance in terms of the number of function evaluations, which is the standard measure of computational costs in derivative-free optimization.

See the GitHub repo of PRIMA for more information. I will be glad to provide assistance if help is needed.

Thanks.

Describe alternatives you've considered.

No response

Additional context (e.g. screenshots, GIFs)

matthew-brett commented 1 year ago

Sadly - I believe we would need someone to change the license, or release it under another license - it's currently under LGPL 3.

This is very topical for us - do you have any comment on this mailing list thread on Powell optimization?

zaikunzhang commented 1 year ago

Hi Matthew @matthew-brett ,

Which license is preferred? I will consider releasing it under another license if that is really needed.

I read the discussions on the mailing list thread on Powell optimization.

As a co-author of PDFO @ragonneau (the predecessor of PRIMA), I am very glad to see that our version of Powell's solvers succeeded in solving this problem, both in the classical mode (highly discouraged) and in the default mode.

BTW, it is PDFO rather than PGFO.

According to my experiences with Powell's code in the past 15 years, especially the past three working on PRIMA, I do not think it will be trivial to find out what is wrong with the scipy.optimize.fmin_powell or SciPy version of COBYLA when solving this particular problem. It is simply too hard to debug Powell's Fortran 77 code --- sorry, but I would say it will be a waste of life.

That is exactly why I spent three years of my life working on PRIMA. I do not want to see anyone else wasting her/his time on decoding a maze of 244 GOTOs in 7939 lines of Fortran 77 code.

Professor Powell was a great mathematician and a pioneer (I was very close to him). His code was great, but it should not be used anymore unless we want to be bitten by bugs from time to time (to be clear, the bugs were not from him but from the language he used).

Thanks.

matthew-brett commented 1 year ago

I'm afraid we absolutely do need a non-viral license - such as MIT or BSD. (Does anyone have a good link for our licensing requirements?).

Thanks for your comment on the thread - note that we aren't using Powell's code in Scipy, for the "Powell" optimizer, but an adaptation apparently due to to Acton, and that appears in Numerical Recipes.

zaikunzhang commented 1 year ago

note that we aren't using Powell's code in Scipy,

I note that the COBYLA optimizer of scipy.optimize is based on Powell's Fortran 77 code:

https://github.com/scipy/scipy/blob/main/scipy/optimize/cobyla/cobyla2.f

It is the main motivation for me to raise the current issue. It is so widely used --- without exaggerating, it is one of the most widely used optimization solvers in today's science and engineering, but it is so buggy.

for the "Powell" optimizer, but an adaptation apparently due to to Acton, and that appears in Numerical Recipes.

Sure, I know this algorithm. It is called Powell's conjugate direction method. Published in 1964, it was Professor Powell's second published work on optimization, and also the second most cited work (the first and meanwhile most cited is his paper on the DFP algorithm, co-authored with late Professor Roger Fletcher FRS). See historical remarks in Section 3 and footnote 6 of our paper on PDFO.

BTW, I note that the comment in scipy/scipy/optimize/__init__.py is incorrect: it says fmin_powell - Powell's (modified) level set method, but there is no such thing as "Powell's (modified) level set method". As mentioned, it is indeed "Powell's (modified) conjugate direction method". I will raise an issue / pull request to correct this.

The word "level set" probably came from a miscopying / misreading / misunderstanding of the word "Direction Set (Powell’s) Methods" in Numerical Recipies. Here, "Direction Set" refers to the set of conjugate directions generated by the algorithm. However, "Powell's conjugate direction method" is a much more used name --- I have never heard anybody from the optimization community calling it a "Direction Set" method.

matthew-brett commented 1 year ago

Thank you - it would be very helpful indeed to have your expertise in setting that straight.

I don't personally maintain the optimizers module, but it would be very good to have someone who has worked a lot on these methods maintaining them, or replacing them if necessary, in Scipy.

zaikunzhang commented 1 year ago

Thank you - it would be very helpful indeed to have your expertise in setting that straight.

I don't personally maintain the optimizers module, but it would be very good to have someone who has worked a lot on these methods maintaining them, or replacing them if necessary, in Scipy.

Sure, it is a pleasure to contribute. I do not really know Python, but I will be glad to help from the optimization and (modern) Fortran side.

tupui commented 1 year ago

@matthew-brett here are our license notes: https://scipy.github.io/devdocs/dev/core-dev/index.html#licensing and this https://scipy.github.io/devdocs/dev/hacking.html#license-considerations

Note that relicensing can be challenging. If you are a single author it can be straightforward, otherwise you need explicit permission from all contributors. And that would only work if the code you wrote in the first place could be license under the new terms. e.g. if you took (yes, even just reading it) some code from another GPL code or a snippet from StackOverflow, then you cannot relicense to MIT/BSD like that.

tupui commented 1 year ago

Sure, it is a pleasure to contribute. I do not really know Python, but I will be glad to help from the optimization and (modern) Fortran side.

@zaikunzhang thank you! That would be great to have you on-board.

We are discussing more and more about ways to move away from our old Fortran code. LFortran folks are trying to get SciPy compiling there and we are even thinking about some tools to translate the code into something else like C++ or even just Python for some things.

That being said, I don't think people would mind if you would propose to replace our F77 with a version of your code in modern Fortran. On the contrary 😃 (especially if you manage to do the change with preserving the user facing API.)

ilayn commented 1 year ago

There are two contributors on PRIMA so the relicensing should not be a problem if the authors are in agreement.

tupui commented 1 year ago

I think it needs slightly more as in the description there are statements about other codes like PDFO which is also LGPL. But yes also a few contributors.

Maybe another option, would that work if we just use the binary as a dependency?

matthew-brett commented 1 year ago

Depending on a binary would be a problem would it not? Won't it mean we'd either have to make everything optional, or provide binaries for every platform?

tupui commented 1 year ago

I have no clue here. If this is something we really want to consider, I suggest this discussion be moved to the mailing list.

matthew-brett commented 1 year ago

Well - if @zaikunzhang and collaborators can and will consider moving to a compatible license - then we don't have the binary question. So - can I ask - is that possible? That you can release under a compatible license? If so, my guess is that the mailing list, like us, would be delighted to include the code.

tupui commented 1 year ago

Note that they can retain their license if they want. This is what we do with UNU.RAN for instance. UNU.RAN is still GPL, but they explicitly allowed us to use some part of it under our license terms. The annoyance is that when they make a change in their code, they need to explicitly allow us to use the change.

ilayn commented 1 year ago

We did this relicensing before in Scipy and also Tim Davis and SuitSparse already did this with Python and Julia users too. So let's not confuse ourselves. That's the easiest of the complications.

tupui commented 1 year ago

Oh I am not saying it's impossible, just pointing out things 😃 I am more than happy if that happens here and we can remove old code.

zaikunzhang commented 1 year ago

The other contributior, Tom Ragonneau @ragonneau was formerly my Ph.D. student and now a colleague. He is a contributor because PRIMA contains some code from the above-mentioned PDFO package, which was developed during his Ph.D. under LGPL3+ and laid the groundwork that made PRIMA possible.

That said, it is not very difficult to get permission from Tom to change the license of PRIMA to, e.g., the BSD 4-clause license.

Indeed, Tom himself seems to prefer BSD to LGPL. For instance, another derivative-free optimization Python package COBYQA by us is licensed under BSD, which was chosen by Tom. (BTW, COBYQA is designed to replace COBYLA, which is included in scipy.optimize as mentioned, and it outperforms COBYLA by a significant margin according to our extensive experiments documented in Tom's thesis. But that's another story).

For PDFO and PRIMA, we currently use LGPL because Professor Powell had chosen LGPL for the original Fortran 77 code of his solvers before he passed. I am not an expert on law/licenses, but does this prohibate us from licensing PRIMA under BSD? PRIMA is derived from Powell's code.

Note that they can retain their license if they want. This is what we do with UNU.RAN for instance. UNU.RAN is still GPL, but they explicitly allowed us to use some part of it under our license terms. The annoyance is that when they make a change in their code, they need to explicitly allow us to use the change.

This is also a possibility.

Thanks for the discussions.

ilayn commented 1 year ago

Ouch. If it's a derivative indeed that is a problem but I think @rkern is more knowledgeable in this regard

zaikunzhang commented 1 year ago

Ouch. If it's a derivative indeed that is a problem but I think @rkern is more knowledgeable in this regard

In fact I do not know the exact definition of "derived". I mean, PRIMA has been written according to Powell's Fortran 77 code, even thoug it does not contain his code anymore.

matthew-brett commented 1 year ago

I would guess that you can ask Powell's heirs if they would allow the code to be relicensed. I am sure we could help you write up something that was clear enough for them to decide on:

https://copyrightalliance.org/what-happens-to-your-copyrights-after-you-die/

zaikunzhang commented 1 year ago

@zaikunzhang thank you! That would be great to have you on-board.

Thank you @tupui ! It will be my pleasure to contribute. It is also my mission and commitment to maintain Professor Powell's solvers, which are too precious to be lost. I had promised to Professor Powell before he passed.

We are discussing more and more about ways to move away from our old Fortran code. LFortran folks are trying to get SciPy compiling there and we are even thinking about some tools to translate the code into something else like C++ or even just Python for some things.

That being said, I don't think people would mind if you would propose to replace our F77 with a version of your code in modern Fortran. On the contrary smiley (especially if you manage to do the change with preserving the user facing API.)

I know LFortran and the main contributors, even though not personally but only through Fortran Discourse. I highly appreciate what they are doing and pushing forward. We do not have collaboration but we are going in the same direction concerning the maintenance and modernization of existing Fortran code, although I focus only on Professor Powell's solvers.

zaikunzhang commented 1 year ago

I would guess that you can ask Powell's heirs if they would allow the code to be relicensed.

This is possible, as I know them personally. However, I hope not to disturb them for this issue. Let's say this is the last resort.

The LGPL license was suggested by Professor Nick Gould to Professor Powell. Nick is also a maintainer of Professor Powell's Fortran 77 code, although he is not involved in PDFO or PRIMA. We would have to consult him as well if relicensing Professor Powll's code becomes a real need.

Indeed, exactly the same licensing problem exists in the current version of SciPy due to the COBYLA code contained in scipy.optimize. This is obviously a (slightly) modified version of Professor Powell's Fortran 77 code. If LGPL is enforced, there may be a problem according to the discussion up to now (I did not know it was a problem).

Again, I am not an expert on law/licenses, and I am not an heir of Professor Powell. But since Professor Powell asked me to maintain these solvers and informed me about the license of his choice, I feel obliged to point this out.

matthew-brett commented 1 year ago

I'm sorry for the inconvenience, but my guess is that changing the license will be necessary, to include the code in Scipy. If I was arguing to Nick Gould, or Professor Powell's heirs, I think I would make the case that Scipy has become the default base library for numerical computing worldwide, and therefore, that his code can have a great deal more impact in terms of good for the world, if they can be included in Scipy, than if they cannot.

For the COBYLA code - ouch - and thanks for pointing that out. We will have to resolve that.

rkern commented 1 year ago

Yes, looking at how you made the modern Fortran from the Fortran 77, I think it would be considered a derivative work, and the LGPL would still apply. At least for our purposes.

However, we did ask for and receive permission from Professor Powell to include our version of COBYLA under our BSD license. So at least for COBYLA, you could probably double-check that our version is close enough to the version you started from, then it would be clean as far as we're concerned. We should update our license information to include this fact.

For the others, I actually suspect that the copyright ownership of the originals may actually reside with his employer, the University of Cambridge. The copyright statement includes both his name and the University for some reason. It is commonly the case that universities claim ownership of the IP of their employees as part of their employment agreements. I would probably contact their Technology Transfer office first and see if they make any claim over the ownership. If not, then yes, it would be his heirs.

zaikunzhang commented 1 year ago

Hi @rkern , thank you for the professional comments.

Yes, looking at how you made the modern Fortran from the Fortran 77, I think it would be considered a derivative work, and the LGPL would still apply. At least for our purposes.

OK. Then it is clear.

However, we did ask for and receive permission from Professor Powell to include our version of COBYLA under our BSD license. So at least for COBYLA, you could probably double-check that our version is close enough to the version you started from, then it would be clean as far as we're concerned. We should update our license information to include this fact.

This is very fortunate! I note that the conversation took place 19 years ago, in 2004. At that time Professor Powell was developing his powerful and renowned NEWUOA solver for unconstrained optimization without derivatives. It is a pity that the inclusion of NEWUOA was not possible to be discussed 19 years ago.

Yes, I confirm that the modernized implementation of COBYLA is based on a Fortran-77 version that is essentially the same as the one included in scipy.optimize.

For the others, I actually suspect that the copyright ownership of the originals may actually reside with his employer, the University of Cambridge. The copyright statement includes both his name and the University for some reason. It is commonly the case that universities claim ownership of the IP of their employees as part of their employment agreements. I would probably contact their Technology Transfer office first and see if they make any claim over the ownership. If not, then yes, it would be his heirs.

If the university gets involved, I do not think it would be a trivial discussion. So it turns out much more complicated than we expected ...

matthew-brett commented 1 year ago

For what it's worth, the license has:

Copyright (C) 1992 M. J. D. Powell (University of Cambridge)
...
Michael J. D. Powell <mjdp@cam.ac.uk>
University of Cambridge
Cambridge, UK.

So, I think Powell is just saying that's where he works, not that he's asserting in the license that the University of Cambridge has copyright. In the linked email thread about COBYLA (thanks!) Jean-Sebastien Roy says he would ask Powell for permission to relicense on the 10 April 2004, and reports back the Powell said yes on the 12 April - I doubt whether Powell had had time to consult and heard back from whatever the technology transfer office was back then, so I take that as more evidence that Powell believed he had sole copyright. Of course Cambridge may disagree.

matthew-brett commented 1 year ago

My guess is that, if you could persuade Powell's heirs, and I guess, Nick Gould, that Powell would have agreed, and that he would have been right to agree, you could then go to Cambridge with that information. They'd have to be pretty aggressive to stop you at that point - especially as it is already under a free license, and Powell has already quickly said yes to a similar request. I can see if I can find anyone who would know the best way to contact the Cambridge people for this, if you would consider going down that route.

rkern commented 1 year ago

For the purposes of this issue about COBYLA, I'm happy with our provenance. If @zaikunzhang and @ragonneau agree with relicensing their modernization contributions to COBYLA to the BSD license that Professor Powell agreed to, then I, at least, am happy to accept them.

For the other algorithms, we can broach the topic of relicensing when someone actually wants to step forward to do the work of making the Python wrappers for them. Right now, no one has.

zaikunzhang commented 1 year ago

My guess is that, if you could persuade Powell's heirs, and I guess, Nick Gould, that Powell would have agreed, and that he would have been right to agree, you could then go to Cambridge with that information. They'd have to be pretty aggressive to stop you at that point - especially as it is already under a free license, and Powell has already quickly said yes to a similar request. I can see if I can find anyone who would know the best way to contact the Cambridge people for this, if you would consider going down that route.

Thank you for the suggestion. I will first discuss with Nick about the licensing issue. He is a world-leading British numerical analyst, and hence I suppose he has good connections with British universities including Cambridge. We may also need your help eventually.

zaikunzhang commented 1 year ago

For the purposes of this issue about COBYLA, I'm happy with our provenance. If @zaikunzhang and @ragonneau agree with relicensing their modernization contributions to COBYLA to the BSD license that Professor Powell agreed to, then I, at least, am happy to accept them.

For the other algorithms, we can broach the topic of relicensing when someone actually wants to step forward to do the work of making the Python wrappers for them. Right now, no one has.

This is great! I will ask Tom @ragonneau and I presume he will agree to license the COBYLA code under BSD.

In addition, Tom knows Python quite well. He coded the Python part of PDFO and the whole of COBYQA. So I guess he may help with the Python wrapper.

ilayn commented 1 year ago

Well @zaikunzhang officially welcome to the funky world of open source 😅

zaikunzhang commented 1 year ago

@ilayn and everyone, thank you!

I have prepared a copy of PRIMA COBYLA licensed under the ~~4-clause BSD~~[updated to 3-clasuse BSD]. I intentionally keep the file tree of PRIMA, so that it is straightforward to include the other four solvers when appropriate.

I confirm the following.

As of commit 0801c02, the repository at https://github.com/libprima/prima_for_scipy contains only code by myself (Zaikun ZHANG) alone. Part of the code is written based on Powell's Fortran-77 version of COBYLA, which is essentially the same as the one included in SciPy at

https://github.com/scipy/scipy/blob/main/scipy/optimize/cobyla/cobyla2.f

The remaining part is my original work.

In particular, it does not contain code from PDFO.

Since I do not know Python, I would need to rely on the capable hands here to write the Python wrapper (I realize that Tom is currently quite busy working on other projects / papers). Meanwhile, I will be glad to provide assistance from the Fortran / optimization side.

The following files contain detail about how to use the PRIMA version of COBYLA.

https://github.com/libprima/prima_for_scipy/blob/main/fortran/cobyla/README.txt https://github.com/libprima/prima_for_scipy/blob/main/fortran/cobyla/cobyla.f90 https://github.com/libprima/prima_for_scipy/blob/main/fortran/examples/cobyla/cobyla_example.f90 https://github.com/libprima/prima_for_scipy/blob/main/fortran/examples/cobyla/Makefile

Thanks.

rkern commented 1 year ago

Thank you! Unfortunately the 4-clause BSD variant is not one that we can use. The advertising clause is incompatible with other open source licenses that we want to allow people to combine scipy with. We use a 3-clause BSD license for scipy itself, and that would be the easiest variant to use. We will make sure to have an explicit entry in the bundled licenses document that will cite and link to the PRIMA project.

zaikunzhang commented 1 year ago

Thank you! Unfortunately the 4-clause BSD variant is not one that we can use. The advertising clause is incompatible with other open source licenses that we want to allow people to combine scipy with. We use a 3-clause BSD license for scipy itself, and that would be the easiest variant to use. We will make sure to have an explicit entry in the bundled licenses document that will cite and link to the PRIMA project.

OK. I see. I have changed it to the 3-clause BSD. Thank you @rkern for the quick comment.

rkern commented 1 year ago

Thank you very much! I appreciate your consideration. I know that I would rather be finding new ways to provoke bugs in Fortran compilers than dealing with licensing minutiae, and that's saying something.

zaikunzhang commented 1 year ago

I have got a response from Nick. His opinion is summarized as follows. If there is a need, I can show the email in private.

It was Professor Powell's intention to make his software distributed freely. He chose a license to make the distribution easy, rather than the opposite.
Nick suggested LGPL (v2.1 at that time) to Professor Powell because it was the license that Nick was familiar with and used for his own code. Now Nick has shifted to the 3-clause BSD. The license was beyond Professor Powell's care due to his health condition, so he adopted directly what was suggested.
According to email exchanges between Nick and Professor Powell, LGPL was attached to Powell's code on April 16, 2015. On the other hand, Professor Powell sent me all the code on or before April 6, 2015, asking me to maintain and distribute it without mentioning a license. The license was an afterthought.
For the above reasons, Nick suggests that I can legitimately change the license from LGPL to 3-clause BSD.
Professor Powell mentioned "Cambridge" in the license as an address instead of an attribution of ownership.

If there is any concern from the SciPy maintainers, I may contact Professor Powell's heirs (but it seems unnecessary).

The standard emails that Professor Powell used to distribute his code can be found below. He sent me the code using the same emails.

Thanks.

matthew-brett commented 1 year ago

Just to clarify - each of the files you mention was sent to you by Professor Powell, for the purpose of redistribution, before the LGPL was attached to it?

Each of those files has the following sentence:

There are no restrictions on or charges for its use.

and no other restrictions. I think these are therefore public domain dedications, along with the assertion of sole copyright, and my opinion would be that these are therefore safe to release under the BSD 3-clause license as they are, given the information you've given.

zaikunzhang commented 1 year ago

Just to clarify - each of the files you mention was sent to you by Professor Powell, for the purpose of redistribution, before the LGPL was attached to it?

Yes, I confirm this is true.

I still have all the emails saved in my mailbox. The last email, which distributed UOBYQA to me, was received on April 6, 2015. He also asked me to maintain and distribute all his solvers on his behalf on April 6, 2015. Both before April 16, when he adopted LGPL for his code.

zaikunzhang commented 1 year ago

I have included the PRIMA implementation of all Powell's derivative-free optimization (DFO) solvers at https://github.com/libprima/prima_for_scipy. The solvers are COBYLA, UOBYQA, NEWUOA, BOBYQA, and LINCOA. They are state-of-art solvers for handling general nonlinear optimization problems without the need for derivatives. These renowned solvers have been widely used by scientists and engineers. For instance, see the recent paper on Powell's solvers as well as the google searches of COBYLA and BOBYQA.

As discussed, it would be beneficial to include the modernized implementation of Powell's renowned solvers into SciPy. I guess the benefits will be for both SciPy (in terms of leveraging its optimization capability, which is of course already quite high) and the users of Python (in terms of easy access to state-of-art DFO solvers).

However, I do not know Python. Is there anyone here interested in wrapping these solvers in SciPy? I will be glad to provide assistance from the Fortran and optimization side. Thank you very much.

Disclaimer: As of commit 3bae603, the above-mentioned repository contains only my own work under project PRIMA and the code that Professor Powell sent to me on or before April 6, 2015, the former being a derivative of the latter. There was no license attached to Professor Powell's code when he sent it to me, and the emails he sent to me mentioned that there were no restrictions on or charges for the use of the code. He also asked me to maintain and distribute his code on his behalf on April 6, 2015. Therefore, I license Powell's original code and my code under the 3-clause BSD license.

dschmitz89 commented 1 year ago

Thanks for providing this @zaikunzhang !

Besides bugs in COBYLA, a wrapper for BOBYQA has been on the wish list for many years (see #1477).

Maybe I missed parts of the discussion but would it be easier to use the python wrappers already available in pdfo ? That repo is also BSD-3 licensed.

zaikunzhang commented 1 year ago

Hi @dschmitz89 ! Thank you for your comments.

Yes, PDFO provides Python wrappers for all the five derivative-free optimization solvers of Professor Powell. They were written by Tom @ragonneau for Chapter 3 of his Ph.D. thesis.

However, the wrappers were written for the Fortran 77 implementation of the solvers (PDFO is based on Powell's Fortran 77 code). The PRIMA implementation adopts a modernized signature, using features like assumed-shape arrays. Therefore, the PDFO wrappers cannot be used directly. However, it would be helpful to use them as a reference.

Comments on COBYLA and BOBYQA

It is not strange that people want BOBYQA to be available in SciPy. COBYLA was the first derivative-free trust-region optimization algorithm by Powell. Released in 1992, some of its techniques are a bit primitive from a modern point of view. BOBYQA (as well as NEWUOA, and LINCOA) incorporates much more advanced techniques, most noticeably the derivative-free symmetric Broyden update. Consequently, NEWUOA, BOBYQA, and LINCOA are much more powerful than COBYLA on the problems that they can solve: NEWUOA for unconstrained problems, BOBYQA for bound-constrained, and LINCOA for linearly constrained.

The advantage of COBYLA is that it can handle nonlinear constraints. However, with the presence of COBYQA, this is not such an advantage anymore. COBYQA can handle nonlinear constraints while exploiting modern techniques including SQP and the derivative-free symmetric Broyden update. It works much better than COBYLA according to our extensive tests. There are many other limitations of COBYLA, but I do not want to give an optimization lecture here. See Chapter 7 of the above-mentioned thesis by Tom if you are interested.

rkern commented 1 year ago

That repo is also BSD-3 licensed.

FYI, PDFO just changed licenses from LGPL to BSD last night, mere hours before your comment, because of this discussion. Thanks, @ragonneau!

Because of the call signature changes, it's not completely trivial to drop in the PRIMA implementations into PDFO, but PDFO does have a lot of the Python-side implementation of the fmin_*-style interface (e.g. dealing with the various kinds of bounds). Probably a good starting point.

zaikunzhang commented 1 year ago

That repo is also BSD-3 licensed.

FYI, PDFO just changed licenses from LGPL to BSD last night, mere hours before your comment, because of this discussion. Thanks, @ragonneau!

Right. I changed the license from LGPL to BSD yesterday because of this discussion, after receiving consent from Professor Nick Gould and Tom @ragonneau.

Because of the call signature changes, it's not completely trivial to drop in the PRIMA implementations into PDFO, but PDFO does have a lot of the Python-side implementation of the fmin_*-style interface (e.g. dealing with the various kinds of bounds). Probably a good starting point.

Exactly.

BTW, three years ago, when Tom and I initiated the PDFO project, I did not post here to suggest the inclusion of Professor Powell's solvers in SciPy because the solvers were still in Fortran 77. PDFO has gained decent popularity after its release, with 50,000+ downloads in total (mirror downloads excluded) and recently ~100 downloads per day. The popularity demonstrates that there is a true demand for these solvers from Python users, which is also manifested by the popularity of COBYLA under SciPy. Since the previous request for Powell's solvers was not met only because of the license, the last obstacle to their inclusion in SciPy has been removed.

stefanv commented 1 year ago

Update from the community call: there is interest in adopting this implementation, but little appetite for taking on more Fortran code (because we're already working to get rid of it in several other components). A feasible route forward could be to translate the Fortran implementation to C, using e.g. f2c, and to use that. Or perhaps there is interest in doing an official Cython / Pythran / C / C++ port?

zaikunzhang commented 1 year ago

Hi @stefanv! Thank you and the community for the update.

I personally understand the lack of appetite for more Fortran code. Making Professor Powell's solvers easily available to non-Fortran users is the very reason for me to work on PRIMA.

However, f2c is not a feasible solution here, as it is incapable of handling modern Fortran.

Official C++ and Python implementations are being planned, but they will not be delivered in the near future.

That said, I guess the most probable and practical solution is to wrap the modern Fortran implementation of PRIMA using iso_c_bindings + ctypes or similar facilities.

I hope to emphasize that modern Fortran is quite different from classic-style Fortran 77. A modern-Fortran package can be modularized, structured, readable, maintainable, and extendable, which is what I endeavor to achieve and demonstrate with PRIMA.

Being a fan of Italian food, I have absolutely no appetite for spaghetti-style Fortran 77 code either. However, it is my humble suggestion that the SciPy community might keep open-minded about the inclusion of modern Fortran code. They are different species.

Indeed, there has been some intensive discussion on the inclusion of PRIMA into SciPy in the past few days. I put them below for your reference. You may find therein useful information and viewpoints on modern Fortran.

Hacker News: https://news.ycombinator.com/item?id=35959991 (Front-page Story of 16 May) https://news.ycombinator.com/item?id=35986906 (Front-page Story of 18 May)

Fortran Discourse: https://fortran-lang.discourse.group/t/scipy-there-is-interest-in-adopting-this-prima-implementation-but-little-appetite-for-taking-on-more-fortran-code/5821 https://fortran-lang.discourse.group/t/optimization-without-using-derivatives-the-prima-package-its-fortran-implementation-and-its-inclusion-in-scipy/5798

rkern commented 1 year ago

FWIW, the root of much of our woes with the other Fortran code has been that we were effectively the maintainers of that Fortran code. Here, we have an active maintainer of the Fortran code keeping it working well on multiple compilers. That might tip the scales some. Swapping in the improved COBYLA Fortran code for the existing COBYLA Fortran code may be pure profit from a maintenance standpoint (though someone does have to rewrite the wrapper). Adding NEWUOA, BOBYQA, LINCOA, and COBYQA is another matter, but this is somewhat different than our issues with other Fortran code because of the active maintenance.

That said, I guess the most probable and practical solution is to wrap the modern Fortran implementation of PRIMA using iso_c_bindings + ctypes or similar facilities.

The issue isn't the wrapping, but the Fortran of the implementation itself.

matthew-brett commented 1 year ago

FWIW, the root of much of our woes with the other Fortran code has been that we were effectively the maintainers of that Fortran code. Here, we have an active maintainer of the Fortran code keeping it working well on multiple compilers.

Excellent point. That seems like a big win - better code and a maintainer.

steppi commented 1 year ago

I'd planned to attend the community meeting but missed it due to being wiped out from the flu doing the rounds in my household. I'm +1 for swapping out the existing COBYLA code for this modern implementation. Looking at some of the code it looks very clean and well documented. It's also actively maintained and it's maintenance appears to be well-funded

PRIMA is a long-term project, which would not have been sustainable without the continued funds from the Hong Kong Research Grants Council (ref. PolyU 253012/17P, PolyU 153054/20P, and PolyU 153066/21P) and The Hong Kong Polytechnic University (PolyU), in particular the Department of Applied Mathematics (AMA).

The original Fortran 77 implementation on the other hand is a tangled mess and @zaikunzhang seems to have gone to considerable lengths to untangle it. I agree with @rkern, that after a new wrapper is written, this should only lower our maintenance burden.

ilayn commented 1 year ago

I have been looking at various *PACK code lately, and I think I don't need to repeat my view on FORTRAN being a very fast and "nice" language. I mean no offense and also I don't mean to stop anyone using Fortran in their own work.

But Fortran code is almost like GPL license. When you commit to it there is no going back you have to stick with it. To be frank, I don't think it is that good of a language to maintain while the rest of the world is moving on to more cross-pollinating languages. The remaining bunch (which is nowhere near to be underestimated) is the matlab, julia, fortran tribe.

If there is any appetite, I would be willing to translate any code to some other language or Cython. The real maintenance burden is the compilation and the packaging not the code itself that we are carrying around.

matthew-brett commented 1 year ago

@ilayn - if the option was between well-maintained Fortran code and well-maintained C or C++ code, I'm sure we'd all go for the latter - but here the option is between poorly maintained buggy old Fortran code, and well-maintained more correct modern Fortran code. It's perfectly reasonable to plan to replace the Fortran code over the long hall, but for now, and the medium term, this seems like a much better option than what we have, and what we can reasonably hope to have in the near future.

scipy / scipy