NAG CL Interface
e05kbc (handle_​solve_​mcs)

Note: this function uses optional parameters to define choices in the problem specification and in the details of the algorithm. If you wish to use default settings for all of the optional parameters, you need only read Sections 1 to 10 of this document. If, however, you wish to reset some or all of the settings please refer to Section 11 for a detailed description of the algorithm, and to Section 12 for a detailed description of the specification of the optional parameters.
Settings help

CL Name Style:


1 Purpose

e05kbc is designed to find the global minimum or maximum of an arbitrary function, subject to simple bound-constraints using a multi-level coordinate search method. Derivatives are not required, but convergence is only guaranteed if the objective function is continuous in a neighbourhood of a global optimum. It is not intended for large problems.

2 Specification

#include <nag.h>
void  e05kbc (void *handle,
void (*objfun)(Integer nvar, const double x[], double *fx, Integer *inform, Nag_Comm *comm),
void (*monit)(Integer nvar, const double x[], Integer *inform, const double rinfo[], const double stats[], Nag_Comm *comm),
Integer nvar, double x[], double rinfo[], double stats[], Nag_Comm *comm, NagError *fail)
The function may be called by the names: e05kbc or nag_glopt_handle_solve_mcs.

3 Description

e05kbc is aimed at minimizing a nonlinear objective function subject to bound constraints:
minimize xn f (x) subject to lx x ux .  
Here f is a smooth nonlinear function and lx and ux are n-dimensional vectors defining bounds on the variables.
e05kbc serves as a solver for compatible problems stored as a handle. The handle points to an internal data structure which defines the problem and serves as a means of communication for functions in the NAG optimization modelling suite. To define a compatible problem handle, you must call e04rac to initialize it followed, optionally, by e04rgc, e04rec or e04rfc to define the objective function and e04rhc to define bounds on the variables. If e04rhc is not called, all the variables will be considered free by the solver. It should be noted that e05kbc always assumes that the gradient of the objective is dense, therefore, defining a sparse structure for the residuals in the call to e04rgc will have no effect. Additionally, the multi-level coordinate search method used by this solver relies on dividing the feasible space in ‘boxes’ (see Section 11 for a more thorough explanation) so it is advisable to define reasonable bounds for the variables using e04rhc. See Section 4.1 in the E04 Chapter Introduction for more details about the NAG optimization modelling suite.
The algorithm behaviour and solver strategy can be modified by various optional parameters (see Section 12) which can be set by e04zmc and e04zpc at any time between the initialization of the handle by e04rac and a call to the solver. The optional parameters' names specific for this solver start with the prefix MCS (Multi-level Coordinate Search). The default values for these optional parameters are chosen to work well in the general case, but it is recommended that you tune them to your particular problem. In particular, if the objective function is known to be numerically difficult, it could be desirable to define a customized initialization list for the algorithm with the optional parameter MCS Initialization Method. For more details on how to create a custom initialization list, please refer to Section 9.2. Once the solver has finished, options may be modified for the next solve. The solver may be called repeatedly with various initialization lists and/or optional parameters.
The method used by e05kbc is based on MCS, the Multi-level Coordinate Search method described in Huyer and Neumaier (1999), and the algorithm it uses is described in detail in Section 11.

4 References

Huyer W and Neumaier A (1999) Global optimization by multi-level coordinate search Journal of Global Optimization 14 331–355

5 Arguments

