NAG Library Routine Document

E05JBF

1  Purpose

2  Specification

3  Description

CALL E05JAF (N_R, COMM, LCOMM, ...)
CALL E05JDF (OPTSTR, COMM, LCOMM, ...)
CALL E05JBF (N, OBJFUN, ...)

4  References

5  Parameters

1:     N – INTEGERInput

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

Constraint: $\mathbf{N}>0$.

2:     OBJFUN – SUBROUTINE, supplied by the user.External Procedure

OBJFUN must evaluate the objective function $F\left(\mathbf{x}\right)$ for a specified $n$-vector $\mathbf{x}$.

The specification of OBJFUN is:

SUBROUTINE OBJFUN ( N, X, F, NSTATE, IUSER, RUSER, INFORM) INTEGER  N, NSTATE, IUSER(*), INFORM REAL (KIND=nag_wp)  X(N), F, RUSER(*)

1:     N – INTEGERInput

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

2:     X(N) – REAL (KIND=nag_wp) arrayInput

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

3:     F – REAL (KIND=nag_wp)Output

On exit: must be set to the value of the objective function at $\mathbf{x}$, unless you have specified termination of the current problem using INFORM.

4:     NSTATE – INTEGERInput

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

5:     IUSER($*$) – INTEGER arrayUser Workspace

6:     RUSER($*$) – REAL (KIND=nag_wp) arrayUser Workspace

OBJFUN is called with the parameters IUSER and RUSER as supplied to E05JBF. You are free to use the arrays IUSER and RUSER to supply information to OBJFUN as an alternative to using COMMON global variables.

7:     INFORM – INTEGEROutput

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.

OBJFUN must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which E05JBF is called. Parameters denoted as Input must not be changed by this procedure.

3:     IBOUND – INTEGERInput

On entry: indicates whether the facility for dealing with bounds of special forms is to be used. IBOUND must be set to one of the following values.

$\mathbf{IBOUND}=0$

You will supply $\mathbf{\ell }$ and $\mathbf{u}$ individually.

$\mathbf{IBOUND}=1$

There are no bounds on $\mathbf{x}$.

$\mathbf{IBOUND}=2$

There are semi-infinite bounds $0\le \mathbf{x}$.

$\mathbf{IBOUND}=3$

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{IBOUND}=0$.

Constraint: $\mathbf{IBOUND}=0$, $1$, $2$ or $3$.

4:     IINIT – INTEGERInput

On entry: selects which initialization method to use.

$\mathbf{IINIT}=0$

Simple initialization (boundary and midpoint), with
$\mathbf{NUMPTS}\left(i\right)=3$, $\mathbf{INITPT}\left(i\right)=2$ and
$\mathbf{LIST}\left(i,j\right)=\left(\mathbf{BL}\left(i\right),\left(\mathbf{BL}\left(i\right)+\mathbf{BU}\left(i\right)\right)/2,\mathbf{BU}\left(i\right)\right)$,
for $i=1,2,\dots ,\mathbf{N}$ and $j=1,2,3$.

$\mathbf{IINIT}=1$

Simple initialization (off-boundary and midpoint), with
$\mathbf{NUMPTS}\left(i\right)=3$, $\mathbf{INITPT}\left(i\right)=2$ and
$$\begin{gathered} \mathbf{LIST}\left(i,j\right)= \\ \left(\left(5\mathbf{BL}\left(i\right)+\mathbf{BU}\left(i\right)\right)/6,\left(\mathbf{BL}\left(i\right)+\mathbf{BU}\left(i\right)\right)/2,\left(\mathbf{BL}\left(i\right)+5\mathbf{BU}\left(i\right)\right)/6\right) \end{gathered}$$,
for $i=1,2,\dots ,\mathbf{N}$ and $j=1,2,3$.

$\mathbf{IINIT}=2$

Initialization using linesearches.

$\mathbf{IINIT}=3$

You are providing your own initialization list.

$\mathbf{IINIT}=4$

Generate a random initialization list.

For more information on methods $\mathbf{IINIT}=2$, $3$ or $4$ see Section 10.1.

If ‘infinite’ values (as determined by the value of the optional parameter Infinite Bound Size) are detected by E05JBF when you are using a simple initialization method ($\mathbf{IINIT}=0$ or $1$), a safeguarded initialization procedure will be attempted, to avoid overflow.

Suggested value: $\mathbf{IINIT}=0$

Constraint: $\mathbf{IINIT}=0$, $1$, $2$, $3$ or $4$.

5:     BL(N) – REAL (KIND=nag_wp) arrayInput/Output

