Bound Optimization BY Quadratic Approximation for .NET
csbobyqa is 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.
M.J.D. Powell, “The BOBYQA algorithm for bound constrained optimization without derivatives”, DAMTP 2009/NA06 Report, www.damtp.cam.ac.uk/user/na/NA_papers/NA2009_06.pdf
Original Fortran 77 implementation: plato.asu.edu/ftp/other_software/bobyqa.zip
C# port of nonlinear constrained derivative-free optimization method COBYLA2: github.com/cureos/cscobyla
The file Bobyqa.cs can be included as-is in any C# project, .NET Framework 4.0 or later, Silverlight 4 or later and Windows Phone 7.5 and later. With very limited modifications the source code can also be incorporated in .NET. 2.0 projects etc.
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, x and x 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, call the static Bobyqa.FindMinimum method:
BobyqaExitStatus FindMinimum(Func<int, double, double> calfun, int n, double x, double xl, double xu, int npt, double rhobeg, double rhoend, int iprint, int maxfun, TextWriter logger)
where x on input is the initial variable array, xl and xu are lower and upper variable bounds, respectively, npt is the number of interpolation conditions (recommended value 2 * n + 1), rhobeg and rhoend are initial and final values of a trust region radius, iprint (0..3) specifies the level of output to the console, maxfun is the maximum allowed number of function evaluations, and logger is a text writer to where Bobyqa's log will be output. On output x provides the optimal obtained variable values. The method returns optimization status on exit from BOBYQA.
If xl and/or xu are set to null, all optimization variables are considered to be unbounded downwards and upwards, respectively. If npt is set to a non-positive value, the npt value applied in the optimization is equal to 2 * n + 1. If rhobeg is set to a non-positive value, the rhobeg value applied in the optimization will be based on the variable start values and the ranges of the bounds. If rhoend is set to a non-positive value, the rhoend vlaue applied in the optimization will be one millionth of the applied rhobeg.
The FindMinimum method also implements default values as follows: xl = null, xu = null, npt = -1, rhobeg = -1, rhoend = -1, iprint = 1, maxfun = 10000 and logger = null.
To solve an unbounded optimization problem, the method can thus potentially be called as follows, employing the above default parameter values in the minimization:
var status = Bobyqa.FindMinimum(calfun, n, x);
Copyright © 2009 Michael Powell, 2012 Anders Gustafsson, Cureos AB.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
/…/ 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 10*RHOEND 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 2*RHOBEG. 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.
/…/ There are no restrictions on or charges for the use of the software. I hope that the time and effort I have spent on developing the package will be helpful to much research and to many applications.
January 5th, 2009, M.J.D. Powell.
May 8, 2012: Updated default value info for rhobeg and rhoend.
May 7, 2012: Added info on logger option.
April 20, 2012: Initial document.