zbMATH — the first resource for mathematics

The NEWUOA software for unconstrained optimization without derivatives. (English) Zbl 1108.90005
Di Pillo, Gianni (ed.) et al., Large-scale nonlinear optimization. Papers based on the presentation at the workshop on large scale nonlinear optimization, Erice, Italy, June 22–July 1, 2004. New York, NY: Springer (ISBN 0-387-30063-5/hbk). Nonconvex Optimization and Its Applications 83, 255-296 (2006).
Summary: The NEWUOA software seeks the least value of a function \(F (\underline x)\), \(\underline x\in\mathbb R^n\), when \(F(\underline x)\) can be calculated for any vector of variables \(\underline x\). The algorithm is iterative, a quadratic model \(Q\approx F\) being required at the beginning of each iteration, which is used in a trust region procedure for adjusting the variables. When \(Q\) is revised, the new \(Q\) interpolates \(F\) at \(m\) points, the value \(m=2n+1\) being recommended. The remaining freedom in the new \(Q\) is taken up by minimizing the Frobenius norm of the change to \(\nabla^2Q\). Only one interpolation point is altered on each iteration. Thus, except for occasional origin shifts, the amount of work per iteration is only of order \((m+n)^2\), which allows \(n\) to be quite large. Many questions were addressed during the development of NEWUOA, for the achievement of good accuracy and robustness. They include the choice of the initial quadratic model, the need to maintain enough linear independence in the interpolation conditions in the presence of computer rounding errors, and the stability of the updating of certain matrices that allow the fast revision of \(Q\). Details are given of the techniques that answer all the questions that occurred. The software was tried on several test problems. Numerical results for nine of them are reported and discussed, in order to demonstrate the performance of the software for up to 160 variables.
For the entire collection see [Zbl 1087.90003].

90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C30 Nonlinear programming
90C56 Derivative-free methods and methods using generalized derivatives