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