Dedicated to late Professor M. J. D. Powell FRS (1936--2015)
PRIMA provides the reference implementation for Powell's 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 is part of a research project funded by the Hong Kong Research Grants Council and the Department of Applied Mathematics (AMA) at the Hong Kong Polytechnic University (PolyU). It is still under intensive development, and there is no release yet. If you want to use the above-mentioned methods, see the website and repository of PDFO instead (Py-BOBYQA is also highly recommended if you intend to solve bound-constrained problems).
PRIMA was initiated by Zaikun Zhang in July 2020, based on the PDFO package by Tom M. Ragonneau and Zaikun Zhang.
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 the citations of COBYLA and BOBYQA).
However, Professor Powell's implementation is in Fortran 77 and the code is nontrivial to understand or maintain, let alone to extend. This becomes an obstacle for many practitioners to exploit these solvers in their applications and hinders researchers from exploring the wealth left by Professor Powell to the community.
Before he passed, Professor Powell had asked me to maintain his solvers. This is an honorable mission, and I have the responsibility to make the solvers more accessible. PRIMA is a project somehow similar to the translation, interpretation, and annotation of Euclid’s Elements. It will make Powell's solvers easily accessible 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), MATLAB, Python, C++, and probably Julia and R. It will be a faithful implementation, in the sense that the code will be mathematically equivalent to Powell’s, 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 easily 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.
There do exist "translations" of Powell's Fortran 77 code into 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.
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. Extensive 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.
The tests are automated by
GitHub Actions. As of January 2023, more than
30,000 "workflows" have been successfully run by GitHub Actions.
Normally, each workflow consists of ~ 5
(sometimes more than 100)
randomized tests that are conducted in parallel,
each test taking from tens of minutes to several hours (the maximum
is 6 hours, after which the workflow will be canceled automatically). In other words,
PRIMA has been verified by more than
Since each GitHub Team account can only run at most 60 GitHub Actions jobs, I have to distribute this large amount of tests to several different Team accounts as follows.
-
-
-
-
- all the tests are disabled
After almost three years of intensive coding, the modern Fortran version of PRIMA has been finished by December 2022. An interface is also provided for using the Fortran implementation under MATLAB. Interfaces for other languages will be available later.
Given the modern Fortran version, the implementation in other languages becomes much easier, because we now have a structured and modularized implementation as a reference. As an illustration, I have implemented a MATLAB version of NEWUOA based on an earlier version of the modern Fortran code (with the help of Mr. Galann Pennec). The MATLAB code was obtained from the modern Fortran code straightforwardly, and indeed, automatically.
PRIMA has fixed the some serious issues in the original Fortran 77 implementation of Powell's methods. Note that all the issues are problems in the Fortran 77 code rather than flaws in the algorithms.
The examples given below are bugs or requests sent to SciPy, NLopt, nloptr, OpenTURNS, etc., which are reputable packages that wrap/interface the original Fortran 77 implementation of Powell's solver. Inevitably, they suffer from the bugs in the Fortran 77 code.
-
The solvers may crash with segmentation faults due to uninitialized variables that are used as indices.
-
The solvers may get stuck in infinite loops.
-
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.
Due to the improvements introduced into the new implementation, PRIMA outperforms Powell's
original code in terms of the number of function evaluations, which is the standard performance
indicator in derivative-free optimization.
Below are the performance profiles
of the PRIMA solvers compared with Powell's implementation, the convergence tolerance being
- NEWUOA on unconstrained CUTEst problems of at most 50 variables
- BOBYQA on bound-constrained CUTEst problems of at most 50 variables
- LINCOA on linearly constrained CUTEst problems of at most 50 variables and 5000 constraints
- COBYLA on nonlinearly constrained CUTEst problems of at most 20 variables and 2000 constraints
- UOBYQA on unconstrained CUTEst problems of at most 20 variables
In the past years, while working on PRIMA, I have spotted a dozen of bugs in reputable Fortran compilers and two bugs in MATLAB. Each of them represents days of bitter debugging, which finally led to the conclusion that it was not a problem in my code but a flaw in the Fortran compilers or in MATLAB. From a very unusual angle, this reflects how intensive the coding has been.
The bitterness behind this "fun" fact is exactly why I work on PRIMA: I hope that all the frustrations that I have experienced will not happen to any user of Powell's methods anymore.
PRIMA is dedicated to the memory of late Professor Powell with gratitude for his inspiration and for the wealth he left to us.
I am grateful to Professor Ya-xiang Yuan for his everlasting encouragement and support.
The development of PRIMA would have been a mission impossible without the groundwork laid by the PDFO package of Tom M. Ragonneau and Zaikun Zhang. PDFO is Chapter 3 of Ragonneau's thesis supervised by Zhang and financially supported by the Hong Kong Ph.D. Fellowship Scheme (ref. PF18-24698).
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).