NAG CL Interface
e05jbc (bnd_mcs_solve)
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.
1
Purpose
e05jbc is designed to find the global minimum or maximum of an arbitrary function, subject to simple boundconstraints using a multilevel 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.
The initialization function
e05jac must have been called before calling
e05jbc.
2
Specification
void 
e05jbc (Integer n,
Nag_BoundType bound,
Nag_MCSInitMethod initmethod,
double bl[],
double bu[],
Integer sdlist,
double list[],
Integer numpts[],
Integer initpt[],
void 
(*monit)(Integer n,
Integer ncall,
const double xbest[],
const Integer icount[],
Integer ninit,
const double list[],
const Integer numpts[],
const Integer initpt[],
Integer nbaskt,
const double xbaskt[],
const double boxl[],
const double boxu[],
Integer nstate,
Nag_Comm *comm, Integer *inform),


double x[],
double *obj,
Nag_E05State *state,
Nag_Comm *comm,
NagError *fail) 

The function may be called by the names: e05jbc or nag_glopt_bnd_mcs_solve.
e05jac must be called before calling
e05jbc, or any of the optionsetting or optiongetting
functions:
You
must not alter the number of nonfixed variables in your problem or the contents of
state
between calls of the
functions:
3
Description
e05jbc is designed to solve modestly sized global optimization problems having simple boundconstraints only; it finds the global optimum of a nonlinear function subject to a set of bound constraints on the variables. Without loss of generality, the problem is assumed to be stated in the following form:
where
$F\left(\mathbf{x}\right)$ (the
objective function) is a nonlinear scalar function (assumed to be continuous in a neighbourhood of a global minimum), and the bound vectors are elements of
${\overline{R}}^{n}$, where
$\overline{R}$ denotes the extended reals
$R\cup \left\{\infty ,\infty \right\}$. Relational operators between vectors are interpreted elementwise.
The optional parameter ${\mathbf{Maximize}}$ should be set if you wish to solve maximization, rather than minimization, problems.
If certain bounds are not present, the associated elements of $\mathbf{\ell}$ or $\mathbf{u}$ can be set to special values that will be treated as $\infty $ or $+\infty $. See the description of the optional parameter ${\mathbf{Infinite\; Bound\; Size}}$. Phrases in this document containing terms like ‘unbounded values’ should be understood to be taken relative to this optional parameter.
Fixing variables (that is, setting ${l}_{i}={u}_{i}$ for some $i$) is allowed in e05jbc.
A typical excerpt from a function calling
e05jbc is:
nag_glopt_bnd_mcs_init(n_r, &state, ...);
nag_glopt_bnd_mcs_optset_string(optstr, &state, ...);
nag_glopt_bnd_mcs_solve(n, objfun, ...);
where
e05jdc sets the optional parameter and value specified in
optstr.
The initialization function
e05jac does not need to be called before each invocation of
e05jbc. You should be aware that a call to the initialization function will reset each optional parameter to its default value, and, if you are using repeatable randomized initialization lists (see the description of the argument
initmethod), the random state stored in
state
will be destroyed.
You must supply a function that evaluates $F\left(\mathbf{x}\right)$; derivatives are not required.
The method used by
e05jbc is based on MCS, the Multilevel 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 multilevel coordinate search Journal of Global Optimization 14 331–355
5
Arguments
Note: for convenience the subarray notation
$a\left(i:j,k:l\right)$, as described in
Section 3.1.4 in the Introduction to the NAG Library CL Interface, is used. Using this notation, the term ‘column index’ refers to the index
$j$ in
${\mathbf{LIST}}\left(i,j\right)$, say (see
list for the definition of
LIST).

1:
$\mathbf{n}$ – Integer
Input

On entry: $n$, the number of variables.
Constraint:
${\mathbf{n}}>0$.

2:
$\mathbf{objfun}$ – function, supplied by the user
External Function

objfun must evaluate the objective function
$F\left(\mathbf{x}\right)$ for a specified
$n$vector
$\mathbf{x}$.
The specification of
objfun is:
void 
objfun (Integer n,
const double x[],
double *f,
Integer nstate,
Nag_Comm *comm, Integer *inform)



1:
$\mathbf{n}$ – Integer
Input

On entry: $n$, the number of variables.

2:
$\mathbf{x}\left[{\mathbf{n}}\right]$ – const double
Input

On entry: $\mathbf{x}$, the vector at which the objective function is to be evaluated.

3:
$\mathbf{f}$ – double *
Output

On exit: must be set to the value of the objective function at $\mathbf{x}$.

4:
$\mathbf{nstate}$ – Integer
Input

On entry: if
${\mathbf{nstate}}=1$ then
e05jbc is calling
objfun for the first time. This argument setting allows you to save computation time if certain data must be read or calculated only once.

5:
$\mathbf{comm}$ – Nag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to
objfun.
 user – double *
 iuser – Integer *
 p – Pointer
The type Pointer will be
void *. Before calling
e05jbc you may allocate memory and initialize these pointers with various quantities for use by
objfun when called from
e05jbc (see
Section 3.1.1 in the Introduction to the NAG Library CL Interface).

6:
$\mathbf{inform}$ – Integer *
Output

On exit: must be set to a value describing the action to be taken by the solver on return from
objfun. Specifically, if the value is negative the solution of the current problem will terminate immediately; otherwise, computations will continue.
Note: objfun should not return floatingpoint NaN (Not a Number) or infinity values, since these are not handled by
e05jbc. If your code inadvertently
does return any NaNs or infinities,
e05jbc is likely to produce unexpected results.

3:
$\mathbf{bound}$ – Nag_BoundType
Input

On entry: indicates whether the facility for dealing with bounds of special forms is to be used.
bound must be set to one of the following values.
 ${\mathbf{bound}}=\mathrm{Nag\_Bounds}$
 You will supply $\mathbf{\ell}$ and $\mathbf{u}$ individually.
 ${\mathbf{bound}}=\mathrm{Nag\_NoBounds}$
 There are no bounds on $\mathbf{x}$.
 ${\mathbf{bound}}=\mathrm{Nag\_BoundsZero}$
 There are semiinfinite bounds $0\le \mathbf{x}$.
 ${\mathbf{bound}}=\mathrm{Nag\_BoundsEqual}$
 There are constant bounds $\mathbf{\ell}={\ell}_{1}$ and $\mathbf{u}={u}_{1}$.
Note that it only makes sense to fix any components of $\mathbf{x}$ when ${\mathbf{bound}}=\mathrm{Nag\_Bounds}$.
Constraint:
${\mathbf{bound}}=\mathrm{Nag\_Bounds}$, $\mathrm{Nag\_NoBounds}$, $\mathrm{Nag\_BoundsZero}$ or $\mathrm{Nag\_BoundsEqual}$.

4:
$\mathbf{initmethod}$ – Nag_MCSInitMethod
Input

On entry: selects which initialization method to use.
 ${\mathbf{initmethod}}=\mathrm{Nag\_SimpleBdry}$
 Simple initialization (boundary and midpoint), with
${\mathbf{numpts}}\left[i1\right]=3$, ${\mathbf{initpt}}\left[i1\right]=2$ and
${\mathbf{LIST}}\left(i,1\right)={\mathbf{bl}}\left[i1\right]$,
${\mathbf{LIST}}\left(i,2\right)=\left({\mathbf{bl}}\left[i1\right]+{\mathbf{bu}}\left[i1\right]\right)/2$,
${\mathbf{LIST}}\left(i,3\right)={\mathbf{bu}}\left[i1\right]$,
for $i=1,2,\dots ,{\mathbf{n}}$.
 ${\mathbf{initmethod}}=\mathrm{Nag\_SimpleOffBdry}$
 Simple initialization (offboundary and midpoint), with