6:     BU(N) – REAL (KIND=nag_wp) arrayInput/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{IBOUND}=0$, you must set $\mathbf{BL}\left(\mathit{i}\right)$ to ${\ell }_{\mathit{i}}$ and $\mathbf{BU}\left(\mathit{i}\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(i\right)$ should be set to $-\mathit{infbnd}$, where $\mathit{infbnd}$ is the value of the optional parameter Infinite Bound Size. Similarly, if a particular $x_i$ is to be unbounded above, the corresponding $\mathbf{BU}\left(i\right)$ should be set to $\mathit{infbnd}$.

If $\mathbf{IBOUND}=1$ or $2$, arrays BL and BU need not be set on input.

If $\mathbf{IBOUND}=3$, you must set $\mathbf{BL}\left(1\right)$ to ${\ell }_1$ and $\mathbf{BU}\left(1\right)$ to $u_1$. The remaining elements of BL and BU will then be populated by these initial values.

On exit: unless $\mathbf{IFAIL}=\mathbf{1}$ or $\mathbf{2}$ on exit, BL and BU are the actual arrays of bounds used by E05JBF.

Constraints:

• if $\mathbf{IBOUND}=0$, $\mathbf{BL}\left(\mathit{i}\right)\le \mathbf{BU}\left(\mathit{i}\right)$, for $\mathit{i}=1,2,\dots ,\mathbf{N}$;
• if $\mathbf{IBOUND}=3$, $\mathbf{BL}\left(1\right)<\mathbf{BU}\left(1\right)$.

7:     SDLIST – INTEGERInput

On entry: the second dimension of the array LIST as declared in the (sub)program from which E05JBF is called. SDLIST is, 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}{\max }}\mathbf{NUMPTS}\left(i\right)$.

Internally, E05JBF 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{IINIT}=2$) internal storage considerations require that SDLIST be at least $192$, but not all of this space may be used.

Constraints:

• if $\mathbf{IINIT}\ne 2$, $\mathbf{SDLIST}\ge 3$;
• if $\mathbf{IINIT}=2$, $\mathbf{SDLIST}\ge 192$;
• if $\mathbf{IINIT}=3$, $\mathbf{SDLIST}\ge {\displaystyle \underset{\mathit{i}}{\max }}\left\{\mathbf{NUMPTS}\left(\mathit{i}\right)\right\}$.

8:     LIST(N,SDLIST) – REAL (KIND=nag_wp) arrayInput/Output

On entry: this parameter need not be set on entry if you wish to use one of the preset initialization methods ($\mathbf{IINIT}\ne 3$).

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 $\mathbf{LIST}\left(i,1:\mathbf{NUMPTS}\left(i\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}\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 safe-range parameter (see X02AMF).

On exit: unless $\mathbf{IFAIL}=\mathbf{1}$, $\mathbf{2}$ or $-\mathbf{999}$ on exit, the actual initialization data used by E05JBF. If you wish to monitor the contents of LIST you are advised to do so solely through MONIT, not through the output value here.

Constraint: if $\mathbf{X}\left(\mathit{i}\right)$ is not fixed, $\mathbf{LIST}\left(\mathit{i},1:\mathbf{NUMPTS}\left(\mathit{i}\right)\right)$ is in ascending order with each entry being distinct, for $\mathit{i}=1,2,\dots ,\mathbf{N}$$\mathbf{BL}\left(\mathit{i}\right)\le \mathbf{LIST}\left(\mathit{i},\mathit{j}\right)\le \mathbf{BU}\left(\mathit{i}\right)$, for $\mathit{i}=1,2,\dots ,\mathbf{N}$ and $\mathit{j}=1,2,\dots ,\mathbf{NUMPTS}\left(\mathit{i}\right)$.

9:     NUMPTS(N) – INTEGER arrayInput/Output

On entry: this parameter need not be set on entry if you wish to use one of the preset initialization methods ($\mathbf{IINIT}\ne 3$).

NUMPTS encodes the number of splitting points in each non-fixed dimension.

On exit: unless $\mathbf{IFAIL}=\mathbf{1}$, $\mathbf{2}$ or $-\mathbf{999}$ on exit, the actual initialization data used by E05JBF.

Constraints:

• if $\mathbf{X}\left(\mathit{i}\right)$ is not fixed, $\mathbf{NUMPTS}\left(\mathit{i}\right)\le \mathbf{SDLIST}$;
• $\mathbf{NUMPTS}\left(\mathit{i}\right)\ge 3$, for $\mathit{i}=1,2,\dots ,\mathbf{N}$.

10:   INITPT(N) – INTEGER arrayInput/Output

On entry: this parameter need not be set on entry if you wish to use one of the preset initialization methods ($\mathbf{IINIT}\ne 3$).

You must designate a point stored in LIST that you wish E05JBF 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}\right)=J_{\mathit{i}}$, for $\mathit{i}=1,2,\dots ,n$.

On exit: unless $\mathbf{IFAIL}=\mathbf{1}$, $\mathbf{2}$ or $-\mathbf{999}$ on exit, the actual initialization data used by E05JBF.

