<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](#what)
- [Why](#why)
- [How](#how)
- [Current status](#current-status)
- [Modern Fortran](#modern-fortran)
- [MATLAB](#matlab)
- [Python](#python)
- [Other languages](#other-languages)
- [Bug fixes](#bug-fixes)
- [Improvements](#improvements)
- [Who was Powell?](#who-was-powell)
- [A "fun" fact](#a-fun-fact)
- [Acknowledgment](#acknowledgment)
- [Citing PRIMA](#citing-prima)
- [Charityware](#charityware)
- [Contact](#contact)
- [Mirrors](#mirrors)
- [Gitee](https://gitee.com/libprima/prima)
- [GitHub](https://github.com/libprima/prima)
- [GitLab](https://gitlab.com/libprima/prima)
- [Star history](#star-history)
### What
PRIMA is a package for **solving general nonlinear optimization problems without using derivatives**.
It provides the reference implementation of Powell's renowned derivative-free optimization methods, i.e., COBYLA, UOBYQA, NEWUOA, BOBYQA, and LINCOA.
The "P" in the name stands for [**P**owell](https://www.zhangzk.net/powell.html),
and "RIMA" is an acronym for "**R**eference **I**mplementation with **M**odernization and **A**melioration".
PRIMA is part of a research project funded by the
[Hong Kong Research Grants Council](https://www.ugc.edu.hk/eng/rgc) and
the [Department of Applied Mathematics](https://www.polyu.edu.hk/ama) (AMA) at the
[Hong Kong Polytechnic University](https://www.polyu.edu.hk) (PolyU).
The current version is ready to be [used in MATLAB](https://github.com/libprima/prima/blob/main/README_mat.md).
If you want to use the above-mentioned methods in Python, see the [website](https://www.pdfo.net)
and [repository](https://github.com/pdfo/pdfo) of [PDFO](https://www.pdfo.net) instead.
PRIMA was initiated by [Zaikun Zhang](https://www.zhangzk.net) in July 2020, based on
the [PDFO](https://www.pdfo.net) package by [Tom M. Ragonneau](https://tomragonneau.com/) and Zaikun Zhang.
See [Zaikun Zhang's talk](https://raw.githubusercontent.com/ztalks/20230603-siopt23/main/202306-siopt23.pdf) on PRIMA at [SIAM Conference on Optimization 2023](https://www.siam.org/conferences/cm/conference/op23) 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](https://arxiv.org/pdf/2302.13246.pdf)
as well as the Google searches of [COBYLA](https://www.google.com/search?q=cobyla)
and [BOBYQA](https://www.google.com/search?q=bobyqa).
However, Professor Powell's implementation was done in [Fortran 77](./fortran/original).
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 to us. By all means, it is
[necessary to make the solvers available in languages other than Fortran](https://permalink.lanl.gov/object/tr?what=info:lanl-repo/lareport/LA-UR-23-23992)
promptly, first wrapping Powell's code, which is the objective of [PDFO](https://www.pdfo.net),
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](https://www.numerical.rl.ac.uk/people/nimg) to maintain his solvers.
This is an honorable mission. To make the solvers more accessible, I started PRIMA.
It is a project somehow 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*](https://en.wikipedia.org/wiki/Euclid%27s_Elements#Translations),
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](https://fortran-lang.org) (F2008 or newer), MATLAB, Python, C++,
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](#bug-fixes) and [improvements](#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 into other languages. For example,
[NLopt](https://github.com/stevengj/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](https://netlib.org/f2c/f2c.pdf), and hence inherits the style, structure,
and probably [bugs](#bug-fixes) of the original Fortran 77 implementation.
Note, however, that
[Py-BOBYQA](https://numericalalgorithmsgroup.github.io/pybobyqa/) 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](./matlab/setup_tools/freeform.m).
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](https://github.com/ralna/CUTEst) problems via [MatCUTEst](https://github.com/equipez/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](https://github.com/libprima/prima/blob/main/matlab/tests/private/tough.m)**.
[**Stress tests**](#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](https://docs.github.com/en/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](https://github.com/primalib/prima/actions/runs/5763631681))
**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.**
Since each GitHub Team account can only run at most 60 GitHub Actions workflows concurrently, I have
to distribute this large amount of tests to several different Team accounts as follows.
- [Tests](https://github.com/libprima/prima/actions) at [libprima/prima](https://github.com/libprima/prima)
- [![Check Spelling](https://github.com/libprima/prima/actions/workflows/spellin