${\mathbf{numpts}}\left[i1\right]=3$, ${\mathbf{initpt}}\left[i1\right]=2$ and
${\mathbf{LIST}}\left(i,1\right)=\left(5{\mathbf{bl}}\left[i1\right]+{\mathbf{bu}}\left[i1\right]\right)/6$,
${\mathbf{LIST}}\left(i,2\right)=\left({\mathbf{bl}}\left[i1\right]+{\mathbf{bu}}\left[i1\right]\right)/2$,
${\mathbf{LIST}}\left(i,3\right)=\left({\mathbf{bl}}\left[i1\right]+5{\mathbf{bu}}\left[i1\right]\right)/6$,
for $i=1,2,\dots ,{\mathbf{n}}$.
 ${\mathbf{initmethod}}=\mathrm{Nag\_Linesearch}$
 Initialization using linesearches.
 ${\mathbf{initmethod}}=\mathrm{Nag\_UserSet}$
 You are providing your own initialization list.
 ${\mathbf{initmethod}}=\mathrm{Nag\_Random}$
 Generate a random initialization list.
See
list for the definition of
LIST.
For more information on methods
${\mathbf{initmethod}}=\mathrm{Nag\_Linesearch}$,
$\mathrm{Nag\_UserSet}$ or
$\mathrm{Nag\_Random}$ see
Section 11.1.
If ‘infinite’ values (as determined by the value of the optional parameter ${\mathbf{Infinite\; Bound\; Size}}$) are detected by e05jbc when you are using a simple initialization method (${\mathbf{initmethod}}=\mathrm{Nag\_SimpleBdry}$ or $\mathrm{Nag\_SimpleOffBdry}$), a safeguarded initialization procedure will be attempted, to avoid overflow.
Suggested value:
${\mathbf{initmethod}}=\mathrm{Nag\_SimpleBdry}$.
Constraint:
${\mathbf{initmethod}}=\mathrm{Nag\_SimpleBdry}$, $\mathrm{Nag\_SimpleOffBdry}$, $\mathrm{Nag\_Linesearch}$, $\mathrm{Nag\_UserSet}$ or $\mathrm{Nag\_Random}$.

5:
$\mathbf{bl}\left[{\mathbf{n}}\right]$ – double
Input/Output

6:
$\mathbf{bu}\left[{\mathbf{n}}\right]$ – double
Input/Output

