IntroductionLast update: April 29, 2020

PDFO (Powell's Derivative-Free Optimization solvers) is a cross-platform package providing interfaces for using late Professor M. J. D. Powell's derivative-free optimization solvers, including UOBYQA, NEWUOA, BOBYQA, LINCOA, and COBYLA, which were originally implemented in Fortran 77.

Professor Powell devised these solvers to tackle general nonlinear optimization problems of continuous variables with or without constraints using only function values but not derivatives of the objective function or nonlinear constraint functions. In practice, such functions are often black boxes defined by simulations. Consequently, the corresponding optimization problems are often categorized as black-box optimization or simulation-based optimization. Problem specified by explicit formulas can probably be handled by other methods more efficiently. See the Decision Tree for Optimization Software for more information.

The current version of PDFO supports MATLAB and Python. It relies on MEX for MATLAB and F2PY for Python to compile the Fortran solvers and wrap them into user-friendly functions.

Based on Professor Powell's Fortran code, PDFO is developed by Tom M. Ragonneau and Zaikun Zhang at the Department of Applied Mathematics, the Hong Kong Polytechnic University.

Download Last update: June 10, 2020

Here is the latest release of PDFO. For earlier versions, see the Releases section. For the latest version under development, check our repository on GitHub (mirrored on GitLab and Gitee).

Download count on PyPI according to PePy:   PDFO downlaod count on PyPI

Installation Last update: June 10, 2020

PDFO can be installed separately for MATLAB and Python.

PDFO for MATLAB

Prerequisites

PDFO supports MATLAB R2014a and later releases. To use the MATLAB version of PDFO, you need first to configure the MEX of your MATLAB so that it can compile Fortran. To check whether your MEX is ready, run the following code in MATLAB:

mex('-setup', '-v', 'FORTRAN'); mex('-v', fullfile(matlabroot, 'extern', 'examples', 'refbook', 'timestwo.F'));

It will attempt to set up your MEX and then compile an example provided by MathWorks for testing MEX on Fortran. If this completes successfully, then your MEX is ready. Otherwise, it is not. To configure MEX for compiling Fortran, see the official documentation of MathWorks. It will require you to install a supported Fortran compiler on your system. Note that MathWorks (rather than PDFO) is quite rigid concerning the version of your compiler, which has to be compatible with the release of your MATLAB; the latest compiler is not necessarily supported by your MATLAB. On Windows, MathWorks needs you to install also Microsoft Visual Studio and Microsoft Windows SDK as well. Follow the official documentation closely.

Installation of PDFO

Download and decompress the source code package. You will obtain a folder containing setup.m. Place this folder at the location where you want PDFO to be installed. In MATLAB, change the directory to this folder, and execute the following command:

setup

If this command runs successfully, PDFO is installed. You may execute the following command in MATLAB to verify the installation:

testpdfo

PDFO for Python on Linux and Mac

Prerequisites

To use the Python version of PDFO on Linux or Mac, you need Python (headers included), NumPy, F2PY, and gfortran, which can be installed in the following way.

  1. Install Python (version 2.7 or above) following the Python website. To include the headers on Linux, python3-dev or python-dev should be installed depending on the Python you want to use; on Mac, the headers are included by default if you install Python using Homebrew.
  2. Install the latest version of SciPy following its official documentation. Then NumPy will be installed by default. NumPy provides F2PY.
  3. Install gfortranusing your package manager, e.g., apt on Debian/Ubuntu, yum on Fedora/RHEL/CentOS, and Homebrew on Mac.
  4. On Mac, it is necessary to install Xcode, which provides the libraries needed by F2PY.

Installation of PDFO

We recommend installing PDFO via PyPI. This does not need you to download the source code. Install pip in your system. Then execute

python -m pip install pdfo

in a command shell (e.g., the terminal in Linux or Mac). If your Python launcher is not python, adapt the command accordingly. If this command runs successfully, PDFO is installed. You may verify the installation by

python -m unittest pdfo.testpdfo

Alternatively, PDFO can be installed from the source code: download and decompress the source code package; you will obtain a folder containing setup.py; in a command shell, change your directory to this folder, and then run python setup.py install --user to install PDFO.

PDFO for Python on Windows

Prerequisites

To use the Python version of PDFO on Windows, you need Python 3 (PDFO does not support Python 2 on Windows), NumPy, F2PY, Microsoft Visual Studio, and Intel Fortran compiler (ifort), which can be installed in the following way.

  1. Install Python 3 following the Python website. Note that the Python installed from the Microsoft Store may not work. In addition, the version of Python has to be compatible with the Intel Fortran compiler; otherwise, Python may complain that some dll is missing.
  2. Install the latest version of SciPy following its official documentation. Then NumPy will be installed by default. NumPy provides F2PY.
  3. Install Microsoft Visual Studio. Make sure to include C++ Build Tools in the Workloads pane, and Microsoft Windows SDK in the Individual Components pane.
  4. Install the Intel Fortran compiler (ifort) according to the Intel website. Your installation has to include the Intel Distribution for Python (included by default). Note that ifort may not support the latest version of Python. As of June 15, 2020, the most recent release of ifort supports Python 3.7 according to the Key Specifications of the Intel Distribution for Python.

Installation of PDFO

PDFO can be installed via PyPI. This does not need you to download the source code. Install pip in your system. In the Intel command shell (either 32 or 64-bit, depending on your Python version), execute

python -m pip install pdfo

Make sure to run the above command in the correct Intel command shell, as it is critical to guarantee the compatibility between the compiler and you Python. If your Python launcher is not python, adapt the command accordingly. If this command runs successfully, PDFO is installed. You may verify the installation by

python -m unittest pdfo.testpdfo

Note that an Ubuntu terminal is available on Windows 10. Within such a terminal, you can use the Linux/Mac version of PDFO. The prerequisites are much easier to fulfill and no commercial software such as ifort is needed.

Usage Last update: May 30, 2020

PDFO for MATLAB

PDFO provides the following MATLAB functions: pdfo, uobyqa, newuoa, bobyqa, lincoa, and cobyla.

The pdfo function can automatically identify the type of your problem and then call one of Powell's Fortran solvers. The other five functions call the solver indicated by their names. It is highly recommended to use pdfo instead of uobyqa, newuoa, etc.

The pdfo function is designed to be compatible with the fmincon function available in the Optimization Toolbox of MATLAB. You can call pdfo in the same way as calling fmincon. In addition, pdfo can be called in some flexible ways that are not supported by fmincon, which will be illustrated in the example below.

For the detailed syntax of these functions, use the standard help command of MATLAB. For example,

help pdfo

will tell you how to use the pdfo function.

An example

The following code illustrates how to minimize the chained Rosenbrock function $$\sum_{i=1}^2 [(x_i - 1)^2 + 4(x_{i+1} - x_i^2)^2]$$ subject to various constraints.

Options

When calling pdfo, we may specify some options by passing a structure to pdfo as the last input. Here are several useful options.

  1. solver: a string indicating which solver to use; default: 'uobyqa' for unconstrained problems with at most 8 variables, 'newuoa' for unconstrained problems with 9 or more variables, 'bobyqa' for bound-constrained problems, 'lincoa' for linearly constrained problems, and 'cobyla' for nonlinearly constrained problems. If you want to choose a solver, note that UOBYQA and NEWUOA can solve unconstrained problems, NEWUOA being preferable except for rather small problems; BOBYQA can solve unconstrained and bound-constrained problems; LINCOA can solve unconstrained, bound-constrained, and linearly constrained problems; COBYLA can solve general nonlinear optimization problems. We observe that LINCOA sometimes outperforms NEWUOA on unconstrained problems. It is also worth noting that BOBYQA evaluates the objective function only at feasible points, while LINCOA and COBYLA may explore infeasible points.
  2. maxfun: maximal number of function evaluations; default: 500*length(x0).
  3. ftarget: target function value; pdfo terminates once it finds a feasible point with a function value at most ftarget; default: -inf.
  4. scale: a boolean value indicating whether to scale the problem according to bound constraints; if it is true and if all the variables have both lower and upper bounds, then the problem will be scaled so that the bound constraints become \(-1 \leq x \le 1\); default: false.
  5. rhobeg: initial trust-region radius; typically, rhobeg should be in the order of one tenth of the greatest expected change to a variable; rhobeg should be positive; default: 1 if the problem will not be scaled, and 0.5 if the problem will be scaled; in case of scaling, rhobeg will be used as the initial trust-region radius of the scaled problem.
  6. rhoend: final trust-region radius; rhoend reflects the precision of the approximate solution obtained by pdfo; rhoend should be positive and not larger than rhobeg; default: 1e-6; in case of scaling, rhoend will be used as the final trust-region radius of the scaled problem.

For instance, to minimize the aforementioned chained Rosenbrock function without constraints by LINCOA with at most \(50\) function evaluations and a target function value \(10^{-2}\), it suffices to replace pdfo(@chrosen, x0) in the above example by

pdfo(@chrosen, x0, struct('solver', 'lincoa', 'maxfun', 50, 'ftarget', 1e-2))

PDFO for Python

PDFO provides the following Python functions: pdfo, uobyqa, newuoa, bobyqa, lincoa, and cobyla.

The pdfo function can automatically identify the type of your problem and the call one of Powell's solvers. The other five functions call the solver indicated by their names. It is highly recommended to use pdfo instead of uobyqa, newuoa, etc.

The pdfo function is designed to be compatible with the minimize function available in the scipy.optimize module of SciPy. You can call pdfo in exactly the same way as calling minimize except that pdfo does not accept derivative arguments.

For detailed syntax of these functions, use the standard help command of Python. For example,

 from pdfo import pdfo; help(pdfo)

will tell you how to use pdfo.

An example

The following code illustrates how to minimize the chained Rosenbrock function defined above subject to various constraints.

Method and options

When using pdfo, we may specify the solver by passing a string to the keyword argument named method. Otherwise, pdfo will choose the solver in the same way as the MATLAB version does.

In addition, options may be specified by passing a dictionary to the keyword argument named options. Useful options include maxfev, ftarget, scale, rhobeg, and rhoend, who are identical to the options for the MATLAB version with the same names, except that the maximal number of function evaluations is named maxfev to align with the minimize function in scipy.optimize.

For instance, to minimize the aforementioned chained Rosenbrock function without constraints by LINCOA with at most \(50\) function evaluations and a target function value \(10^{-2}\), it suffices to replace pdfo(chrosen, x0) in the above example by

pdfo(chrosen, x0, method='lincoa', options={'maxfev': 50, 'ftarget': 1e-2})

Releases Last update: June 10, 2020

Here are all the releases of PDFO. For the latest version under development, check our repository on GitHub (mirrored on GitLab and Gitee).
Version number Date Remark
1.0 June 10, 2020 First stable version
0.9 April 19, 2020 Public beta release

Issues Last update: June 15, 2020

During the development of PDFO, some issues have occurred. We keep here a list of the most salient ones.

In case of problems or bugs when using PDFO, you may contact us or open a new issue on GitHub.

Date Description Status/Solution
June 15, 2020 As of June 15, 2020, version 1.0 of PDFO cannot be installed on Windows for Python 3.8 and onwards, because the most recent version of Intel Distribution for Python supports only Python 3.7. Higher versions of Python may be supported on Windows when Intel updates the Intel Distribution for Python.
April 19, 2020 Version 0.9 does not support 64-bit Python on Windows because F2PY does not work well with MinGW-w64. 64-bit Python is supported by version 1.0 on Windows.

References Last update: May 14, 2020

[1] M. J. D. Powell, A direct search optimization method that models the objective and constraint functions by linear interpolation, In Advances in Optimization and Numerical Analysis, eds. S. Gomez and J. P. Hennart, pages 51--67, Springer Verlag, Dordrecht, Netherlands, 1994

[2] M. J. D. Powell, UOBYQA: unconstrained optimization by quadratic approximation, Math. Program., 92(B):555--582, 2002

[3] M. J. D. Powell, Least Frobenius norm updating of quadratic models that satisfy interpolation conditions. Math. Program., 100:183--215, 2004

[4] M. J. D. Powell, On the use of quadratic models in unconstrained minimization without derivatives, Optim. Methods Softw., 19:399--411, 2004

[5] M. J. D. Powell, The NEWUOA software for unconstrained optimization without derivatives, In Large-Scale Nonlinear Optimization, eds. G. Di Pillo and M. Roma, pages 255--297, Springer, New York, US, 2006

[6] M. J. D. Powell, A view of algorithms for optimization without derivatives, Technical Report DAMTP 2007/NA63, Department of Applied Mathematics and Theoretical Physics, Cambridge University, Cambridge, UK, 2007

[7] M. J. D. Powell, Developments of NEWUOA for minimization without derivatives, IMA J. Numer. Anal., 28:649--664, 2008

[8] M. J. D. Powell, The BOBYQA algorithm for bound constrained optimization without derivatives, Technical Report DAMTP 2009/NA06, Department of Applied Mathematics and Theoretical Physics, Cambridge University, Cambridge, UK, 2009

[9] M. J. D. Powell, On fast trust region methods for quadratic models with linear constraints, Math. Program. Comput., 7:237--267, 2015

Remarks

  1. A key technique underlying the success of NEWUOA, BOBYQA, and LINCOA is the least Frobenius norm updating of quadratic models elaborated in [3] and [4]. The idea comes from the least change update for quasi-Newton methods, a vast research area initiated by the DFP algorithm, where P stands for Powell.
  2. LINCOA seeks the least value of a nonlinear function subject to linear inequality constraints without using derivatives of the objective function. Professor Powell did not publish a paper to introduce the algorithm. The paper [9] discusses how LINCOA solves its trust-region subproblems.
  3. Zaikun Zhang gave a brief introduction to PDFO in his talk "PDFO: Powell’s Derivative-Free Optimization Solvers with MATLAB and Python Interfaces" delivered (online) at the State Key Laboratory of Scientific and Engineering Computing, Chinese Academy of Sciences on May 13, 2020.
  4. If you would like to mention PDFO in your work, you may cite it as follows. A paper will be published later. Thank you.

    T. M. Ragonneau and Z. Zhang, PDFO: Cross-Platform Interfaces for Powell's Derivative-Free Optimization Solvers (Version 1.0), available at https://www.pdfo.net, doi:10.5281/zenodo.3887569, 2020

Licence Last update: June 10, 2020

PDFO is free software. You can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

PDFO is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.