UOBYQA: unconstrained optimization by quadratic approximation

UOBYQA is a new algorithm for general unconstrained optimization Calculations, that takes account of the curvature of the objective function, F say, by forming quadratic models by interpolation. Therefore, because no first derivatives are required, each model is defined by 1/2 (n+l)(n+2) values of F, where n is the number of variables, and the interpolation points must have the property that no nonzero quadratic polynomial vanishes at all of them. A typical iteration of the algorithm generates a new vector of variables, (x) over tilde (t) say, either by minimizing the quadratic model subject to a trust region bound, or by a procedure that should improve the accuracy of the model. Then usually F((x) over bar (t)) is obtained, and one of the interpolation points is replaced by (x) over tilde (t). Therefore the paper addresses the initial positions of the interpolation points. the adjustment of trust region radii, the calculation of (x) over tilde (t) in the two cases that have been mentioned. and the selection of the point to be replaced. Further, UOBYQA works with the Lagrange functions of the interpolation equations explicitly, so their coefficients are updated when an interpolation point is moved. The Lagrange functions assist the procedure that improves the model, and also they provide an estimate of the error of the quadratic approximation to F, which allows the algorithm to achieve a fast rate of convergence. These features are discussed and a summary of the algorithm is given. Finally, a Fortran implementation of UOBYQA is applied to several choices of F, in order to investigate accuracy, robustness in the presence of rounding errors, the effects of first derivative discontinuities. and the amount of work. The numerical results are very promising for n less than or equal to 20, but larger values are problematical, because the routine work of an iteration is of fourth order in the number of variables.