1: handle void * Input
On entry: the handle to the problem. It needs to be initialized (e.g., by e04rac) and to hold a problem formulation compatible with e05kbc. It must not be changed between calls to the NAG optimization modelling suite.
2: objfun function, supplied by the user External Function
objfun must calculate the value of the nonlinear objective function f(x) at a specified point x. If there is no nonlinear objective (e.g., e04rec or e04rfc was called to define a linear or quadratic objective function), objfun will never be called by e05kbc and may be NULLFN.
The specification of objfun is:
void  objfun (Integer nvar, const double x[], double *fx, Integer *inform, Nag_Comm *comm)
1: nvar Integer Input
On entry: n, the current number of decision variables x in the model.
2: x[nvar] const double Input
On entry: the vector x of variable values at which the objective function is to be evaluated.
3: fx double * Output
On exit: the value of the objective function at x.
4: inform Integer * Input/Output
On entry: a non-negative value.
On exit: may be used to indicate that the requested objective value could not be computed. Specifically, it can be set to a negative value:
inform<0
The solver will cleanly exit with fail.code= NE_USER_STOP and return the best available point as well as the solve statistics.
5: comm Nag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to objfun.
userdouble *
iuserInteger *
pPointer 
The type Pointer will be void *. Before calling e05kbc you may allocate memory and initialize these pointers with various quantities for use by objfun when called from e05kbc (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).
Note: objfun should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by e05kbc. If your code inadvertently does return any NaNs or infinities, e05kbc is likely to produce unexpected results.
3: monit function, supplied by the user External Function
monit is provided to enable you to monitor the progress of the optimization and, optionally, to terminate the solver early if necessary. It is invoked at the end of every ith step where i is given by the MCS Monitor Frequency (the default is 0, monit is not called). A step is complete when the procedure in which a sub-box is considered for splitting finishes correctly.
monit may be specified as NULLFN.
The specification of monit is:
void  monit (Integer nvar, const double x[], Integer *inform, const double rinfo[], const double stats[], Nag_Comm *comm)
1: nvar Integer Input
On entry: n, the current number of decision variables x in the model.
2: x[nvar] const double Input
On entry: the vector x of decision variables at the current iteration.
3: inform Integer * Input/Output
On entry: a non-negative value.
On exit: may be used to request the solver to stop immediately. Specifically, if inform<0 the solver will terminate immediately with fail.code= NE_USER_STOP; otherwise, the solver will proceed normally.
4: rinfo[100] const double Input
On entry: error measures and various indicators at the end of the current iteration as described in rinfo.
5: stats[100] const double Input
On entry: solver statistics at the end of the current iteration as described in stats.
6: comm Nag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to monit.
userdouble *
iuserInteger *
pPointer 
The type Pointer will be void *. Before calling e05kbc you may allocate memory and initialize these pointers with various quantities for use by monit when called from e05kbc (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).
Note: monit should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by e05kbc. If your code inadvertently does return any NaNs or infinities, e05kbc is likely to produce unexpected results.
4: nvar Integer Input
On entry: n, the current number of decision variables x in the model.
5: x[nvar] double Output
On exit: the final values of the variables, x.
6: rinfo[100] double Output
On exit: error measures and various indicators at the end of the final iteration as given in the table below:
0 Objective function value f(x).
1 Number of sweeps.
299 Reserved for future use.
7: stats[100] double Output
On exit: solver statistics at the end of the final iteration as given in the table below:
0 Number of calls to the objective function.
1 Total time spent in the solver (including time spent evaluating the objective).
2 Total time spent evaluating the objective function.
3 Number of sub-boxes.
4 Number of splits.
5 Cumulative number of splits by initialization list.
6 The current lowest level containing no split boxes.
799 Reserved for future use.
8: comm Nag_Comm *
The NAG communication argument (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).
9: fail NagError * Input/Output
The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).
e05kbc returns with fail.code= NE_NOERROR if the iterates have converged to a point x that satisfies the convergence criteria described in Section 7.

6 Error Indicators and Warnings

NE_ALLOC_FAIL
Dynamic memory allocation failed.
See Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
NE_BAD_PARAM
On entry, argument value had an illegal value.
NE_DIV_COMPLETE
The division procedure completed but your target value could not be reached.
Despite every sub-box being processed MCS Splits Limit times, the target value you provided in MCS Target Objective Value could not be found to the tolerances given in MCS Target Objective Error and MCS Target Objective Safeguard. You could try reducing MCS Splits Limit or the objective tolerances.
NE_HANDLE
The supplied handle does not define a valid handle to the data structure for the NAG optimization modelling suite. It has not been properly initialized or it has been corrupted.
NE_INF_INIT_LIST
A finite initialization list could not be computed internally. Consider reformulating the bounds on the problem, try providing your own initialization list, use the randomization option (MCS Initialization Method=CUSTOM) or vary the value of Infinite Bound Size.
The user-supplied initialization list contained infinite values, as determined by the optional parameter Infinite Bound Size.
NE_INLIST_CLOSE
An error occurred during initialization. It is likely that points from the initialization list are very close together. Try relaxing the bounds on the variables or use a different initialization method.
NE_INT
On entry, user-supplied section list(i,1:numpts[i-1]) contained ndist distinct elements, and ndist<numpts[i-1]: ndist=value, numpts[i-1]=value, i=value.
For more details, please refer to Section 9.2.
On entry, user-supplied section list(i,1:numpts[i-1]) was not in ascending order: numpts[i-1]=value, i=value.
For more details, please refer to Section 9.2.
The dimension of the array ‘MCS List’ is not a multiple of nvar. For more details, please refer to Section 9.2.
NE_INT_2
On entry, user-supplied initpt[i-1]=value, i=value.
Constraint: if x[i-1] is not fixed then initpt[i-1]1, for i=1,2,,nvar.
For more details, please refer to Section 9.2.
On entry, user-supplied initpt[i-1]=value, i=value and sdlist=value.
Constraint: if x[i-1] is not fixed then initpt[i-1] sdlist , for i=1,2,,nvar.
For more details, please refer to Section 9.2.
On entry, user-supplied numpts[i-1]=value, i=value.
Constraint: if x[i-1] is not fixed then numpts[i-1]3, for i=1,2,,nvar.
For more details, please refer to Section 9.2.
On entry, user-supplied numpts[i-1]=value, i=value and sdlist=value.
Constraint: if x[i-1] is not fixed then numpts[i-1]sdlist, for i=1,2,,nvar.
For more details, please refer to Section 9.2.
NE_INTERNAL_ERROR
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
See Section 7.5 in the Introduction to the NAG Library CL Interface for further information.
NE_LINESEARCH_ERROR
An error occurred during linesearching. It is likely that your objective function is badly scaled: try rescaling it. Also, try relaxing the bounds or use a different initialization method. If the problem persists, please contact NAG quoting error code value.
NE_MISSING_CALL
The optional parameter MCS Initialization Method was set to CUSTOM but one of the arrays list, initpt or numpts was not passed correctly to the handle.
For more details, please refer to Section 9.2.
NE_NO_LICENCE
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library CL Interface for further information.
NE_NOT_PARSED
There were n=value variables and the optional parameter MCS Splits Limit smax=value.
Constraint: smax>n+2 .
Use e04zmc to set compatible option values.
NE_NULL_ARGUMENT
The problem requires the objfun values. Please provide a proper objfun function.
NE_PHASE
The problem is already being solved.
NE_REAL_2
On entry, user-supplied list[i][j]=value, i=value, j=value, and bl[i-1]=value.
Constraint: if x[i-1] is not fixed then list[i][j] bl[i-1] , for i=1,2,,nvar and j=1,2,,numpts[i-1].
For more details, please refer to Section 9.2.
On entry, user-supplied list[i][j]=value, i=value, j=value, and bu[i-1]=value.
Constraint: if x[i-1] is not fixed then list[i][j] bu[i-1] , for i=1,2,,nvar and j=1,2,,numpts[i-1].
For more details, please refer to Section 9.2.
NE_REF_MATCH
On entry, nvar=value, expected value=value.
Constraint: nvar must match the current number of variables of the model in the handle.
NE_SETUP_ERROR
This solver does not support the model defined in the handle.
NE_TOO_MANY_FEVALS
The function evaluations limit was exceeded.
Approximately MCS Max Objective Calls function calls have been made without your chosen termination criterion being satisfied.
NE_USER_STOP
User-supplied monitoring function requested termination.
User-supplied objective function requested termination.