Constraint: if $\mathbf{X}\left(\mathit{i}\right)$ is not fixed, $1\le \mathbf{INITPT}\left(\mathit{i}\right)\le \mathbf{SDLIST}$, for $\mathit{i}=1,2,\dots ,\mathbf{N}$.

11:   MONIT – SUBROUTINE, supplied by the NAG Library or the user.External Procedure

MONIT may be used to monitor the optimization process. It is invoked upon every successful completion of the procedure in which a sub-box is considered for splitting. It will also be called just before E05JBF exits if that splitting procedure was not successful.

If no monitoring is required, MONIT may be the dummy monitoring routine E05JBK supplied by the NAG Library.

The specification of MONIT is:

SUBROUTINE MONIT ( N, NCALL, XBEST, ICOUNT, NINIT, LIST, NUMPTS, INITPT, NBASKT, XBASKT, BOXL, BOXU, NSTATE, IUSER, RUSER, INFORM) INTEGER  N, NCALL, ICOUNT(6), NINIT, NUMPTS(N), INITPT(N), NBASKT, NSTATE, IUSER(*), INFORM REAL (KIND=nag_wp)  XBEST(N), LIST(N,NINIT), XBASKT(N,NBASKT), BOXL(N), BOXU(N), RUSER(*)

1:     N – INTEGERInput

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

2:     NCALL – INTEGERInput

On entry: the cumulative number of calls to OBJFUN.

3:     XBEST(N) – REAL (KIND=nag_wp) arrayInput

On entry: the current best point.

4:     ICOUNT($6$) – INTEGER arrayInput

On entry: an array of counters.

$\mathbf{ICOUNT}\left(1\right)$

$\mathit{nboxes}$, the current number of sub-boxes.

$\mathbf{ICOUNT}\left(2\right)$

$\mathit{ncloc}$, the cumulative number of calls to OBJFUN made in local searches.

$\mathbf{ICOUNT}\left(3\right)$

$\mathit{nloc}$, the cumulative number of points used as start points for local searches.

$\mathbf{ICOUNT}\left(4\right)$

$\mathit{nsweep}$, the cumulative number of sweeps through levels.

$\mathbf{ICOUNT}\left(5\right)$

$\mathit{m}$, the cumulative number of splits by initialization list.

$\mathbf{ICOUNT}\left(6\right)$

$\mathit{s}$, the current lowest level containing non-split boxes.

5:     NINIT – INTEGERInput

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 parameter NUMPTS.

6:     LIST(N,NINIT) – REAL (KIND=nag_wp) arrayInput

On entry: the initialization list.

7:     NUMPTS(N) – INTEGER arrayInput

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

8:     INITPT(N) – INTEGER arrayInput

On entry: a pointer to the ‘initial point’ in LIST. Element $\mathbf{INITPT}\left(i\right)$ is the column index in LIST of the $i$th coordinate of the initial point.

9:     NBASKT – INTEGERInput

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

10:   XBASKT(N,NBASKT) – REAL (KIND=nag_wp) arrayInput

Note: the $j$th candidate minimum has its $i$th coordinate stored in $\mathbf{XBASKT}\left(\mathit{j},\mathit{i}\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:   BOXL(N) – REAL (KIND=nag_wp) arrayInput

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

12:   BOXU(N) – REAL (KIND=nag_wp) arrayInput

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

13:   NSTATE – INTEGERInput

On entry: is set by E05JBF 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:   IUSER($*$) – INTEGER arrayUser Workspace

15:   RUSER($*$) – REAL (KIND=nag_wp) arrayUser Workspace

MONIT is called with the parameters IUSER and RUSER as supplied to E05JBF. You are free to use the arrays IUSER and RUSER to supply information to MONIT as an alternative to using COMMON global variables.

16:   INFORM – INTEGEROutput

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.

MONIT must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which E05JBF is called. Parameters denoted as Input must not be changed by this procedure.

12:   X(N) – REAL (KIND=nag_wp) arrayOutput

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

13:   OBJ – REAL (KIND=nag_wp)Output

On exit: if $\mathbf{IFAIL}=\mathbf{0}$, contains the function value at X.

If you request early termination of E05JBF using INFORM in OBJFUN or the analogous INFORM in MONIT, there is no guarantee that the function value at X equals OBJ.

14:   COMM(LCOMM) – REAL (KIND=nag_wp) arrayCommunication Array

On exit: COMM must not be altered between calls to any of the routines E05JBF, E05JCF, E05JDF, E05JEF, E05JFF, E05JGF, E05JHF, E05JJF, E05JKF and E05JLF.

15:   LCOMM – INTEGERInput

On entry: the dimension of the array COMM as declared in the (sub)program from which E05JBF is called.

Constraint: $\mathbf{LCOMM}\ge 100$.

16:   IUSER($*$) – INTEGER arrayUser Workspace

17:   RUSER($*$) – REAL (KIND=nag_wp) arrayUser Workspace

IUSER and RUSER are not used by E05JBF, but are passed directly to OBJFUN and MONIT and may be used to pass information to these routines as an alternative to using COMMON global variables.

18:   IFAIL – INTEGERInput/Output

On entry: IFAIL must be set to $0$, $-1\text{ or }1$. If you are unfamiliar with this parameter you should refer to Section 3.3 in the Essential Introduction for details.

For environments where it might be inappropriate to halt program execution when an error is detected, the value $-1\text{ or }1$ is recommended. If the output of error messages is undesirable, then the value $1$ is recommended. Otherwise, if you are not familiar with this parameter, the recommended value is $0$. When the value $-\mathbf{1}\text{ or }\mathbf{1}$ is used it is essential to test the value of IFAIL on exit.

On exit: $\mathbf{IFAIL}=\mathbf{0}$ unless the routine detects an error or a warning has been flagged (see Section 6).

E05JBF returns with $\mathbf{IFAIL}=\mathbf{0}$ 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 Target Objective Value, Target Objective Error and Target Objective Safeguard), or the best function value was static for the number of sweeps through levels given by the optional parameter Static Limit. The latter criterion is the default.

