Prima

<h2 align="center">PRIMA: Reference Implementation for Powell's Methods with Modernization and Amelioration</h2> <p align="center">Dedicated to the late Professor <b><a href="https://www.zhangzk.net/powell.html">M. J. D. Powell</a></b> FRS (1936--2015)</p>

• What
• Why
• How
• Current status
  • Modern Fortran
  • C
  • Python
  • MATLAB
  • Julia
  • Other languages
• Bug fixes
• Improvements
• Who was Powell?
• A "fun" fact
• Acknowledgment
• Citing PRIMA
• Charityware
• Contact
• Mirrors
  • Gitee
  • GitHub
• Star history
• Users

What

PRIMA is a package for solving general nonlinear optimization problems without using derivatives. It provides the reference implementation for Powell's renowned derivative-free optimization methods, i.e., 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".

The current version is ready to be used in Fortran, in C, in Python, in MATLAB, and in Julia.

PRIMA was initiated by Zaikun Zhang in July 2020, based on the PDFO package.

See Zaikun Zhang's talk on PRIMA at The 10th International Congress on Industrial and Applied Mathematics for more information.

Why

Professor Powell carefully implemented his derivative-free optimization methods into publicly available solvers, which are genuine masterpieces. 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.

However, Professor Powell's implementation was done in Fortran 77. The code is nontrivial to understand or maintain, let alone extend. For many practitioners, this has become an obstacle to exploiting these solvers in their applications. Even worse, it has hindered researchers from exploring the wealth left by Professor Powell. By all means, it is necessary to make the solvers available in languages other than Fortran promptly, first wrapping Powell's code, which is the objective of PDFO, and then providing native and modernized implementations, which is the mission of PRIMA.

Before he passed, Professor Powell had asked me and Professor Nick Gould to maintain his solvers. This is an honorable mission. To make the solvers more accessible, I started PRIMA. It is a project similar to the translation, interpretation, and annotation of Euclid’s Elements. It will make Powell's solvers easily understandable to everyone, not only the experts. Few people remember who translated Elements, but it is a job that must be done.

PRIMA aims to provide the reference implementation of Powell's methods in modern languages, including modern Fortran (F2008 or newer), C/C++, Python, MATLAB, Julia, and R. It will be a faithful implementation, in the sense that the code will be mathematically equivalent to Powell’s (verified by differential testing), except for the bug fixes and improvements made intentionally.

The focus is to implement these methods in a structured and modularized way so that they are understandable, maintainable, extendable, fault-tolerant, and future-proof. The code will have no GOTO (of course) and will use matrix-vector procedures instead of loops whenever possible. In doing so, PRIMA codes the algorithms in a way that we would present them on a blackboard. Such an implementation will enable us to get a deeper understanding of Powell's methods and pave the way for new developments based on them.

There do exist "translations" of Powell's Fortran 77 code in other languages. For example, NLopt contains a C version of COBYLA, NEWUOA, and BOBYQA, but the C code in NLopt is translated from the Fortran 77 code straightforwardly, if not automatically by f2c, and hence inherits the style, structure, and probably bugs of the original Fortran 77 implementation. Note, however, that Py-BOBYQA is a true translation of BOBYQA to Python, with significant improvements.

How

The mission of PRIMA is nontrivial due to the delicacy of Powell's algorithms and the unique style of his code. To ensure the faithfulness of PRIMA, the modern Fortran version was started by refactoring Powell's code into the free form via a small MATLAB tool. However, such refactored code is far from what is desired, because it inherits completely the structure and style of Powell's code except for the layout. Significant modifications are needed to reorganize (indeed, to rewrite) the code. To maintain the faithfulness and quality of the reference implementation, extensive tests are conducted after each and every tiny modification, using the CUTEst problems via MatCUTEst. The tests do not only verify the faithfulness of the implementation but also check that the solvers behave properly even if they are invoked with improper inputs or encounter failures of function evaluations (essentially fuzz testing). Stress tests are also conducted periodically to verify that the solvers work correctly without running into errors when applied to excessively large problems.

The tests are automated by GitHub Actions. As of August 2023, more than 45,000 "workflows" have been successfully run by GitHub Actions. Normally, each workflow consists of ~ 5 (sometimes more than 200) randomized tests, each test taking from tens of minutes to several hours (the maximum is 6 hours, after which the test will be canceled automatically). In other words, PRIMA has been verified by more than 200,000 hours (or more than 20 years) of randomized tests. Code must be battle-tested before becoming software.

Current status

Modern Fortran

After almost three years of intensive coding, the modern Fortran version of PRIMA was finished by December 2022. It can be compiled using CMake as follows.<a name="cmake"></a>

git clone --depth 1 https://github.com/libprima/prima.git
cd prima
cmake -S . -B build -DCMAKE_INSTALL_PREFIX=install
cmake --build build --target install

This should create the primaf library for Fortran usage, located in the install/lib/ directory to be used with the module files in install/include/prima/mod/. In case CMake fails to find your Fortran compiler, you can indicate it by specifying -DCMAKE_Fortran_COMPILER=/path/to/your/Fortran/compiler. Similarly, set -DCMAKE_C_COMPILER=/path/to/your/C/compiler for your C compiler if needed.

Examples on how to use the library from an external code are available in fortran/examples/. Below is an illustration with COBYLA.

cd fortran/examples/cobyla
cmake -S . -B build -DCMAKE_INSTALL_PREFIX=install -DPRIMA_DIR=$PWD/../../../install/lib/cmake/prima/
cmake --build build --target install
LD_LIBRARY_PATH=$LD_LIBRARY_PATH:$PWD/../../../install/lib ./install/bin/cobyla_example_1

C

A C binding to the Fortran library is available in the c/ folder. In the same way as the Fortran library, it can be compiled using CMake, which should also create the primac library for C compilation, located in install/lib/ to be used with the prima.h header in install/include/prima/.

Examples on how to use the library from an external code are available in c/examples/. Below is an illustration with COBYLA.

cd c/examples/cobyla
cmake -S . -B build -DCMAKE_INSTALL_PREFIX=install -DPRIMA_DIR=$PWD/../../../install/lib/cmake/prima/
cmake --build build --target install
LD_LIBRARY_PATH=$LD_LIBRARY_PATH:$PWD/../../../install/lib ./install/bin/cobyla_example

Python

• An interface is provided for using the modern Fortran implementation in Python.
• SciPy 1.16.0 replaces the buggy and unmaintained Fortran 77 version of COBYLA underlying scipy.optimize.minimize with the PRIMA version, which is a faithful Python translation of the **[modern Fortran implementation](./fort