7 Accuracy

If fail.code= NE_NOERROR on exit, then the vector returned in the array x is an estimate of the solution x whose function value satisfies your termination criterion: the function value was static for MCS Static Limit sweeps through levels, or
F(x) - objval max( objerr × |objval| ,objsfg) ,  
where objval is the value of the optional parameter MCS Target Objective Value, objerr is the value of the optional parameter MCS Target Objective Error, and objsfg is the value of the optional parameter MCS Target Objective Safeguard.

8 Parallelism and Performance

Background information to multithreading can be found in the Multithreading documentation.
e05kbc is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
e05kbc makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.
Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this function. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

9 Further Comments

9.1 Description of the Printed Output

The solver can print information to give an overview of the problem and the progress of the computation. The output may be sent to two independent file ID which are set by optional parameters Print File and Monitoring File. Optional parameters Print Level, Print Options, Monitoring Level and Print Solution determine the exposed level of detail. This allows, for example, a detailed log file to be generated while the condensed information is displayed on the screen.
By default (Print File=6, Print Level=2), four sections are printed to the standard output: a header, a list of options, an iteration log and a summary.
Header
The header is a message indicating the start of the solver. It should look like:
 -------------------------------------------------
  E05KB, MCS method for bound constrained problems
 -------------------------------------------------
Optional parameters list
If Print Options=YES, a list of the optional parameters and their values is printed. The list shows all options of the solver, each displayed on one line. The line contains the option name, its current value and an indicator for how it was set. The options left at their defaults are noted by ‘d’ and the ones you have set are noted by ‘U’. Note that the output format is compatible with the file format expected by e04zpc. The output looks as follows:
     Mcs Initialization Method     =       Simple Bounds     * d
     Mcs Local Searches            =                  On     * d
     Mcs Local Searches Limit      =                  50     * d
     Mcs Local Searches Tolerance  =         2.22045E-16     * d
     Mcs Max Objective Calls       =                   0     * d
     Mcs Monitor Frequency         =                   0     * d
     Mcs Repeatability             =                 Off     * d
     Mcs Splits Limit              =                   0     * d
     Mcs Static Limit              =                   0     * d
     Mcs Target Objective Error    =         1.02648E-04     * d
     Mcs Target Objective Safeguard=         1.05367E-08     * d
     Mcs Target Objective Value    =        -1.7977E+308     * d
     Mcs Print Frequency           =                   1     * d
Problem statistics
If Print Level2, statistics on the problem are printed, for example:
 Problem Statistics
   No of variables                  4
     free (unconstrained)           1
     bounded                        3
   Objective function       Nonlinear
Iteration log
If Print Level2, the solver will print a summary line for each split. Each line shows the split number, the value of the objective function (obj), the number of sweeps (nsweeps), and the cumulative number of objective function evaluations (nf). The output looks as follows:
  ----------------------------------------------
   Splits |    obj        nsweeps    |    nf   |
  ----------------------------------------------
        1 | -8.00E+00        1       |     8   |
        2 | -9.00E+00        1       |     9   |
        3 | -9.00E+00        1       |    10   |
        4 | -9.00E+00        1       |    11   |
Summary
Once the solver finishes, a summary is produced:
Status: Converged, objective function is static

  Value of the objective                   -9.00000E+00
  Number of objective function evaluations           81
  Number of sweeps                                   10
Note that only the iterations that decrease the objective function are printed in the iteration log, meaning that objective evaluations are likely to happen between the last printed iteration and the convergence. This leads to a small difference between the last line of the iteration log and the final summary in terms of the number of function evaluations.
Optionally, if Stats Time=YES, the timings are printed:
Timings
      Total time spent in the solver            0.056
      Time spent in the objective evaluation    0.012