6  Error Indicators and Warnings

$\mathbf{IFAIL}=1$

Either the initialization routine E05JAF has not been called or LCOMM is less than 100.

$\mathbf{IFAIL}=2$

An input parameter is invalid. If $\mathbf{IFAIL}=\mathbf{0}$ or $-\mathbf{1}$ on entry, the output message provides more details of the invalid argument.

$\mathbf{IFAIL}=3$

The initialization list contained infinities.

Either the user-supplied initialization list contained infinite values, as determined by the optional parameter Infinite Bound Size, or a finite initialization list could not be computed internally. In the latter case you should consider reformulating the bounds on the problem, try providing your own initialization list, use the randomization option ($\mathbf{IINIT}=4$) or vary the value of Infinite Bound Size.

$\mathbf{IFAIL}=4$

The division procedure completed but your target value could not be reached.

Despite every sub-box being processed $\mathit{smax}$ times (where $\mathit{smax}$ is the value of the optional parameter Splits Limit), the target value you provided via the optional parameter Target Objective Value could not be found to the tolerances given in the optional parameters Target Objective Error and Target Objective Safeguard. You could try increasing Splits Limit or the objective tolerances.

$\mathbf{IFAIL}=5$

The function evaluations limit was exceeded.

Approximately $\mathit{nf}$ function calls (where $\mathit{nf}$ is the value of the optional parameter Function Evaluations Limit) have been made without your chosen termination criterion being satisfied.

$\mathbf{IFAIL}=6$

You terminated the solver.

You indicated that you wished to halt solution of the current problem by setting INFORM in OBJFUN or INFORM in MONIT to a negative value on exit. If $\mathbf{IFAIL}=\mathbf{0}$ or $-\mathbf{1}$ on entry to E05JBF, the output message provides more details of where the termination was requested.

$\mathbf{IFAIL}=7$

No further progress could be made on your problem. Try rescaling the objective function, relaxing the bounds, or using a different initialization method.

$\mathbf{IFAIL}=-999$

Internal memory allocation failed.

7  Accuracy

8  Further Comments

9  Example

9.1  Program Text

Program Text (e05jbfe.f90)

9.2  Program Data

Program Data (e05jbfe.d)

9.3  Program Results

Program Results (e05jbfe.r)

10  Algorithmic Details

10.1  Initialization and Sweeps

10.2  Splitting

10.2.1  Splitting by rank

10.2.2  Splitting by expected gain

10.3  Local Search

11  Optional Parameters

• Defaults
• Function Evaluations Limit
• Infinite Bound Size
• List
• Local Searches
• Local Searches Limit
• Local Searches Tolerance
• Maximize
• Minimize
• Nolist
• Repeatability
• Splits Limit
• Static Limit
• Target Objective Error
• Target Objective Safeguard
• Target Objective Value

 Begin
   Static Limit = 50
 End

 CALL E05JCF (IOPTS, COMM, LCOMM, IFAIL)

11.1  Description of the Optional Parameters

• a parameter value, where the letters $a$, $i\text{ and }r$ denote options that take character, integer and real values respectively, and where the letter $a$ denotes an option that takes an ‘ON’ or ‘OFF’ value;
• the default value, where the symbol $\epsilon$ is a generic notation for machine precision (see X02AJF), the symbol $r_{\max }$ stands for the largest positive model number (see X02ALF), $n_r$ represents the number of non-fixed variables, and the symbol $d$ stands for the maximum number of decimal digits that can be represented (see X02BEF).