-
Notifications
You must be signed in to change notification settings - Fork 11
BOBYQA
Bound Optimization BY Quadratic Approximation for .NET
A C# implementation of Michael Powell's nonlinear derivative-free bound constrained optimization method BOBYQA. The algorithm applies a trust region method that forms quadratic models by interpolation. There is usually some freedom in the interpolation conditions, which is taken up by minimizing the Frobenius norm of the change to the second derivative of the model, beginning with the zero matrix. The values of the variables are constrained by upper and lower bounds.
The C# implementation is relatively faithful to the original Fortran 77 implementation. It should be noted however that the indexing of the variables and constraints arrays in the public interface is zero-based, i.e. for a problem with 3 variables, x[0], x[1] and x[2] should be employed in the objective function evaluations. Furthermore, the signature of the objective function evaluation method is different from the original Fortran implementation.
Implement a method for computing the objective function with the following signature:
double calfun(int n, double[] x)
where n is the number of variables and x is the variable array. The method should return the calculated objective function value.
To minimize the objective function subject to bounds, initialize a Bobyqa instance and call the FindMinimum instance method:
var optimizer = new Bobyqa(n, calfun, xl, xu);
var result = optimizer.FindMinimum(x0);
where n is the number of optimization variables and xl and xu are lower and upper variable bounds, respectively, of type double[]. x0 is the initial variable array, of type double[].
You may additionally set Bobyqa properties InterpolationConditions (recommended value 2 * n + 1 where n is the number of variables in x), TrustRegionRadiusStart and TrustRegionRadiusEnd, MaximumFunctionCalls which is the maximum allowed number of function evaluations, PrintLevel (0..3) which specifies the level of output, and Logger which is a text writer to where BOBYQA's log will be output.
The FindMinimum method returns the result as an OptimizationResult object containing:
OptimizationStatus Status /* Optimization status upon exit from BOBYQA */
int Evals /* Total number of function evaluations */
double F /* Optimal value of the objective function
double[] X /* Optimal values of the optimization variables */
Upon instantiation, Bobyqa applies these default values as follows: MaximumFunctionCalls = 10000, PrintLevel = 1 and Logger = null. InterpolationConditions is by default set to 2 * n + 1. TrustRegionRadiusStart is by default based on the variable start values and the ranges of the bounds. TrustRegionRadiusEnd is by default set to one millionth of the applied TrustRegionRadiusStart.
If xl and/or xu are set to null in the constructor, all optimization variables are considered to be unbounded downwards and upwards, respectively. To solve an unbounded optimization problem, the constructor can thus potentially be invoked as follows:
var optimizer = new Bobyqa(n, calfun);
/.../ BOBYQA is attached. Its purpose is to seek the least value of a function F of several variables, when derivatives are not available, where F is specified by the user through a subroutine called CALFUN. The name BOBYQA denotes Bound Approximation BY Quadratic Approximation, the constraints being lower and upper bounds on every variable, which can be set to huge values for unconstrained variables. The algorithm is intended to change the variables to values that are close to a local minimum of F. The user, however, should assume responsibility for finding out if the calculations are satisfactory, by considering carefully the values of F that occur. The BOBYQA software has been developed from the method of the paper "The NEWUOA software for unconstrained minimization without derivatives", in Large-Scale Nonlinear Optimization, editors G. Di Pillo and M. Roma, Springer (2006), pages 255-297. /.../
In addition to providing CALFUN, an initial vector of variables and the lower and upper bounds, the user has to set the values of the parameters RHOBEG, RHOEND and NPT. After scaling the individual variables if necessary, so that the magnitudes of their expected changes are similar, RHOBEG is the initial steplength for changes to the variables, a reasonable choice being the mesh size of a coarse grid search. Further, RHOEND should be suitable for a search on a very fine grid. Typically, the software calculates a vector of variables that is within distance 10RHOEND of a local minimum. Another consideration is that every trial vector of variables is forced to satisfy the lower and upper bounds, but there has to be room to make a search in all directions. Therefore an error return occurs if the difference between the bounds on any variable is less than 2RHOBEG. The parameter NPT specifies the number of interpolation conditions on each quadratic model, the value NPT=2*N+1 being recommended for a start, where N is the number of variables. It is often worthwhile to try other choices too, but much larger values tend to be inefficient, because the amount of routine work of each iteration is of magnitude NPT**2, and because the achievement of adequate accuracy in some matrix calculations becomes more difficult. Some excellent numerical results have been found in the case NPT=N+6 even with more than 100 variables. /.../
January 5th, 2009, M.J.D. Powell.