Additionally, if Print Solution=YES, the solution is printed along with the bounds:
 Primal variables:
   idx   Lower bound       Value       Upper bound
     1   1.00000E+00    1.00000E+00    3.00000E+00
     2  -2.00000E+00   -8.52342E-02    0.00000E+00
     3       -inf       4.09304E-01         inf
     4   1.00000E+00    1.00000E+00    3.00000E+00

9.2 Creating a Custom Initialization List

By default, the initialization list as described in Section 11.1 is computed internally by the solver using one of the methods defined by the optional parameter MCS Initialization Method. It is however possible to customize the initialization method by first setting MCS Initialization Method to CUSTOM and providing the following information to the handle before the solver call through the utility routines e04rxc and e04rwc:
Numpts(nvar): integer array
numpts encodes the number of splitting points in each coordinate direction; e.g., for i=1,...,nvar, numpts(i) is the number of splits intially created in the ith direction. The coordinates of the initial boxes must be provided in the argument list(nvar*sdlist), where sdlist is defined implicitly when list is passed to the problem structure.
To provide the array numpts, the routine e04rwc must be called with the command string cmdstr='MCS number points'.
Constraint:
Initpt(nvar): integer array
initpt designates a point stored in list that you wish e05kbc to consider as an ‘initial point’ for the purposes of the splitting procedure. Call this initial point x0. The coordinates of x0 correspond to a set of indices ji, i=1,...,nvar, such that xi0 is stored in list(i+(ji-1)×nvar). You must set initpt(i)=ji for i=1,...,nvar.
To provide the array initpt, the routine e04rwc must be called with the command string cmdstr='MCS initial points'.
Constraint:
List(nvar×sdlist): real array
list is the ‘initialization list’: whenever a sub-box in the algorithm is split for the first time (either during the initialization procedure or later), for each non-fixed coordinate i the split is done at the values list(i+(j-1)×nvar), j=1,...,numpts(i), as well as at some adaptively chosen intermediate points. For all i, the values list(i+(j-1)×nvar), j=1,...,numpts(i), must be in ascending order with each entry being distinct.
The dimension sdlist is defined implicitly as sdlist=dim(list)nvar when list is passed to the handle.
To provide the array list, the routine e04rxc must be called with the command string cmdstr='MCS list'.
Constraint:

10 Example

This example finds the global minimum of the ‘peaks’ function in two dimensions
F(x,y) = 3 (1-x) 2 exp(- x 2 - (y+1) 2 ) -10 ( x 5 - x 3 - y 5 ) exp(- x 2 - y 2 ) - 1 3 exp(- (x+1) 2 - y 2 )  
on the box [−3,3] × [−3,3] .
The function F has several local minima and one global minimum in the given box. The global minimum is approximately located at (0.23,-1.63) , where the function value is approximately -6.55.

10.1 Program Text

Program Text (e05kbce.c)

10.2 Program Data

None.

10.3 Program Results

Program Results (e05kbce.r)
GnuplotProduced by GNUPLOT 4.6 patchlevel 3 −3 −2 −1 0 1 2 3 −3 −2 −1 0 1 2 3 Example Program The Peaks Function F and Search Boxes The global minimum is denoted by GM, while our start point is labelled with X GM X gnuplot_plot_1 gnuplot_plot_2 gnuplot_plot_3 gnuplot_plot_4 gnuplot_plot_5 gnuplot_plot_6 gnuplot_plot_7 gnuplot_plot_8 gnuplot_plot_9 gnuplot_plot_10 gnuplot_plot_11 gnuplot_plot_12 gnuplot_plot_13 gnuplot_plot_14

11 Algorithmic Details

Here we summarise the main features of the MCS algorithm used in e05kbc, and we introduce some terminology used in the description of the function and its arguments. We assume throughout that we will only do any work in coordinates i in which xi is free to vary. The MCS algorithm is fully described in Huyer and Neumaier (1999).

11.1 Initialization and Sweeps

