Powell's DFO methods: the Fortran 77 implementation of COBYLA / NEWUOA is unmaintained and buggy; Switch to PRIMA?

[zaikunzhang]

Dear Nevergrad 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 (DFO) solvers of the late Professor M.J.D. Powell. I am the author of PRIMA, which provides the modernized reference implementation for these solvers.

Thank you for making COBYLA and NEWUOA available in Nevergrad. 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.

• The Fortran 77 solvers may get stuck in infinite loops.

  • optimize: COBYLA hangs / infinite loop scipy/scipy#8998

  • BUG: optimize: COBYLA hangs on some CPUs scipy/scipy#15527

  • COBYLA freezes (though maxeval and maxtime are given) stevengj/nlopt#370

  • COBYLA hangs stevengj/nlopt#118

  • NEWUOA_BOUND stuck in infinite loop inside MMA stevengj/nlopt#117

  • Cobyla freezes in 0T1.16rc1 openturns/openturns#1651

  • Optimization freezes astamm/nloptr#25

  • BOBYQA gets stuck in infinite loop. cureos/csnumerics#7

  • Algorithm turns into infinite loop and never finishes xypron/jcobyla#3

  • The Fortran 77 version of UOBYQA encounters infinite cyclings very often if PRIMA_REAL_PRECISION is 32 libprima/prima#98

• The Fortran 77 solvers may crash with segmentation faults due to uninitialized variables that are used as indices.

  • Fix all uninitialized variable warnings stevengj/nlopt#134

  • Bobyqa uninitialised variables in rare cases stevengj/nlopt#133

  • Use of uninitialized variable in bobyqa altmov_() stevengj/nlopt#36

• 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.

  • nlopt COBYLA optimizer gives unexpected output stevengj/nlopt#182

  • Last Result Returned Not Optimized Result stevengj/nlopt#110

  • cobyla returns last evaluated function which might not be minimum stevengj/nlopt#57

  • Successful termination when constraints violated cureos/jcobyla#1

Expected Results

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 current version of PRIMA implements these 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.

I also note that there was an interest to include BOBYQA into Nevergrad, but it was not possible due to the license. PRIMA is licensed under the 3-Clause BSD, which I suppose is compatible with MIT.

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

Thanks.

Best regards,
Zaikun Zhang, Ph.D. and Assistant Professor
Department of Applied Mathematics
The Hong Kong Polytechnic University

[bottler]

Thanks for letting us know about this. I think for nevergrad we should wait and see how the scipy issue gets resolved.