On entry:
${\mathbf{bl}}$ is
$\mathbf{\ell}$, the array of lower bounds.
${\mathbf{bu}}$ is
$\mathbf{u}$, the array of upper bounds.
If ${\mathbf{bound}}=\mathrm{Nag\_Bounds}$, you must set
${\mathbf{bl}}\left[\mathit{i}1\right]$ to ${\ell}_{\mathit{i}}$ and ${\mathbf{bu}}\left[\mathit{i}1\right]$ to ${u}_{\mathit{i}}$, for $\mathit{i}=1,2,\dots ,{\mathbf{n}}$. If a particular ${x}_{i}$ is to be unbounded below, the corresponding ${\mathbf{bl}}\left[i1\right]$ should be set to $\mathit{infbnd}$, where $\mathit{infbnd}$ is the value of the optional parameter ${\mathbf{Infinite\; Bound\; Size}}$. Similarly, if a particular ${x}_{i}$ is to be unbounded above, the corresponding ${\mathbf{bu}}\left[i1\right]$ should be set to $\mathit{infbnd}$.
If
${\mathbf{bound}}=\mathrm{Nag\_NoBounds}$ or
$\mathrm{Nag\_BoundsZero}$, arrays
bl and
bu need not be set on input.
If
${\mathbf{bound}}=\mathrm{Nag\_BoundsEqual}$, you must set
${\mathbf{bl}}\left[0\right]$ to
${\ell}_{1}$ and
${\mathbf{bu}}\left[0\right]$ to
${u}_{1}$. The remaining elements of
bl and
bu will then be populated by these initial values.
On exit: unless
${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_INT,
NE_INT_2,
NE_NOT_INIT,
NE_REAL or
NE_REAL_2 on exit,
bl and
bu are the actual arrays of bounds used by
e05jbc.
Constraints:
 if ${\mathbf{bound}}=\mathrm{Nag\_Bounds}$, ${\mathbf{bl}}\left[\mathit{i}1\right]\le {\mathbf{bu}}\left[\mathit{i}1\right]$, for $\mathit{i}=1,2,\dots ,{\mathbf{n}}$;
 if ${\mathbf{bound}}=\mathrm{Nag\_BoundsEqual}$, ${\mathbf{bl}}\left[0\right]<{\mathbf{bu}}\left[0\right]$.

7:
$\mathbf{sdlist}$ – Integer
Input

On entry:
must be set to, at least, the maximum over
$i$ of the number of points in coordinate
$i$ at which to split according to the initialization list
list; that is,
${\mathbf{sdlist}}\ge {\displaystyle \underset{i}{\mathrm{max}}}\phantom{\rule{0.25em}{0ex}}{\mathbf{numpts}}\left[i1\right]$.
Internally,
e05jbc uses
list to determine sets of points along each coordinate direction to which it fits quadratic interpolants. Since fitting a quadratic requires at least three distinct points, this puts a lower bound on
sdlist. Furthermore, in the case of initialization by linesearches (
${\mathbf{initmethod}}=\mathrm{Nag\_Linesearch}$) internal storage considerations require that
sdlist be at least
$192$.
Constraints:
 if ${\mathbf{initmethod}}\ne \mathrm{Nag\_Linesearch}$, ${\mathbf{sdlist}}\ge 3$;
 if ${\mathbf{initmethod}}=\mathrm{Nag\_Linesearch}$, ${\mathbf{sdlist}}\ge 192$;
 if ${\mathbf{initmethod}}=\mathrm{Nag\_UserSet}$, ${\mathbf{sdlist}}\ge {\displaystyle \underset{\mathit{i}}{\mathrm{max}}}\phantom{\rule{0.25em}{0ex}}\left\{{\mathbf{numpts}}\left[\mathit{i}\right]\right\}$.

8:
$\mathbf{list}\left[{\mathbf{n}}\times {\mathbf{sdlist}}\right]$ – double
Input/Output

Note: where ${\mathbf{LIST}}\left(i,j\right)$ appears in this document, it refers to the array element
${\mathbf{list}}\left[\left(i1\right)\times {\mathbf{sdlist}}+j1\right]$.
for convenience the subarray notation
${\mathbf{list}}\left(i:j,k:l\right)$, as described in
Section 3.1.4 in the Introduction to the NAG Library CL Interface, is used. Using this notation, the term ‘column index’ refers to the index
$j$ in
${\mathbf{LIST}}\left(i,j\right)$, say.
On entry: this argument need not be set on entry if you wish to use one of the preset initialization methods (
${\mathbf{initmethod}}\ne \mathrm{Nag\_UserSet}$).
list is the ‘initialization list’: whenever a subbox in the algorithm is split for the first time (either during the
initialization procedure or later), for each nonfixed coordinate
$i$ the split is done at the values
${\mathbf{LIST}}\left(i,1:{\mathbf{numpts}}\left[i1\right]\right)$, as well as at some adaptively chosen intermediate points. The array sections
${\mathbf{LIST}}\left(\mathit{i},1:{\mathbf{numpts}}\left[\mathit{i}1\right]\right)$, for
$\mathit{i}=1,2,\dots ,{\mathbf{n}}$, must be in ascending order with each entry being distinct. In this context, ‘distinct’ should be taken to mean relative to the saferange parameter (see
X02AMC).
On exit: unless
${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_ALLOC_FAIL,
NE_INT,
NE_INT_2,
NE_NOT_INIT,
NE_REAL or
NE_REAL_2 on exit, the actual initialization data used by
e05jbc. If you wish to monitor the contents of
list you are advised to do so solely through
monit, not through the output value here.
Constraints:
if
${\mathbf{x}}\left[\mathit{i}1\right]$ is not fixed,
 ${\mathbf{LIST}}\left(\mathit{i},1:{\mathbf{numpts}}\left[\mathit{i}1\right]\right)$ is in ascending order with each entry being distinct, for $\mathit{i}=1,2,\dots ,{\mathbf{n}}$;
 ${\mathbf{bl}}\left[\mathit{i}1\right]\le {\mathbf{LIST}}\left(\mathit{i},\mathit{j}\right)\le {\mathbf{bu}}\left[\mathit{i}1\right]$, for $\mathit{i}=1,2,\dots ,{\mathbf{n}}$ and $\mathit{j}=1,2,\dots ,{\mathbf{numpts}}\left[\mathit{i}1\right]$.

9:
$\mathbf{numpts}\left[{\mathbf{n}}\right]$ – Integer
Input/Output

On entry: this argument need not be set on entry if you wish to use one of the preset initialization methods (
${\mathbf{initmethod}}\ne \mathrm{Nag\_UserSet}$).
numpts encodes the number of splitting points in each nonfixed dimension.
On exit: unless
${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_ALLOC_FAIL,
NE_INT,
NE_INT_2,
NE_NOT_INIT,
NE_REAL or
NE_REAL_2 on exit, the actual initialization data used by
e05jbc.
Constraints:
 if ${\mathbf{x}}\left[\mathit{i}1\right]$ is not fixed, ${\mathbf{numpts}}\left[\mathit{i}1\right]\le {\mathbf{sdlist}}$;
 ${\mathbf{numpts}}\left[\mathit{i}1\right]\ge 3$, for $\mathit{i}=1,2,\dots ,{\mathbf{n}}$.

10:
$\mathbf{initpt}\left[{\mathbf{n}}\right]$ – Integer
Input/Output

On entry: this argument need not be set on entry if you wish to use one of the preset initialization methods (
${\mathbf{initmethod}}\ne \mathrm{Nag\_UserSet}$).
You must designate a point stored in
list that you wish
e05jbc to consider as an ‘initial point’ for the purposes of the splitting procedure. Call this initial point
${\mathbf{x}}^{*}$. The coordinates of
${\mathbf{x}}^{*}$ correspond to a set of indices
${J}_{\mathit{i}}$, for
$\mathit{i}=1,2,\dots ,n$, such that
${\mathbf{x}}_{\mathit{i}}^{*}$ is stored in
${\mathbf{LIST}}\left(\mathit{i},{J}_{\mathit{i}}\right)$, for
$\mathit{i}=1,2,\dots ,n$. You must set
${\mathbf{initpt}}\left[\mathit{i}1\right]={J}_{\mathit{i}}$, for
$\mathit{i}=1,2,\dots ,n$.
On exit: unless
${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_ALLOC_FAIL,
NE_INT,
NE_INT_2,
NE_NOT_INIT,
NE_REAL or
NE_REAL_2 on exit, the actual initialization data used by
e05jbc.
Constraint:
if ${\mathbf{x}}\left[\mathit{i}1\right]$ is not fixed,
$1\le {\mathbf{initpt}}\left[\mathit{i}1\right]\le {\mathbf{sdlist}}$, for $\mathit{i}=1,2,\dots ,{\mathbf{n}}$.

11:
$\mathbf{monit}$ – function, supplied by the user
External Function

monit may be used to monitor the optimization process. It is invoked upon every successful completion of the procedure in which a subbox is considered for splitting. It will also be called just before
e05jbc exits if that splitting procedure was not successful.
If no monitoring is required,
monit may be
specified as
NULLFN.
The specification of
monit is:
void 
monit (Integer n,
Integer ncall,
const double xbest[],
const Integer icount[],
Integer ninit,
const double list[],
const Integer numpts[],
const Integer initpt[],
Integer nbaskt,
const double xbaskt[],
const double boxl[],
const double boxu[],
Integer nstate,
Nag_Comm *comm, Integer *inform)



1:
$\mathbf{n}$ – Integer
Input

On entry: $n$, the number of variables.

2:
$\mathbf{ncall}$ – Integer
Input

On entry: the cumulative number of calls to
objfun.

3:
$\mathbf{xbest}\left[{\mathbf{n}}\right]$ – const double
Input

On entry: the current best point.

4:
$\mathbf{icount}\left[6\right]$ – const Integer
Input

On entry: an array of counters.
 ${\mathbf{icount}}\left[0\right]$
 $\mathit{nboxes}$, the current number of subboxes.
 ${\mathbf{icount}}\left[1\right]$
 $\mathit{ncloc}$, the cumulative number of calls to objfun made in local searches.
 ${\mathbf{icount}}\left[2\right]$
 $\mathit{nloc}$, the cumulative number of points used as start points for local searches.
 ${\mathbf{icount}}\left[3\right]$
 $\mathit{nsweep}$, the cumulative number of sweeps through levels.
 ${\mathbf{icount}}\left[4\right]$
 $\mathit{m}$, the cumulative number of splits by initialization list.
 ${\mathbf{icount}}\left[5\right]$
 $\mathit{s}$, the current lowest level containing nonsplit boxes.

5:
$\mathbf{ninit}$ – Integer
Input

On entry: the maximum over
$i$ of the number of points in coordinate
$i$ at which to split according to the initialization list
list. See also the description of the argument
numpts.

6:
$\mathbf{list}\left[{\mathbf{n}}\times {\mathbf{ninit}}\right]$ – const double
Input

On entry: the initialization list.

7:
$\mathbf{numpts}\left[{\mathbf{n}}\right]$ – const Integer
Input

On entry: the number of points in each coordinate at which to split according to the initialization list
list.

8:
$\mathbf{initpt}\left[{\mathbf{n}}\right]$ – const Integer
Input

On entry: a pointer to the ‘initial point’ in
list. Element
${\mathbf{initpt}}\left[i1\right]$ is the column index in
LIST of the
$i$th coordinate of the initial point.

9:
$\mathbf{nbaskt}$ – Integer
Input

On entry: the number of points in the ‘shopping basket’
xbaskt.

10:
$\mathbf{xbaskt}\left[{\mathbf{n}}\times {\mathbf{nbaskt}}\right]$ – const double
Input

Note: the $j$th candidate minimum has its $i$th coordinate stored in
${\mathbf{xbaskt}}\left[\left(\mathit{j}1\right)\times {\mathbf{nbaskt}}+\mathit{i}1\right]$, for $\mathit{i}=1,2,\dots ,{\mathbf{n}}$ and $\mathit{j}=1,2,\dots ,{\mathbf{nbaskt}}$.
On entry: the ‘shopping basket’ of candidate minima.

11:
$\mathbf{boxl}\left[{\mathbf{n}}\right]$ – const double
Input

On entry: the array of lower bounds of the current search box.

12:
$\mathbf{boxu}\left[{\mathbf{n}}\right]$ – const double
Input

On entry: the array of upper bounds of the current search box.

13:
$\mathbf{nstate}$ – Integer
Input

On entry: is set by
e05jbc to indicate at what stage of the minimization
monit was called.
 ${\mathbf{nstate}}=1$
 This is the first time that monit has been called.
 ${\mathbf{nstate}}=1$
 This is the last time monit will be called.
 ${\mathbf{nstate}}=0$
 This is the first and last time monit will be called.

14:
$\mathbf{comm}$ – Nag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to
monit.
 user – double *
 iuser – Integer *
 p – Pointer
The type Pointer will be
void *. Before calling
e05jbc you may allocate memory and initialize these pointers with various quantities for use by
monit when called from
e05jbc (see
Section 3.1.1 in the Introduction to the NAG Library CL Interface).

15:
$\mathbf{inform}$ – Integer *
Output

On exit: must be set to a value describing the action to be taken by the solver on return from
monit. Specifically, if the value is negative the solution of the current problem will terminate immediately; otherwise, computations will continue.

12:
$\mathbf{x}\left[{\mathbf{n}}\right]$ – double
Output

On exit: if
${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_NOERROR, contains an estimate of the global optimum (see also
Section 7).

13:
$\mathbf{obj}$ – double *
Output

On exit: if
${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_NOERROR, contains the function value at
x.
If you request early termination of
e05jbc in
objfun or
monit, there is no guarantee that the function value at
x equals
obj.

14:
$\mathbf{state}$ – Nag_E05State *
Communication Structure

state contains information required by other functions in this suite. You must not modify it directly in any way.

15:
$\mathbf{comm}$ – Nag_Comm *

The NAG communication argument (see
Section 3.1.1 in the Introduction to the NAG Library CL Interface).

16:
$\mathbf{fail}$ – NagError *
Input/Output

The NAG error argument (see
Section 7 in the Introduction to the NAG Library CL Interface).
e05jbc returns with ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_NOERROR if your termination criterion has been met: either a target value has been found to the required relative error (as determined by the values of the optional parameters ${\mathbf{Target\; Objective\; Value}}$, ${\mathbf{Target\; Objective\; Error}}$ and ${\mathbf{Target\; Objective\; Safeguard}}$), or the best function value was static for the number of sweeps through levels given by the optional parameter ${\mathbf{Static\; Limit}}$. The latter criterion is the default.
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 $\u2329\mathit{\text{value}}\u232a$ had an illegal value.
 NE_DIV_COMPLETE

The division procedure completed but your target value could not be reached.
Despite every subbox being processed ${\mathbf{Splits\; Limit}}$ times, the target value you provided in ${\mathbf{Target\; Objective\; Value}}$ could not be found to the tolerances given in ${\mathbf{Target\; Objective\; Error}}$ and ${\mathbf{Target\; Objective\; Safeguard}}$. You could try reducing ${\mathbf{Splits\; Limit}}$ or the objective tolerances.
 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 (${\mathbf{initmethod}}=\mathrm{Nag\_Random}$) or vary the value of ${\mathbf{Infinite\; Bound\; Size}}$.
The usersupplied initialization list contained infinite values, as determined by the optional parameter ${\mathbf{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, ${\mathbf{initmethod}}=\mathrm{Nag\_Linesearch}$ and ${\mathbf{sdlist}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: if ${\mathbf{initmethod}}=\mathrm{Nag\_Linesearch}$ then ${\mathbf{sdlist}}\ge 192$.
On entry, ${\mathbf{initmethod}}=\u2329\mathit{\text{value}}\u232a$ and ${\mathbf{sdlist}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: if ${\mathbf{initmethod}}\ne \mathrm{Nag\_Linesearch}$ then ${\mathbf{sdlist}}\ge 3$.
On entry, ${\mathbf{n}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{n}}>0$.
On entry, usersupplied section ${\mathbf{LIST}}\left(i,1:{\mathbf{numpts}}\left[i1\right]\right)$ contained $\mathit{ndist}$ distinct elements, and $\mathit{ndist}<{\mathbf{numpts}}\left[i1\right]$: $\mathit{ndist}=\u2329\mathit{\text{value}}\u232a$, ${\mathbf{numpts}}\left[i1\right]=\u2329\mathit{\text{value}}\u232a$, $i=\u2329\mathit{\text{value}}\u232a$.
The number of nonfixed variables ${n}_{r}=0$.
Constraint: ${n}_{r}>0$.
 NE_INT_2

A value of ${\mathbf{Splits\; Limit}}$ ($\mathit{smax}$) smaller than ${n}_{r}+3$ was set: $\mathit{smax}=\u2329\mathit{\text{value}}\u232a$, ${n}_{r}=\u2329\mathit{\text{value}}\u232a$.
On entry, usersupplied ${\mathbf{initpt}}\left[i1\right]=\u2329\mathit{\text{value}}\u232a$, $i=\u2329\mathit{\text{value}}\u232a$.
Constraint: if ${\mathbf{x}}\left[i1\right]$ is not fixed then ${\mathbf{initpt}}\left[\mathit{i}1\right]\ge 1$, for $\mathit{i}=1,2,\dots ,{\mathbf{n}}$.
On entry, usersupplied ${\mathbf{initpt}}\left[i1\right]=\u2329\mathit{\text{value}}\u232a$, $i=\u2329\mathit{\text{value}}\u232a$ and ${\mathbf{sdlist}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: if ${\mathbf{x}}\left[i1\right]$ is not fixed then ${\mathbf{initpt}}\left[\mathit{i}1\right]\le {\mathbf{sdlist}}$, for $\mathit{i}=1,2,\dots ,{\mathbf{n}}$.
On entry, usersupplied ${\mathbf{numpts}}\left[i1\right]=\u2329\mathit{\text{value}}\u232a$, $i=\u2329\mathit{\text{value}}\u232a$.
Constraint: if ${\mathbf{x}}\left[i1\right]$ is not fixed then ${\mathbf{numpts}}\left[\mathit{i}1\right]\ge 3$, for $\mathit{i}=1,2,\dots ,{\mathbf{n}}$.
On entry, usersupplied ${\mathbf{numpts}}\left[i1\right]=\u2329\mathit{\text{value}}\u232a$, $i=\u2329\mathit{\text{value}}\u232a$ and ${\mathbf{sdlist}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: if ${\mathbf{x}}\left[i1\right]$ is not fixed then ${\mathbf{numpts}}\left[\mathit{i}1\right]\le {\mathbf{sdlist}}$, for $\mathit{i}=1,2,\dots ,{\mathbf{n}}$.
On entry, usersupplied section ${\mathbf{LIST}}\left(i,1:{\mathbf{numpts}}\left[i1\right]\right)$ was not in ascending order: ${\mathbf{numpts}}\left[i1\right]=\u2329\mathit{\text{value}}\u232a$, $i=\u2329\mathit{\text{value}}\u232a$.
 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
$\u2329\mathit{\text{value}}\u232a$.
 NE_MONIT_TERMIN

Usersupplied monitoring function requested termination.
 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_INIT

Initialization function
e05jac has not been called.
 NE_OBJFUN_TERMIN

Usersupplied objective function requested termination.
 NE_REAL

On entry, ${\mathbf{bound}}=\mathrm{Nag\_BoundsEqual}$ and ${\mathbf{bl}}\left[0\right]={\mathbf{bu}}\left[0\right]=\u2329\mathit{\text{value}}\u232a$.
Constraint: if ${\mathbf{bound}}=\mathrm{Nag\_BoundsEqual}$ then ${\mathbf{bl}}\left[0\right]<{\mathbf{bu}}\left[0\right]$.
 NE_REAL_2

On entry, ${\mathbf{bound}}=\mathrm{Nag\_Bounds}$ or $\mathrm{Nag\_BoundsEqual}$ and ${\mathbf{bl}}\left[i1\right]=\u2329\mathit{\text{value}}\u232a$, ${\mathbf{bu}}\left[i1\right]=\u2329\mathit{\text{value}}\u232a$ and $i=\u2329\mathit{\text{value}}\u232a$.
Constraint: if ${\mathbf{bound}}=\mathrm{Nag\_Bounds}$ then ${\mathbf{bl}}\left[\mathit{i}1\right]\le {\mathbf{bu}}\left[\mathit{i}1\right]$, for $\mathit{i}=1,2,\dots ,{\mathbf{n}}$; if ${\mathbf{bound}}=\mathrm{Nag\_BoundsEqual}$ then ${\mathbf{bl}}\left[0\right]<{\mathbf{bu}}\left[0\right]$.
On entry, usersupplied ${\mathbf{LIST}}\left(i,j\right)=\u2329\mathit{\text{value}}\u232a$, $i=\u2329\mathit{\text{value}}\u232a$, $j=\u2329\mathit{\text{value}}\u232a$, and ${\mathbf{bl}}\left[i1\right]=\u2329\mathit{\text{value}}\u232a$.
Constraint: if ${\mathbf{x}}\left[i1\right]$ is not fixed then ${\mathbf{LIST}}\left(\mathit{i},\mathit{j}\right)\ge {\mathbf{bl}}\left[\mathit{i}1\right]$, for $\mathit{i}=1,2,\dots ,{\mathbf{n}}$ and $\mathit{j}=1,2,\dots ,{\mathbf{numpts}}\left[\mathit{i}1\right]$.
On entry, usersupplied ${\mathbf{LIST}}\left(i,j\right)=\u2329\mathit{\text{value}}\u232a$, $i=\u2329\mathit{\text{value}}\u232a$, $j=\u2329\mathit{\text{value}}\u232a$, and ${\mathbf{bu}}\left[i1\right]=\u2329\mathit{\text{value}}\u232a$.
Constraint: if ${\mathbf{x}}\left[i1\right]$ is not fixed then ${\mathbf{LIST}}\left(\mathit{i},\mathit{j}\right)\le {\mathbf{bu}}\left[\mathit{i}1\right]$, for $\mathit{i}=1,2,\dots ,{\mathbf{n}}$ and $\mathit{j}=1,2,\dots ,{\mathbf{numpts}}\left[\mathit{i}1\right]$.
 NE_TOO_MANY_FEVALS

The function evaluations limit was exceeded.
Approximately ${\mathbf{Function\; Evaluations\; Limit}}$ function calls have been made without your chosen termination criterion being satisfied.
7
Accuracy
If
${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_NOERROR on exit, then the vector returned in the array
x is an estimate of the solution
$\mathbf{x}$ whose function value satisfies your termination criterion: the function value was static for
${\mathbf{Static\; Limit}}$ sweeps through levels, or
where
$\mathit{objval}$ is the value of the optional parameter
${\mathbf{Target\; Objective\; Value}}$,
$\mathit{objerr}$ is the value of the optional parameter
${\mathbf{Target\; Objective\; Error}}$, and
$\mathit{objsfg}$ is the value of the optional parameter
${\mathbf{Target\; Objective\; Safeguard}}$.
8
Parallelism and Performance
e05jbc is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
e05jbc 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 implementationspecific information.
For each invocation of
e05jbc, local workspace arrays of fixed length are allocated internally. The total size of these arrays amounts to
$13{n}_{r}+\mathit{smax}1$ Integer elements, where
$\mathit{smax}$ is the value of the optional parameter
${\mathbf{Splits\; Limit}}$ and
${n}_{r}$ is the number of nonfixed variables, and
$\left(2+{n}_{r}\right){\mathbf{sdlist}}+2{\mathbf{n}}+22{n}_{r}+3{n}_{r}^{2}+1$ double elements. In addition, if you are using randomized initialization lists (see the description of the argument
initmethod), a further
$21$ Integer elements are allocated internally.
In order to keep track of the regions of the search space that have been visited while looking for a global optimum,
e05jbc internally allocates arrays of increasing sizes depending on the difficulty of the problem. Two of the main factors that govern the amount allocated are the number of subboxes (call this quantity
$\mathit{nboxes}$) and the number of points in the ‘shopping basket’ (the argument
nbaskt on entry to
monit). Safe, pessimistic upper bounds on these two quantities are so large as to be impractical. In fact, the worstcase number of subboxes for even the most simple initialization list (when
${\mathbf{ninit}}=3$ on entry to
monit) grows like
${{n}_{r}}^{{n}_{r}}$. Thus
e05jbc does not attempt to estimate in advance the final values of
$\mathit{nboxes}$ or
nbaskt for a given problem. There are a total of
$5$ Integer arrays and
$4+{n}_{r}+{\mathbf{ninit}}$ double arrays whose lengths depend on
$\mathit{nboxes}$, and there are a total of
$2$ Integer arrays and
$3+{\mathbf{n}}+{n}_{r}$ double arrays whose lengths depend on
nbaskt.
e05jbc makes a fixed initial guess that the maximum number of subboxes required will be
$10000$ and that the maximum number of points in the ‘shopping basket’ will be
$1000$. If ever a greater amount of subboxes or more room in the ‘shopping basket’ is required,
e05jbc performs reallocation, usually doubling the size of the inadequatelysized arrays. Clearly this process requires periods where the original array and its extension exist in memory simultaneously, so that the data within can be copied, which compounds the complexity of
e05jbc's memory usage. It is possible (although not likely) that if your problem is particularly difficult to solve, or of a large size (hundreds of variables), you may run out of memory.
One array that could be dynamically resized by
e05jbc is the ‘shopping basket’ (
xbaskt on entry to
monit). If the initial attempt to allocate
$1000{n}_{r}$ doubles for this array fails,
monit will not be called on exit from
e05jbc.
e05jbc performs better if your problem is wellscaled. It is worth trying (by guesswork perhaps) to rescale the problem if necessary, as sensible scaling will reduce the difficulty of the optimization problem, so that e05jbc will take less computer time.
10
Example
This example finds the global minimum of the ‘peaks’ function in two dimensions
on the box
$\left[3,3\right]\times \left[3,3\right]$.
The function $F$ has several local minima and one global minimum in the given box. The global minimum is approximately located at $\left(0.23,1.63\right)$, where the function value is approximately $6.55$.
We use default values for all the optional parameters, and we instruct
e05jbc to use the simple initialization list corresponding to
${\mathbf{initmethod}}=\mathrm{Nag\_SimpleBdry}$. In particular, this will set for us the initial point
$\left(0,0\right)$
(see
Section 10.3).
10.1
Program Text
10.2
Program Data
10.3
Program Results
Note: the remainder of this document is intended for more advanced users.
Section 11 contains a detailed description of the algorithm. This information may be needed in order to understand
Section 12, which describes the optional parameters that can be set by calls to
e05jcc,
e05jdc,
e05jec,
e05jfc and/or
e05jgc.
11
Algorithmic Details
Here we summarise the main features of the MCS algorithm used in
e05jbc, 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
${x}_{i}$ is free to vary. The MCS algorithm is fully described in
Huyer and Neumaier (1999).
11.1
Initialization and Sweeps
Each subbox is determined by a basepoint $\mathbf{x}$ and an opposite point $\mathbf{y}$. We denote such a subbox by $B\left[\mathbf{x},\mathbf{y}\right]$. The basepoint is allowed to belong to more than one subbox, is usually a boundary point, and is often a vertex.
An
initialization procedure produces an initial set of subboxes. Whenever a subbox is split along a coordinate
$i$ for the first time (in the initialization procedure or later), the splitting is done at three or more userdefined values
${\left\{{x}_{i}^{j}\right\}}_{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
and a vector
$\mathbf{p}$ that, for each
$i$, locates within
${\left\{{x}_{i}^{j}\right\}}_{j}$ the
$i$th coordinate of an
initial point ${\mathbf{x}}^{0}$; that is, if
${x}_{i}^{0}={x}_{i}^{j}$ for some
$j=1,2,\dots ,{L}_{i}$, then
${p}_{i}=j$. A good guess for the global optimum can be used as
${\mathbf{x}}^{0}$.
The initialization points and the vectors
$\mathbf{\ell}$ and
$\mathbf{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
e05jbc: if you provide them yourself,
${\mathbf{LIST}}\left(i,j\right)$ should contain
${x}_{i}^{j}$,
${\mathbf{numpts}}\left[i1\right]$ should contain
${L}_{i}$, and
${\mathbf{initpt}}\left[i1\right]$ should contain
${p}_{\mathit{i}}$, for
$\mathit{i}=1,2,\dots ,n$ and
$\mathit{j}=1,2,\dots ,{L}_{\mathit{i}}$; if you wish
e05jbc to use one of its preset initialization methods, you could choose one of two simple, threepoint 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
$\mathrm{subint}\left(x,y\right)$ (which is also used during the splitting procedure, and is described in
Section 11.2). If infinite values persist,
e05jbc exits with
${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_INF_INIT_LIST. There is also the option to generate an initialization list with the aid of linesearches (by setting
${\mathbf{initmethod}}=\mathrm{Nag\_Linesearch}$). 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 closeby values. The final preset initialization option (
${\mathbf{initmethod}}=\mathrm{Nag\_Random}$) generates a randomized list, so that independent multiple runs may be made if you suspect a global optimum has not been found. Each call to the initialization function
e05jac resets the initialstate vector for the Wichmann–Hill basegenerator that is used. Depending on whether you set the optional parameter
${\mathbf{Repeatability}}$ to
$\mathrm{ON}$ or
$\mathrm{OFF}$, the random state is initialized to give a repeatable or nonrepeatable sequence. Then, a random integer between
$3$ and
sdlist is selected, which is then used to determine the number of points to be generated in each coordinate; that is,
numpts becomes a constant vector, set to this value. 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. The array
${\mathbf{initpt}}$ is set to point to the best point in
list.
Given an initialization list (preset or otherwise),
e05jbc evaluates
$F$ at
${\mathbf{x}}^{0}$, and sets the initial estimate of the global minimum,
${\mathbf{x}}^{*}$, to
${\mathbf{x}}^{0}$. Then, for
$i=1,2,\dots ,n$, the objective function
$F$ is evaluated at
${L}_{i}1$ points that agree with
${\mathbf{x}}^{*}$ in all but the
$i$th coordinate. We obtain pairs
$\left({\hat{\mathbf{x}}}^{\mathit{j}},{f}_{i}^{\mathit{j}}\right)$, for
$\mathit{j}=1,2,\dots ,{L}_{i}$, with:
${\mathbf{x}}^{*}={\hat{\mathbf{x}}}^{{j}_{1}}$, say; with, for
$j\ne {j}_{1}$,
and with
The point having the smallest function value is renamed ${\mathbf{x}}^{*}$ and the procedure is repeated with the next coordinate.
Once
e05jbc has a full set of initialization points and function values, it can generate an initial set of subboxes. Recall that the
root box is
$B\left[\mathbf{x},\mathbf{y}\right]=\left[\mathbf{\ell},\mathbf{u}\right]$, having basepoint
$\mathbf{x}={\mathbf{x}}^{0}$. The opposite point
$\mathbf{y}$ is a corner of
$\left[\mathbf{\ell},\mathbf{u}\right]$ farthest away from
$\mathbf{x}$, in some sense. The point
$\mathbf{x}$ need not be a vertex of
$\left[\mathbf{\ell},\mathbf{u}\right]$, and
$\mathbf{y}$ is entitled to have infinite coordinates. We loop over each coordinate
$i$, splitting the current box along coordinate
$i$ into
$2{L}_{i}2$,
$2{L}_{i}1$ or
$2{L}_{i}$ subintervals with exactly one of the
${\hat{x}}_{i}^{j}$ as endpoints, depending on whether two, one or none of the
${\hat{x}}_{i}^{j}$ are on the boundary. Thus, as well as splitting at
${\hat{x}}_{i}^{\mathit{j}}$, for
$\mathit{j}=1,2,\dots ,{L}_{i}$, we split at additional points
${z}_{i}^{\mathit{j}}$, for
$\mathit{j}=2,3,\dots ,{L}_{i}$. These additional
${z}_{i}^{j}$ are such that
where
$q$ is the goldensection ratio
$\left(\sqrt{5}1\right)/2$, and the exponent
$m$ takes the value
$1$ or
$2$, chosen so that the subbox with the smaller function value gets the larger fraction of the interval. Each child subbox gets as basepoint the point obtained from
${\mathbf{x}}^{*}$ by changing
${x}_{i}^{*}$ to the
${x}_{i}^{j}$ that is a boundary point of the corresponding
$i$th coordinate interval; this new basepoint therefore has function value
${f}_{i}^{j}$. The opposite point is derived from
$\mathbf{y}$ by changing
${y}_{i}$ to the other end of that interval.
e05jbc 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 ${\hat{x}}_{i}^{j}$, taking the difference between the upper and lower bounds obtained as a measure of the variability of $F$ in coordinate $i$. A vector $\mathbf{\pi}$ is populated in such a way that coordinate $i$ has the ${\pi}_{i}$th highest estimated variability. For tiebreaks, when the ${\mathbf{x}}^{*}$ obtained after splitting coordinate $i$ belongs to two subboxes, the one that contains the minimizer of the quadratic models is designated the current subbox for coordinate $i+1$.
Boxes are assigned levels in the following manner. The root box is given level $1$. When a subbox of level $s$ is split, the child with the smaller fraction of the goldensection 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 nonsplit boxes have levels $2,\dots ,{n}_{r}+2$, so it is meaningful to choose ${s}_{\mathrm{max}}$ much larger than ${n}_{r}$. Note that the internal structure of e05jbc demands that ${s}_{\mathrm{max}}$ be at least ${n}_{r}+3$.
Examples of initializations in two dimensions are given in
Figure 1. In both cases the initial point is
${\mathbf{x}}^{0}=\left(\mathbf{\ell}+\mathbf{u}\right)/2$; on the left the initialization points are
while on the right the points are
In
Figure 1, basepoints and levels after initialization are displayed. Note that these initialization lists correspond to
${\mathbf{initmethod}}=\mathrm{Nag\_SimpleBdry}$ and
${\mathbf{initmethod}}=\mathrm{Nag\_SimpleOffBdry}$, respectively.
After initialization, a series of
sweeps through levels is begun. A sweep is defined by three steps:

(i)scan the list of nonsplit subboxes. Fill a record list $\mathbf{b}$ according to ${b}_{s}=0$ if there is no box at level $s$, and with ${b}_{s}$ pointing to a subbox with the lowest function value among all subboxes with level $s$ otherwise, for $0<s<{s}_{\mathrm{max}}$;

(ii)the subbox with label ${b}_{s}$ is a candidate for splitting. If the subbox is not to be split, according to the rules described in Section 11.2, increase its level by $1$ and update ${b}_{s+1}$ if necessary. If the subbox is split, mark it so, insert its children into the list of subboxes, and update $\mathbf{b}$ if any child with level ${s}^{\prime}$ yields a strict improvement of $F$ over those subboxes at level ${s}^{\prime}$;

(iii)increment $s$ by $1$. If $s={s}_{\mathrm{max}}$ then displaying monitoring information and start a new sweep; else if ${b}_{s}=0$ then repeat this step; else display monitoring information and go to the previous step.
Clearly, each sweep ends after at most ${s}_{\mathrm{max}}1$ visits of the third step.
11.2
Splitting
Each subbox is stored by
e05jbc as a set of information about the history of the subbox: the label of its parent, a label identifying which child of the parent it is, etc. Whenever a subbox
$B\left[\mathbf{x},\mathbf{y}\right]$ of level
$s<{s}_{\mathrm{max}}$ is a candidate for splitting, as described in
Section 11.1, we recover
$\mathbf{x}$,
$\mathbf{y}$, and the number,
${n}_{j}$, of times coordinate
$j$ has been split in the history of
$B$. Subbox
$B$ could be split in one of two ways.

(i)Splitting by rank
If $s>2{n}_{r}\left(\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({n}_{j}+1\right)\right)$, the box is always split. The splitting index is set to a coordinate $i$ such that ${n}_{i}=\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({n}_{j}\right)$.

(ii)Splitting by expected gain
If $s\le 2{n}_{r}\left(\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({n}_{j}+1\right)\right)$, the subbox 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 $2{n}_{r}+1$ function values. If the expected gain is too small the subbox is not split at all, and its level is increased by $1$.
Eventually, a subbox that is not eligible for splitting by expected gain will reach level $2{n}_{r}\left(\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({n}_{j}+1\right)\right)+1$ and then be split by rank, as long as ${s}_{\mathrm{max}}$ is large enough. As ${s}_{\mathrm{max}}\to \infty $, 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
$i$th coordinate interval
$\u25af\left\{{x}_{i},{y}_{i}\right\}$, where we define
$\u25af\left\{{x}_{i},{y}_{i}\right\}=\left[\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({x}_{i},{y}_{i}\right),\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left({x}_{i},{y}_{i}\right)\right]$, for
${x}_{i}\in R$ and
${y}_{i}\in \overline{R}$, and where
$\mathbf{x}$ is the basepoint of the subbox being considered. The descendants of the subbox should shrink sufficiently fast, so we should not split too close to
${x}_{i}$. Moreover, if
${y}_{i}$ is large we want the new
splitting value to
not be too large, so we force it to belong to some smaller interval
$\u25af\left\{{\xi}^{\prime},{\xi}^{\prime \prime}\right\}$, determined by
where the function
$\mathrm{subint}$ is defined by
11.2.1
Splitting by rank
Consider a subbox $B$ with level $s>2{n}_{r}\left(\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({n}_{j}+1\right)\right)$. Although the subbox 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 ${n}_{i}=\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({n}_{j}\right)$ for $B$, select the splitting index to be the coordinate with the lowest ${\pi}_{i}$ (and hence highest variability rank). ‘Splitting by rank’ refers to the ranking of the coordinates by ${n}_{i}$ and ${\pi}_{i}$.
If
${n}_{i}=0$, so that
$B$ has never been split along coordinate
$i$, the splitting is done according to the initialization list and the adaptively chosen goldensection 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 goldensection split (that is, those with larger function values) are given level
$\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left\{s+2,{s}_{\mathrm{max}}\right\}$. All other children are given level
$s+1$.
Otherwise, $B$ ranges between ${x}_{i}$ and ${y}_{i}$ in the $i$th coordinate direction. The splitting value is selected to be ${z}_{i}={x}_{i}+2\left(\mathrm{subint}\left({x}_{i},{y}_{i}\right){x}_{i}\right)/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 ${z}_{i}$ may not be optimal. Subbox $B$ is split at ${z}_{i}$ and the goldensection split point, producing three parts and requiring only one additional function evaluation, at the point ${\mathbf{x}}^{\prime}$ obtained from $\mathbf{x}$ by changing the $i$th coordinate to ${z}_{i}$. The child with the smaller fraction of the goldensection split is given level $\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left\{s+2,{s}_{\mathrm{max}}\right\}$, 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 $\mathbf{x}$, and the basepoint of the second and third children is the point ${\mathbf{x}}^{\prime}$. Opposite points are obtained by changing ${y}_{i}$ to the other end of the $i$th coordinateinterval of the corresponding child.
11.2.2
Splitting by expected gain
When a subbox $B$ has level $s\le 2{n}_{r}\left(\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({n}_{j}+1\right)\right)$, 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 $i$th 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
$\mathbf{x}$. If the current coordinate has not yet been split we use the initialization list. Then we generate a local separable model
$e\left(\mathbf{\xi}\right)$ for
$F\left(\mathbf{\xi}\right)$ by interpolation at
$\mathbf{x}$ and the
$2{n}_{r}$ additional points just collected:
We define the
expected gain ${\hat{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:

(i)${n}_{i}=0$. We compute the expected gain as
Again, we split according to the initialization list, with the new basepoints and opposite points being as before.

(ii)${n}_{i}>0$. Now, the $i$th component of our subbox ranges from ${x}_{i}$ to ${y}_{i}$. Using the quadratic partial correction function
we can approximate the maximal gain expected when changing ${x}_{i}$ only. We will choose the splitting value from $\u25af\left\{{\xi}^{\prime},{\xi}^{\prime \prime}\right\}$. We compute
and call ${z}_{i}$ the minimizer in $\u25af\left\{{\xi}^{\prime},{\xi}^{\prime \prime}\right\}$.
If the expected best function value
${f}_{\mathrm{exp}}$ satisfies
where
${f}_{\mathrm{best}}$ is the current best function value (including those function values obtained by local optimization), we expect the subbox to contain a better point and so we split it, using as splitting index the component with minimal
${\hat{e}}_{i}$. Equation
(1) prevents wasting function calls by avoiding splitting subboxes whose basepoints have bad function values. These subboxes will eventually be split by rank anyway.
We now have a splitting index and a splitting value ${z}_{i}$. The subbox is split at ${z}_{i}$ as long as ${z}_{i}\ne {y}_{i}$, and at the goldensection split point; two or three children are produced. The larger fraction of the goldensection split receives level $s+1$, while the smaller fraction receives level $\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left\{s+2,{s}_{\mathrm{max}}\right\}$. If it is the case that ${z}_{i}\ne {y}_{i}$ and the third child is larger than the smaller of the two children from the goldensection split, the third child receives level $s+1$. Otherwise it is given the level $\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left\{s+2,{s}_{\mathrm{max}}\right\}$. The basepoint of the first child is set to $\mathbf{x}$, and the basepoint of the second (and third if it exists) is obtained by changing the $i$th coordinate of $\mathbf{x}$ to ${z}_{i}$. The opposite points are again derived by changing ${y}_{i}$ to the other end of the $i$th 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
e05jbc 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 regiontype 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
$\mathit{loclim}$ visits to this part of the local search have occurred, where
$\mathit{loclim}$ is the value of the optional parameter
${\mathbf{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
${\mathbf{Function\; Evaluations\; Limit}}$). The final criterion checks if no improvement can be made to the function value, or whether the approximated gradient
$\mathbf{g}$ is small, in the sense that
The vector ${\mathbf{x}}_{\mathrm{old}}$ is the best point at the start of the current loop in this iterative localsearch procedure, the constant $\mathit{loctol}$ is the value of the optional parameter ${\mathbf{Local\; Searches\; Tolerance}}$, $f$ is the objective value at $\mathbf{x}$, and ${f}_{0}$ is the smallest function value found by the initialization procedure.
Next, e05jbc 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
e05jbc uses the general nonlinear optimizer
e04vhc to minimize the models.
12
Optional Parameters
Several optional parameters in e05jbc define choices in the problem specification or the algorithm logic. In order to reduce the number of formal arguments of e05jbc 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 following is a list of the optional parameters available. A full description of each optional parameter is provided in
Section 12.1.
Optional parameters may be specified by calling one, or more, of the functions
e05jcc,
e05jdc,
e05jec,
e05jfc and
e05jgc before a call to
e05jbc.
e05jcc reads options from an external options file, with
Begin and
End as the first and last lines respectively, and with each intermediate line defining a single optional parameter. For example,
Begin
Static Limit = 50
End
The call
e05jcc (fileid, &state, &fail);
can then be used to read the file on
the descriptor
fileid as returned by a call of
x04acc. The value
${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_NOERROR is returned
on successful exit.
e05jcc should be consulted for a full description of this method of supplying optional parameters.
e05jdc,
e05jec,
e05jfc or
e05jgc can be called to supply options directly, one call being necessary for each optional parameter.
e05jdc,
e05jec,
e05jfc or
e05jgc should be consulted for a full description of this method of supplying optional parameters.
All optional parameters not specified by you are set to their default values. Valid values of optional parameters specified by you are unaltered by e05jbc and so remain in effect for subsequent calls to e05jbc, unless you explicitly change them.
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:
 a parameter value,
where the letters $a$, $i$ and $r$ denote options that take character, integer and real values respectively, and where the letter $a$ denotes an option that takes an $\mathrm{ON}$ or $\mathrm{OFF}$ value;
 the default value, where the symbol $\epsilon $ is a generic notation for machine precision (see X02AJC), the symbol ${r}_{\mathrm{max}}$ stands for the largest positive model number (see X02ALC), ${n}_{r}$ represents the number of nonfixed variables, and the symbol $d$ stands for the maximum number of decimal digits that can be represented (see X02BEC).
Option names are caseinsensitive and must be provided in full; abbreviations are not recognized.
This special keyword is used to reset all optional parameters to their default values, and any random state stored in
state will be destroyed.
Any option value given with this keyword will be ignored. This optional parameter cannot be queried or got.
Function Evaluations Limit  $i$  Default $\text{}=100{n}_{r}^{2}$ 
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 $\mathit{nf}$ may be made.
Constraint:
$\mathit{nf}>0$.
Infinite Bound Size  $r$  Default $\text{}={r}_{\mathrm{max}}^{\frac{1}{4}}$ 
This defines the ‘infinite’ bound $\mathit{infbnd}$ in the definition of the problem constraints. Any upper bound greater than or equal to $\mathit{infbnd}$ will be regarded as $\infty $ (and similarly any lower bound less than or equal to $\mathit{infbnd}$ will be regarded as $\infty $).
Constraint:
${r}_{\mathrm{max}}^{\frac{1}{4}}\le \mathit{infbnd}\le {r}_{\mathrm{max}}^{\frac{1}{2}}$.
Local Searches  $a$  Default $\text{}=\mathrm{ON}$ 
If you want to try to accelerate convergence of e05jbc by starting local searches from candidate minima, you will require $\mathit{lcsrch}$ to be $\mathrm{ON}$.
Constraint:
$\mathit{lcsrch}=\mathrm{ON}\text{ or}\mathrm{OFF}$.
Local Searches Limit  $i$  Default $\text{}=50$ 
This defines the maximal number of iterations to be used in the trust region loop of the localsearch procedure.
Constraint:
$\mathit{loclim}>0$.
Local Searches Tolerance  $r$  Default $\text{}=2\epsilon $ 
The value of
$\mathit{loctol}$ 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:
$\mathit{loctol}\ge 2\epsilon $.
These keywords specify the required direction of optimization. Any option value given with these keywords will be ignored.
Optional parameter ${\mathbf{List}}$ enables printing of each optional parameter specification as it is supplied. ${\mathbf{Nolist}}$ suppresses this printing.
Repeatability  $a$  Default $\text{}=\mathrm{OFF}$ 
For use with random initialization lists (
${\mathbf{initmethod}}=\mathrm{Nag\_Random}$). When set to
$\mathrm{ON}$, an internallyinitialized random state is stored in
state for use in subsequent calls to
e05jbc.
Constraint:
$\mathit{repeat}=\mathrm{ON}\text{ or}\mathrm{OFF}$.
Splits Limit  $i$  Default $\text{}=\u230ad\left({n}_{r}+2\right)/3\u230b$ 
Along with the initialization list
list, this defines a limit on the number of times the root box will be split along any single coordinate direction. If
${\mathbf{Local\; Searches}}$ is
$\mathrm{OFF}$ you may find the default value to be too small.
Constraint:
$\mathit{smax}>{n}_{r}+2$.
Static Limit  $i$  Default $\text{}=3{n}_{r}$ 
As the default termination criterion, computation stops when the best function value is static for $\mathit{stclim}$ sweeps through levels. This parameter is ignored if you have specified a target value to reach in ${\mathbf{Target\; Objective\; Value}}$.
Constraint:
$\mathit{stclim}>0$.
Target Objective Error  $r$  Default $\text{}={\epsilon}^{\frac{1}{4}}$ 
If you have given a target objective value to reach in
$\mathit{objval}$ (the value of the optional parameter
${\mathbf{Target\; Objective\; Value}}$),
$\mathit{objerr}$ sets your desired relative error (from above if
${\mathbf{Minimize}}$ is set, from below if
${\mathbf{Maximize}}$ is set) between
obj and
$\mathit{objval}$, as described in
Section 7. See also the description of the optional parameter
${\mathbf{Target\; Objective\; Safeguard}}$.
Constraint:
$\mathit{objerr}\ge 2\epsilon $.
Target Objective Safeguard  $r$  Default $\text{}={\epsilon}^{\frac{1}{2}}$ 
If you have given a target objective value to reach in $\mathit{objval}$ (the value of the optional parameter ${\mathbf{Target\; Objective\; Value}}$), $\mathit{objsfg}$ sets your desired safeguarded termination tolerance, for when $\mathit{objval}$ is close to zero.
Constraint:
$\mathit{objsfg}\ge 2\epsilon $.
Target Objective Value  $r$  
This parameter may be set if you wish e05jbc to use a specific value as the target function value to reach during the optimization. Setting $\mathit{objval}$ overrides the default termination criterion determined by the optional parameter ${\mathbf{Static\; Limit}}$.