Each sub-box is determined by a basepoint x and an opposite point y. We denote such a sub-box by B[x,y]. The basepoint is allowed to belong to more than one sub-box, is usually a boundary point, and is often a vertex.
An initialization procedure produces an initial set of sub-boxes. Whenever a sub-box is split along a coordinate i for the first time (in the initialization procedure or later), the splitting is done at three or more user-defined values {xij}j at which the objective function is sampled, and at some adaptively chosen intermediate points. At least four children are generated. More precisely, we assume that we are given
i xi1 < xi2 < < xiLi ui ,  Li 3 ,  for ​ i=1,2,,n  
and a vector p that, for each i, locates within {xij}j the ith coordinate of an initial point x0; that is, if xi0=xij for some j=1,2,,Li, then pi=j. A good guess for the global optimum can be used as x0.
The initialization points and the vectors and p are collectively called the initialization list (and sometimes we will refer to just the initialization points as ‘the initialization list’, whenever this causes no confusion). The initialization data may be input by you, or they can be set to sensible default values by e05kbc: if you provide them yourself, the arrays list(i+(j-1)×nvar) should contain xij, numpts[i-1] should contain Li, and initpt[i-1] should contain pi, for i=1,2,,n and j=1,2,,Li; please refer to Section 9.2 for more information on how to define a custom initialization list. If you wish e05kbc to use one of its preset initialization methods, you could choose one of two simple, three-point methods (see Figure 1). If the list generated by one of these methods contains infinite values, attempts are made to generate a safeguarded list using the function subint(x,y) (which is also used during the splitting procedure, and is described in Section 11.2). If infinite values persist, e05kbc exits with fail.code= NE_INF_INIT_LIST. There is also the option to generate an initialization list with the aid of linesearches (by setting MCS Initialization Method=simple off-bounds). Starting with the absolutely smallest point in the root box, linesearches are made along each coordinate. For each coordinate, the local minimizers found by the linesearches are put into the initialization list. If there were fewer than three minimizers, they are augmented by close-by values. The final preset initialization option (MCS Initialization Method=random) generates a randomized list, so that independent multiple runs may be made if you suspect a global optimum has not been found. Depending on whether you set the optional parameter MCS Repeatability to ON or OFF, the random state is initialized to give a repeatable or non-repeatable sequence. The components of list are then generated, from a uniform distribution on the root box if the box is finite, or else in a safeguarded fashion if any bound is infinite.
Given an initialization list (preset or otherwise), e05kbc evaluates F at x0 and sets the initial estimate of the global minimum, x*, to x0. Then, for i=1,2,,n, the objective function F is evaluated at Li-1 points that agree with x* in all but the ith coordinate. We obtain pairs ( x^ j , f i j ) , for j=1,2,,Li, with: x*=x^j1, say; with, for jj1,
x^kj = { xk* if ​ki; xkj otherwise;  
and with
fij = F ( x^ j ) .  
The point having the smallest function value is renamed x* and the procedure is repeated with the next coordinate.
Once e05kbc has a full set of initialization points and function values, it can generate an initial set of sub-boxes. Recall that the root box is B[x,y]=[,u], having basepoint x=x0. The opposite point y is a corner of [,u] farthest away from x, in some sense. The point x need not be a vertex of [,u], and y is entitled to have infinite coordinates. We loop over each coordinate i, splitting the current box along coordinate i into 2Li-2, 2Li-1 or 2Li sub-intervals with exactly one of the x^ij as endpoints, depending on whether two, one or none of the x^ij are on the boundary. Thus, as well as splitting at x^ i j , for j=1,2,,Li, we split at additional points z i j , for j=2,3,,Li. These additional zij are such that
zij = x^ i j-1 + qm ( x^ i j - x^ i j-1 ) ,   j=2,,Li ,  
where q is the golden-section ratio (5-1)/2, and the exponent m takes the value 1 or 2, chosen so that the sub-box with the smaller function value gets the larger fraction of the interval. Each child sub-box gets as basepoint the point obtained from x* by changing xi* to the xij that is a boundary point of the corresponding ith coordinate interval; this new basepoint, therefore, has function value fij. The opposite point is derived from y by changing yi to the other end of that interval.
e05kbc can now rank the coordinates based on an estimated variability of F. For each i we compute the union of the ranges of the quadratic interpolant through any three consecutive x^ij, taking the difference between the upper and lower bounds obtained as a measure of the variability of F in coordinate i. A vector π is populated in such a way that coordinate i has the πith highest estimated variability. For tiebreaks, when the x* obtained after splitting coordinate i belongs to two sub-boxes, the one that contains the minimizer of the quadratic models is designated the current sub-box for coordinate i+1.
Boxes are assigned levels in the following manner. The root box is given level 1. When a sub-box of level s is split, the child with the smaller fraction of the golden-section split receives level s+2; all other children receive level s+1. The box with the better function value is given the larger fraction of the splitting interval and the smaller level because then it is more likely to be split again more quickly. We see that after the initialization procedure the first level is empty and the non-split boxes have levels 2,,nr+2, so it is meaningful to choose smax much larger than nr. Note that the internal structure of e05kbc demands that smax be at least nr+3.
Examples of initializations in two dimensions are given in Figure 1. In both cases the initial point is x0=(+u)/2; on the left the initialization points are
x1 = ,  x2 = (+u) / 2 ,  x3 = u ,  
while on the right the points are
x1 = (5+u) / 6 ,  x2 = (+u) / 2 ,  x3 = (+5u) / 6 .  
In Figure 1, basepoints and levels after initialization are displayed. Note that these initialization lists correspond to MCS Initialization Method=simple bounds and MCS Initialization Method=simple off-bounds, respectively.
Examples of the initialization procedure
Figure 1: Examples of the initialization procedure
After initialization, a series of sweeps through levels is begun. A sweep is defined by three steps:
  1. (i)scan the list of non-split sub-boxes. Fill a record list b according to bs=0 if there is no box at level s, and with bs pointing to a sub-box with the lowest function value among all sub-boxes with level s otherwise, for 0<s<smax;
  2. (ii)the sub-box with label bs is a candidate for splitting. If the sub-box is not to be split, according to the rules described in Section 11.2, increase its level by 1 and update bs+1 if necessary. If the sub-box is split, mark it so, insert its children into the list of sub-boxes, and update b if any child with level s yields a strict improvement of F over those sub-boxes at level s;
  3. (iii)increment s by 1. If s=smax then display the monitoring information and start a new sweep; else if bs=0 then repeat this step; else display monitoring information and go to the previous step.
Clearly, each sweep ends after at most smax-1 visits of the third step.

11.2 Splitting

Each sub-box is stored by e05kbc as a set of information about the history of the sub-box: the label of its parent, a label identifying which child of the parent it is, etc. Whenever a sub-box B[x,y] of level s<smax is a candidate for splitting, as described in Section 11.1, we recover x, y, and the number, nj, of times coordinate j has been split in the history of B. Sub-box B could be split in one of two ways.
  1. (i)Splitting by rank
    If s > 2nr (min(nj+1)) , the box is always split. The splitting index is set to a coordinate i such that ni=min(nj).
  2. (ii)Splitting by expected gain
    If s 2nr (min(nj+1)) , the sub-box could be split along a coordinate where a maximal gain in function value is expected. This gain is estimated according to a local separable quadratic model obtained by fitting to 2nr+1 function values. If the expected gain is too small the sub-box is not split at all, and its level is increased by 1.
Eventually, a sub-box that is not eligible for splitting by expected gain will reach level 2nr (min(nj+1)) +1 and then be split by rank, as long as smax is large enough. As smax, the rule for splitting by rank ensures that each coordinate is split arbitrarily often.
Before describing the details of each splitting method, we introduce the procedure for correctly handling splitting at adaptive points and for dealing with unbounded intervals. Suppose we want to split the ith coordinate interval {xi,yi}, where we define {xi,yi}=[min(xi,yi),max(xi,yi)], for xiR and yiR¯, and where x is the basepoint of the sub-box being considered. The descendants of the sub-box should shrink sufficiently fast, so we should not split too close to xi. Moreover, if yi is large we want the new splitting value to not be too large, so we force it to belong to some smaller interval {ξ,ξ}, determined by
ξ = subint (xi,yi) ,  ξ = xi + (ξ-xi) / 10 ,  
where the function subint is defined by
subint (x,y) = { sign(y) if ​ 1000|x|<1 ​ and ​ |y|>1000 ; 10sign(y)|x| if ​ 1000|x|1 ​ and ​ |y|>1000|x| ; y otherwise.  

11.2.1 Splitting by rank

Consider a sub-box B with level s > 2nr (min(nj+1)) . Although the sub-box has reached a high level, there is at least one coordinate along which it has not been split very often. Among the i such that ni = min(nj) for B, select the splitting index to be the coordinate with the lowest πi (and hence highest variability rank). ‘Splitting by rank’ refers to the ranking of the coordinates by ni and πi.
If ni=0, so that B has never been split along coordinate i, the splitting is done according to the initialization list and the adaptively chosen golden-section split points, as described in Section 11.1. Also as covered there, new basepoints and opposite points are generated. The children having the smaller fraction of the golden-section split (that is, those with larger function values) are given level min{s+2,smax}. All other children are given level s+1.
Otherwise, B ranges between xi and yi in the ith coordinate direction. The splitting value is selected to be zi=xi+2(subint(xi,yi)-xi)/3; we are not attempting to split based on a large reduction in function value, merely in order to reduce the size of a large interval, so zi may not be optimal. Sub-box B is split at zi and the golden-section split point, producing three parts and requiring only one additional function evaluation, at the point x obtained from x by changing the ith coordinate to zi. The child with the smaller fraction of the golden-section split is given level min{s+2,smax}, while the other two parts are given level s+1. Basepoints are assigned as follows: the basepoint of the first child is taken to be x, and the basepoint of the second and third children is the point x. Opposite points are obtained by changing yi to the other end of the ith coordinate-interval of the corresponding child.

11.2.2 Splitting by expected gain

When a sub-box B has level s 2nr (min(nj+1)) , we compute the optimal splitting index and splitting value from a local separable quadratic used as a simple local approximation of the objective function. To fit this curve, for each coordinate we need two additional points and their function values. Such data may be recoverable from the history of B: whenever the ith coordinate was split in the history of B, we obtained values that can be used for the current quadratic interpolation in coordinate i.
We loop over i; for each coordinate we pursue the history of B back to the root box, and we take the first two points and function values we find, since these are expected to be closest to the current basepoint x. If the current coordinate has not yet been split we use the initialization list. Then we generate a local separable model e(ξ) for F(ξ) by interpolation at x and the 2nr additional points just collected:
e(ξ) = F(x) + i=1 n ei (ξi) .  
We define the expected gain e^i in function value when we evaluate at a new point obtained by changing coordinate i in the basepoint, for each i, based on two cases:
  1. (i)ni=0. We compute the expected gain as
    e^i = min 1j Li {fij} - f i pi .  
    Again, we split according to the initialization list, with the new basepoints and opposite points being as before.
  2. (ii)ni>0. Now, the ith component of our sub-box ranges from xi to yi. Using the quadratic partial correction function
    ei (ξi) = αi (ξi-xi) + βi (ξi-xi) 2  
    we can approximate the maximal gain expected when changing xi only. We will choose the splitting value from {ξ,ξ}. We compute
    e^i = min ξi {ξ,ξ} ei (ξi)  
    and call zi the minimizer in {ξ,ξ}.
    If the expected best function value fexp satisfies
    fexp = F(x) + min 1in e^i < fbest , (1)
    where fbest is the current best function value (including those function values obtained by local optimization), we expect the sub-box to contain a better point and so we split it, using as splitting index the component with minimal e^i. Equation (1) prevents wasting function calls by avoiding splitting sub-boxes whose basepoints have bad function values. These sub-boxes will eventually be split by rank anyway.
    We now have a splitting index and a splitting value zi. The sub-box is split at zi as long as ziyi, and at the golden-section split point; two or three children are produced. The larger fraction of the golden-section split receives level s+1, while the smaller fraction receives level min{s+2,smax}. If it is the case that ziyi and the third child is larger than the smaller of the two children from the golden-section split, the third child receives level s+1. Otherwise it is given the level min{s+2,smax}. The basepoint of the first child is set to x, and the basepoint of the second (and third if it exists) is obtained by changing the ith coordinate of x to zi. The opposite points are again derived by changing yi to the other end of the ith coordinate interval of B.
    If equation (1) does not hold, we expect no improvement. We do not split, and we increase the level of B by 1.

11.3 Local Search

The local optimization algorithm used by e05kbc uses linesearches along directions that are determined by minimizing quadratic models, all subject to bound constraints. Triples of vectors are computed using coordinate searches based on linesearches. These triples are used in triple search procedures to build local quadratic models for F. A trust region-type approach to minimize these models is then carried out, and more information about the coordinate search and the triple search can be found in Huyer and Neumaier (1999).
The local search starts by looking for better points without being too local, by making a triple search using points found by a coordinate search. This yields a new point and function value, an approximation of the gradient of the objective, and an approximation of the Hessian of the objective. Then the quadratic model for F is minimized over a small box, with the solution to that minimization problem then being used as a linesearch direction to minimize the objective. A measure r is computed to quantify the predictive quality of the quadratic model.
The third stage is the checking of termination criteria. The local search will stop if more than loclim visits to this part of the local search have occurred, where loclim is the value of the optional parameter MCS Local Searches Limit. If that is not the case, it will stop if the limit on function calls has been exceeded (see the description of the optional parameter MCS Max Objective Calls). The final criterion checks if no improvement can be made to the function value, or whether the approximated gradient g is small, in the sense that
|g|T max(|x|,| x old |) < loctol (f0-f) .  
The vector xold is the best point at the start of the current loop in this iterative local-search procedure, the constant loctol is the value of the optional parameter MCS Local Searches Tolerance, f is the objective value at x, and f0 is the smallest function value found by the initialization procedure.
Next, e05kbc attempts to move away from the boundary, if any components of the current point lie there, using linesearches along the offending coordinates. Local searches are terminated if no improvement could be made.
The fifth stage carries out another triple search, but this time it does not use points from a coordinate search, rather points lying within the trust region box are taken.
The final stage modifies the trust region box to be bigger or smaller, depending on the quality of the quadratic model, minimizes the new quadratic model on that box, and does a linesearch in the direction of the minimizer. The value of r is updated using the new data, and then we go back to the third stage (checking of termination criteria).
The Hessians of the quadratic models generated by the local search may not be positive definite, so e05kbc uses a general nonlinear optimizer to minimize the models.

12 Optional Parameters

Several optional parameters in e05kbc define choices in the problem specification or the algorithm logic. In order to reduce the number of formal arguments of e05kbc these optional parameters have associated default values that are appropriate for most problems. Therefore, you need only specify those optional parameters whose values are to be different from their default values.
The remainder of this section can be skipped if you wish to use the default values for all optional parameters.
The optional parameters can be changed by calling e04zmc anytime between the initialization of the handle and the call to the solver. Modification of the optional parameters during intermediate monitoring stops is not allowed. Once the solver finishes, the optional parameters can be altered again for the next solve.
The option values may be retrieved by e04znc.
The following is a list of the optional parameters available. A full description of each optional parameter is provided in Section 12.1.

12.1 Description of the Optional Parameters

For each option, we give a summary line, a description of the optional parameter and details of constraints.
The summary line contains:
All options accept the value DEFAULT to return single options to their default states.
Keywords and character values are case and white space insensitive.
Defaults
This special keyword may be used to reset all optional parameters to their default values. Any value given with this keyword will be ignored.
MCS Initialization MethodaDefault =SIMPLE BOUNDS
The solver provides several methods to produce the initial set of sub-boxes. When MCS Initialization Method=SIMPLE BOUNDS, SIMPLE OFF-BOUNDS, LINESEARCH or RANDOM, e05kbc will generate the sub-boxes internally. Please refer to Section 11.1 for more details about the differences between the automatic methods.
It is also possible to create a custom initialization list by setting MCS Initialization Method=CUSTOM. Section 9.2 describes how to provide the custom initialization list to the solver.
Constraint: MCS Initialization Method=SIMPLE BOUNDS, SIMPLE OFF-BOUNDS, LINESEARCH, RANDOM or CUSTOM
MCS Max Objective CallsiDefault =100nr2
This puts an approximate limit on the number of function calls allowed. The total number of calls made is checked at the top of an internal iteration loop, so it is possible that a few calls more than MCS Max Objective Calls may be made.
Constraint: MCS Max Objective Calls1
MCS Monitor FrequencyiDefault =0
This parameter specifies the frequency on which to call the monitor function monit. If zero, the monitor function will not be called.
Constraint: MCS Monitor Frequency0.
MCS Print FrequencyiDefault =1
This parameter specifies the frequency with which to print information regarding each sweep to Print File and/or Monitoring File. By default, it will print information of every sweep.
Constraint: MCS Print Frequency1.
MCS Local SearchesaDefault =ON
If you want to try to accelerate convergence of e05kbc by starting local searches from candidate minima, you will require MCS Local Searches to be ON.
Constraint: MCS Local Searches=ON or OFF
MCS Local Searches LimitiDefault =50
This defines the maximal number of iterations to be used in the trust region loop of the local-search procedure.
Constraint: MCS Local Searches Limit>0
MCS Local Searches TolerancerDefault =2ε
The value of MCS Local Searches Tolerance is the multiplier used during local searches as a stopping criterion for when the approximated gradient is small, in the sense described in Section 11.3.
Constraint: MCS Local Searches Tolerance2ε
MCS RepeatabilityaDefault =OFF
For use with random initialization lists (MCS Initialization Method=random). When set to ON, The initialization list will be consistent for every call of e05kbc.
Constraint: MCS Repeatability=ON or OFF
MCS Splits LimitiDefault =d(nr+2)/3
Along with the initialization list, this defines a limit on the number of times the root box will be split along any single coordinate direction. If MCS Local Searches is OFF you may find the default value to be too small.
Constraint: MCS Splits Limit>nr+2
MCS Static LimitiDefault =3nr
As the default termination criterion, computation stops when the best function value is static for MCS Static Limit sweeps through levels. This parameter is ignored if you have specified a target value to reach in MCS Target Objective Value.
Constraint: MCS Static Limit>0
MCS Target Objective ErrorrDefault =ε14
If you have given a target objective value to reach in MCS Target Objective Value, this optional parameter sets your desired relative error between F(x) and MCS Target Objective Value, as described in Section 7. See also the description of the optional parameter MCS Target Objective Safeguard.
Constraint: MCS Target Objective Error2ε
MCS Target Objective SafeguardrDefault =ε12
If you have given a target objective value to reach in MCS Target Objective Value (the value of the optional parameter MCS Target Objective Value), this optional parameter sets your desired safeguarded termination tolerance, for when MCS Target Objective Value is close to zero.
Constraint: MCS Target Objective Safeguard2ε
MCS Target Objective Valuer
This parameter may be set if you wish e05kbc to use a specific value as the target function value to reach during the optimization. Setting MCS Target Objective Value overrides the default termination criterion determined by the optional parameter MCS Target Objective Value.
Infinite Bound SizerDefault =rmax14
This defines the ‘infinite’ bound bigbnd in the definition of the problem constraints. Any upper bound greater than or equal to bigbnd will be regarded as + (and similarly any lower bound less than or equal to -bigbnd will be regarded as -). Note that a modification of this optional parameter does not influence constraints which have already been defined; only the constraints formulated after the change will be affected.
Constraint: Infinite Bound Size1000.
Monitoring FileiDefault =−1
(See Section 3.1.1 in the Introduction to the NAG Library CL Interface for further information on NAG data types.)
If i0, the Nag_FileID number (as returned from x04acc) for the secondary (monitoring) output. If Monitoring File=−1, no secondary output is provided. The information output to this file ID is controlled by Monitoring Level.
Constraint: Monitoring File−1.
Monitoring LeveliDefault =4
This parameter sets the amount of information detail that will be printed by the solver to the secondary output. The meaning of the levels is the same as with Print Level.
Constraint: 0Monitoring Level5.
Print FileiDefault =Nag_FileID number associated with stdout
(See Section 3.1.1 in the Introduction to the NAG Library CL Interface for further information on NAG data types.)
If i0, the Nag_FileID number (as returned from x04acc, stdout as the default) for the primary output of the solver. If Print File=−1, the primary output is completely turned off independently of other settings. The information output to this unit is controlled by Print Level.
Constraint: Print File−1.
Print LeveliDefault =2
This parameter defines how detailed information should be printed by the solver to the primary and secondary output.
i Output
0 No output from the solver.
1 The Header and Summary.
2, 3, 4, 5 Additionally, the Iteration log.
Constraint: 0Print Level5.
Print OptionsaDefault =YES
If Print Options=YES, a listing of optional parameters will be printed to the primary output and is always printed to the secondary output.
Constraint: Print Options=YES or NO.
Print SolutionaDefault =NO
If Print Solution=YES, the solution will be printed to the primary and secondary output.
Constraint: Print Solution=YES or NO.
Stats TimeaDefault =NO
This parameter turns on timings of various parts of the algorithm to give a better overview of where most of the time is spent. This might be helpful for a choice of different solving approaches. It is possible to choose between CPU and wall clock time. Choice YES is equivalent to WALL CLOCK.
Constraint: Stats Time=YES, NO, CPU or WALL CLOCK.
TaskaDefault =MINIMIZE
This parameter specifies the required direction of the optimization. If Task=FEASIBLE POINT, the objective function (if set) is ignored and the algorithm stops as soon as a feasible point is found with respect to the given tolerance.
Constraint: Task=MINIMIZE, MAXIMIZE or FEASIBLE POINT.