Introduction Last update: August 23, 2021

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: October 28, 2021

Here is the latest release of PDFO. For earlier versions, see the Releases section.

While MATLAB users need to download this source code package to install PDFO, Python users can install PDFO via PyPI without the source code. See the Installation section for more details.

Installation Last update: August 23, 2021

PDFO can be installed separately for MATLAB and Python.

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')); timestwo(1); delete('timestwo.mex*'); 

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. Follow the official documentation closely.

Installation

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

Python

Recommended installation

To use the Python version of PDFO on Linux, Mac, or Windows, you need Python 3.7 or above.

We highly 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, or the Command Shell for Windows). 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

If you are an Anaconda user, PDFO is also available through the conda installer. However, it is not managed by us.

Alternatively, although deeply discouraged, PDFO can be installed from the source code. It requires you to install additional Python headers, a Fortran compiler (e.g., gfortran), and F2PY (provided by NumPy). 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 -m pip install ./ to install PDFO.

Usage Last update: May 30, 2020

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))

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: October 28, 2021

Here are all the releases of PDFO. For the latest version under development, check our repository on GitHub or the mirrors on GitLab and Gitee.
Version number Date Remark
1.2 October 7, 2021 Rebuilt of Python wheels to include devlewheel patch for Anaconda
1.1 August 23, 2021 Simplify installation for Python by providing wheels on PyPI for Linux, macOS, and Windows
1.0 June 10, 2020 First stable version
0.9 April 19, 2020 Public beta release

Issues Last update: August 23, 2021

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
August 23, 2021 Python users of version 1.0 and below needed to install manually some dependencies, e.g., Python headers and a Fortran compiler. Wheel distributions are now available on PyPI for Windows, Linux, and macOS. The wheel distributions are generated automatically using GitHub Actions. Users do not need to handle the dependencies anymore as long as they install PDFO via PyPI with Python 3.7 or above.
June 15, 2020
As of June 15, 2020, version 1.0 of PDFO could not be installed on Windows for Python 3.8 and above, because the most recent version of Intel Distribution for Python supports only Python 3.7.
The latest versions of Python are supported on Windows by version 1.1 and above.
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 and above on Windows.
Click here to see more/less issues.

References Last update: August 23, 2021

[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, On updating the inverse of a KKT matrix, in Numerical Linear Algebra and Optimization, ed. Ya-xiang Yuan, Science Press (Beijing), pp. 56--78, 2004

[6] 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

[7] 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

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

[9] 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

[10] 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. The least Frobenius norm updating is a quadratic programming problem, whose constraints correspond to the interpolation conditions. At each iteration of Powell's algorithms, only one of the constraints is different from the previous iteration. To solve this problem efficiently and stably, Powell designed a procedure to update the inverse of its KKT matrix along the iterations. Such a procedure is detailed in [5], and it is indispensable for the remarkable numerical stability of NEWUOA, BOBYQA, and LINCOA.
  3. 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 [10] discusses how LINCOA solves its trust-region subproblems.
  4. 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.
  5. Tom M. Ragonneau presented PDFO in his talk "PDFO: a Cross-Platform MATLAB/Python Interface for Powell's Derivative-Free Optimization Solvers" delivered (online) at the SIAM Conference on Optimization (OP21), on July 21, 2021.
  6. 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.1), available at https://www.pdfo.net, doi:10.5281/zenodo.3887569, 2021

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.

Acknowledgment Last update: August 23, 2021

PDFO is dedicated to the memory of late Professor Powell with gratitude for his inspiration and for the treasures he left to us.

We are grateful to Professor Ya-xiang Yuan for his everlasting encouragement and support.

The development of PDFO is funded by the Hong Kong Research Grants Council (ref. PolyU 253012/17P and PolyU 153054/20P), the Hong Kong Ph.D. Fellowship Scheme (ref. PF18-24698), and the Hong Kong Polytechnic University.