-

 

 

 




Optimization Online





 

The BOBYQA algorithm for bound constrained optimization without derivatives

MJD Powell(mjdp***at***cam.ac.uk)

Abstract: BOBYQA is an iterative algorithm for finding the minimum of a function F(x) subject to lower and upper bounds on the variables, F(x) 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 automatically, but m is a prescribed constant, the value m=2n+1 being typical, where n is the number of variables. These conditions leave much freedom in Q, taken up when the model is updated by 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 the damage from computer rounding errors. Some other changes to the model 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.

Keywords: Bound constraints. No derivatives. Nonlinear optimization. Quadratic models. Trust regions.

Category 1: Nonlinear Optimization (Bound-constrained Optimization )

Citation: Report DAMTP 2009/NA06, Centre for Mathematical Sciences, University of Cambridge, UK (August, 2009).

Download: [PDF]

Entry Submitted: 05/14/2010
Entry Accepted: 05/14/2010
Entry Last Modified: 05/14/2010

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society