Bound Optimization BY Quadratic Approximation

NAG Library mini-article

Mark 23 of the NAG Library and the NAG Toolbox for MATLAB® expands the functionality provided by the Chapter for Minimizing or Maximizing a Function (E04). The BOBYQA (Bound Optimization BY Quadratic Approximation) algorithm of Prof. Mike Powell, University of Cambridge, is now available in the Library. This robust method is an easy-to-use algorithm that employs quadratic approximation and trust regions to minimize an objective subject to bound constraints. No derivatives of the objective function are required, and the solver's efficiency is preserved for large problem sizes.

As a simple example, the problem of distributing 50 points on a sphere to have maximal pairwise separation, starting from equispaced points on the equator (see also Powell (2009)), is solved using 4633 function evaluations. This compares with 16757 taken by the NAG Nelder–Mead simplex solver on the same problem (run on a machine using GCC 4.5.2, Fedora 10, four 2.00GHz dual-core Intel® Xeon® E5405 processors, 8Gb RAM).

Reference: Powell M.J.D. (2009), "The BOBYQA algorithm for bound constrained optimization without derivatives", Report DAMTP 2009/NA06, University of Cambridge.

Related information

The Price of Derivatives - Derivative-free Optimization · read the blog post

NAG Library Function Document for (e04jcc) - Bound constrained minimum, model-based algorithm, using function values only