The BOBYQA algorithm for bound constrained optimization without derivatives

Abstract

BOBYQA is an iterative algorithm for finding a minimum of a function F(x), x2R n , subject to bounds axb on the variables, F being specified by a black box that returns the value F(x) for any feasible x. Each iteration employs a quadratic approximation Q to F that satisfies Q(y j )= F(y j ), j =1 ,2,...,m, the interpolation points y j being chosen and adjusted automatically, but m is a prescribed constant, the value m =2 n+1 being typical. These conditions leave much freedom in Q, taken up when the model is updated by the highly successful technique of minimizing the Frobenius norm of the change to the second derivative matrix of Q. Thus no first derivatives of F are required explicitly. Most changes to the variables are an approximate solution to a trust region subproblem, using the current quadratic model, with a lower bound on the trust region radius that is reduced cautiously, in order to keep the interpolation points well separated until late in the calculation, which lessens damage from computer rounding errors. Some other changes to the variables are designed to improve the model without reducing F. These techniques are described. Other topics include the starting procedure that is given an initial vector of variables, the value of m and the initial trust region radius. There is also a new device called RESCUE that tries to restore normality if severe loss of accuracy occurs in the matrix calculations of the updating of the model. Numerical results are reported and discussed for two test problems, the numbers of variables being between 10 and 320.