NAG Library Routine Document
E04JCF
1 Purpose
E04JCF is an easytouse algorithm that uses methods of quadratic approximation to find a minimum of an objective function $F$ over $\mathbf{x}\in {R}^{n}$, subject to fixed lower and upper bounds on the independent variables ${x}_{1},{x}_{2},\dots ,{x}_{n}$. Derivatives of $F$ are not required.
The routine is intended for functions that are continuous and that have continuous first and second derivatives (although it will usually work even if the derivatives have occasional discontinuities). Efficiency is maintained for large $n$.
2 Specification
SUBROUTINE E04JCF ( 
OBJFUN, N, NPT, X, BL, BU, RHOBEG, RHOEND, MONFUN, MAXCAL, F, NF, IUSER, RUSER, IFAIL) 
INTEGER 
N, NPT, MAXCAL, NF, IUSER(*), IFAIL 
REAL (KIND=nag_wp) 
X(N), BL(N), BU(N), RHOBEG, RHOEND, F, RUSER(*) 
EXTERNAL 
OBJFUN, MONFUN 

3 Description
E04JCF is applicable to problems of the form:
where
$F$ is a nonlinear scalar function whose derivatives may be unavailable, and where the bound vectors are elements of
${R}^{n}$. Relational operators between vectors are interpreted elementwise.
Fixing variables (that is, setting ${\ell}_{i}={u}_{i}$ for some $i$) is allowed in E04JCF.
You must supply a subroutine to calculate the value of $F$ at any given point $\mathbf{x}$.
The method used by E04JCF is based on BOBYQA, the method of Bound Optimization BY Quadratic Approximation described in
Powell (2009). In particular, each iteration of E04JCF generates a quadratic approximation
$Q$ to
$F$ that agrees with
$F$ at
$m$ automatically chosen interpolation points. The value of
$m$ is a constant prescribed by you. Updates to the independent variables mostly occur from approximate solutions to trustregion subproblems, using the current quadratic model.
4 References
Powell M J D (2009) The BOBYQA algorithm for bound constrained optimization without derivatives
Report DAMTP 2009/NA06 University of Cambridge
http://www.damtp.cam.ac.uk/user/na/NA_papers/NA2009_06.pdf
5 Parameters
 1: $\mathrm{OBJFUN}$ – SUBROUTINE, supplied by the user.External Procedure

OBJFUN must evaluate the objective function
$F$ at a specified vector
$\mathbf{x}$.
The specification of
OBJFUN is:
INTEGER 
N, IUSER(*), INFORM 
REAL (KIND=nag_wp) 
X(N), F, RUSER(*) 

 1: $\mathrm{N}$ – INTEGERInput

On entry: $n$, the number of independent variables.
 2: $\mathrm{X}\left({\mathbf{N}}\right)$ – REAL (KIND=nag_wp) arrayInput

On entry: $\mathbf{x}$, the vector at which the objective function is to be evaluated.
 3: $\mathrm{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: $\mathrm{IUSER}\left(*\right)$ – INTEGER arrayUser Workspace
 5: $\mathrm{RUSER}\left(*\right)$ – REAL (KIND=nag_wp) arrayUser Workspace

OBJFUN is called with the parameters
IUSER and
RUSER as supplied to E04JCF. You are free to use the arrays
IUSER and
RUSER to supply information to
OBJFUN as an alternative to using COMMON global variables.
 6: $\mathrm{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 E04JCF is called. Parameters denoted as
Input must
not be changed by this procedure.
 2: $\mathrm{N}$ – INTEGERInput

On entry: $n$, the number of independent variables.
Constraint:
${\mathbf{N}}\ge 2$ and ${n}_{r}\ge 2$, where ${n}_{r}$ denotes the number of nonfixed variables.
 3: $\mathrm{NPT}$ – INTEGERInput

On entry: $m$, the number of interpolation conditions imposed on the quadratic approximation at each iteration.
Suggested value:
${\mathbf{NPT}}=2\times {n}_{r}+1$, where ${n}_{r}$ denotes the number of nonfixed variables.
Constraint:
${n}_{r}+2\le {\mathbf{NPT}}\le \frac{\left({n}_{r}+1\right)\times \left({n}_{r}+2\right)}{2}$, where ${n}_{r}$ denotes the number of nonfixed variables.
 4: $\mathrm{X}\left({\mathbf{N}}\right)$ – REAL (KIND=nag_wp) arrayInput/Output

On entry: an estimate of the position of the minimum. If any component is outofbounds it is replaced internally by the bound it violates.
On exit: the lowest point found during the calculations. Thus, if
${\mathbf{IFAIL}}={\mathbf{0}}$ on exit,
X is the position of the minimum.
 5: $\mathrm{BL}\left({\mathbf{N}}\right)$ – REAL (KIND=nag_wp) arrayInput
 6: $\mathrm{BU}\left({\mathbf{N}}\right)$ – REAL (KIND=nag_wp) arrayInput

On entry: the fixed vectors of bounds: the lower bounds
$\mathbf{\ell}$ and the upper bounds
$\mathbf{u}$, respectively. To signify that a variable is unbounded you should choose a large scalar
$r$ appropriate to your problem, then set the lower bound on that variable to
$r$ and the upper bound to
$r$. For wellscaled problems
$r={r}_{\mathrm{max}}^{\frac{1}{4}}$ may be suitable, where
${r}_{\mathrm{max}}$ denotes the largest positive model number (see
X02ALF).
Constraints:
 if ${\mathbf{X}}\left(\mathit{i}\right)$ is to be fixed at ${\mathbf{BL}}\left(\mathit{i}\right)$, then ${\mathbf{BL}}\left(\mathit{i}\right)={\mathbf{BU}}\left(\mathit{i}\right)$;
 otherwise ${\mathbf{BU}}\left(\mathit{i}\right){\mathbf{BL}}\left(\mathit{i}\right)\ge 2.0\times {\mathbf{RHOBEG}}$, for $\mathit{i}=1,2,\dots ,{\mathbf{N}}$.
 7: $\mathrm{RHOBEG}$ – REAL (KIND=nag_wp)Input

On entry: an initial lower bound on the value of the trustregion radius.
Suggested value:
RHOBEG should be about one tenth of the greatest expected overall change to a variable: the initial quadratic model will be constructed by taking steps from the initial
X of length
RHOBEG along each coordinate direction.
Constraints:
 ${\mathbf{RHOBEG}}>0.0$;
 ${\mathbf{RHOBEG}}\ge {\mathbf{RHOEND}}$.
 8: $\mathrm{RHOEND}$ – REAL (KIND=nag_wp)Input

On entry: a final lower bound on the value of the trustregion radius.
Suggested value:
RHOEND should indicate the absolute accuracy that is required in the final values of the variables.
Constraint:
${\mathbf{RHOEND}}>0.0$.
 9: $\mathrm{MONFUN}$ – SUBROUTINE, supplied by the NAG Library or the user.External Procedure

MONFUN may be used to monitor the optimization process. It is invoked every time a new trustregion radius is chosen.
If no monitoring is required,
MONFUN may be the dummy monitoring routine E04JCP supplied by the NAG Library.
The specification of
MONFUN is:
INTEGER 
N, NF, IUSER(*), INFORM 
REAL (KIND=nag_wp) 
X(N), F, RHO, RUSER(*) 

 1: $\mathrm{N}$ – INTEGERInput

On entry: $n$, the number of independent variables.
 2: $\mathrm{NF}$ – INTEGERInput

On entry: the cumulative number of calls made to
OBJFUN.
 3: $\mathrm{X}\left({\mathbf{N}}\right)$ – REAL (KIND=nag_wp) arrayInput

On entry: the current best point.
 4: $\mathrm{F}$ – REAL (KIND=nag_wp)Input

On entry: the value of
OBJFUN at
X.
 5: $\mathrm{RHO}$ – REAL (KIND=nag_wp)Input

On entry: a lower bound on the current trustregion radius.
 6: $\mathrm{IUSER}\left(*\right)$ – INTEGER arrayUser Workspace
 7: $\mathrm{RUSER}\left(*\right)$ – REAL (KIND=nag_wp) arrayUser Workspace

MONFUN is called with the parameters
IUSER and
RUSER as supplied to E04JCF. You are free to use the arrays
IUSER and
RUSER to supply information to
MONFUN as an alternative to using COMMON global variables.
 8: $\mathrm{INFORM}$ – INTEGEROutput

On exit: must be set to a value describing the action to be taken by the solver on return from
MONFUN. Specifically, if the value is negative the solution of the current problem will terminate immediately; otherwise, computations will continue.
MONFUN must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which E04JCF is called. Parameters denoted as
Input must
not be changed by this procedure.
 10: $\mathrm{MAXCAL}$ – INTEGERInput

On entry: the maximum permitted number of calls to
OBJFUN.
Constraint:
${\mathbf{MAXCAL}}\ge 1$.
 11: $\mathrm{F}$ – REAL (KIND=nag_wp)Output

On exit: the function value at the lowest point found (
X).
 12: $\mathrm{NF}$ – INTEGEROutput

On exit: unless
${\mathbf{IFAIL}}={\mathbf{1}}$ or
${{\mathbf{999}}}$ on exit, the total number of calls made to
OBJFUN.
 13: $\mathrm{IUSER}\left(*\right)$ – INTEGER arrayUser Workspace
 14: $\mathrm{RUSER}\left(*\right)$ – REAL (KIND=nag_wp) arrayUser Workspace

IUSER and
RUSER are not used by E04JCF, but are passed directly to
OBJFUN and
MONFUN and may be used to pass information to these routines as an alternative to using COMMON global variables.
 15: $\mathrm{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).
E04JCF returns with
${\mathbf{IFAIL}}={\mathbf{0}}$ if the final trustregion radius has reached its lower bound
RHOEND.
6 Error Indicators and Warnings
If on entry
${\mathbf{IFAIL}}={\mathbf{0}}$ or
${{\mathbf{1}}}$, explanatory error messages are output on the current error message unit (as defined by
X04AAF).
Errors or warnings detected by the routine:
 ${\mathbf{IFAIL}}=1$

On entry, ${\mathbf{MAXCAL}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{MAXCAL}}\ge 1$.
On entry, ${\mathbf{RHOBEG}}=\u2329\mathit{\text{value}}\u232a$, ${\mathbf{BL}}\left(i\right)=\u2329\mathit{\text{value}}\u232a$, ${\mathbf{BU}}\left(i\right)=\u2329\mathit{\text{value}}\u232a$ and $i=\u2329\mathit{\text{value}}\u232a$.
Constraint: if ${\mathbf{BL}}\left(i\right)\ne {\mathbf{BU}}\left(i\right)$ in coordinate $i$, then ${\mathbf{BU}}\left(i\right){\mathbf{BL}}\left(i\right)\ge 2\times {\mathbf{RHOBEG}}$.
On entry, ${\mathbf{RHOBEG}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{RHOBEG}}>0.0$.
On entry, ${\mathbf{RHOBEG}}=\u2329\mathit{\text{value}}\u232a$ and ${\mathbf{RHOEND}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{RHOEND}}\le {\mathbf{RHOBEG}}$.
On entry, ${\mathbf{RHOEND}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{RHOEND}}>0.0$.
There were ${n}_{r}=\u2329\mathit{\text{value}}\u232a$ unequal bounds.
Constraint: ${n}_{r}\ge 2$.
There were ${n}_{r}=\u2329\mathit{\text{value}}\u232a$ unequal bounds and ${\mathbf{NPT}}=\u2329\mathit{\text{value}}\u232a$ on entry.
Constraint: ${n}_{r}+2\le {\mathbf{NPT}}\le \frac{\left({n}_{r}+1\right)\times \left({n}_{r}+2\right)}{2}$.
 ${\mathbf{IFAIL}}=2$

The function evaluations limit was reached:
OBJFUN has been called
MAXCAL times.
 ${\mathbf{IFAIL}}=3$

The predicted reduction in a trustregion step was nonpositive. Check your specification of
OBJFUN and whether the function needs rescaling. Try a different initial
X.
 ${\mathbf{IFAIL}}=4$

A rescue procedure has been called in order to correct damage from rounding errors when computing an update to a quadratic approximation of
$F$, but no further progess could be made. Check your specification of
OBJFUN and whether the function needs rescaling. Try a different initial
X.
 ${\mathbf{IFAIL}}=5$

Usersupplied monitoring routine requested termination.
Usersupplied objective function requested termination.
 ${\mathbf{IFAIL}}=99$
An unexpected error has been triggered by this routine. Please
contact
NAG.
See
Section 3.8 in the Essential Introduction for further information.
 ${\mathbf{IFAIL}}=399$
Your licence key may have expired or may not have been installed correctly.
See
Section 3.7 in the Essential Introduction for further information.
 ${\mathbf{IFAIL}}=999$
Dynamic memory allocation failed.
See
Section 3.6 in the Essential Introduction for further information.
7 Accuracy
Experience shows that, in many cases, on successful termination the
$\infty $norm distance from the best point
$\mathbf{x}$ to a local minimum of
$F$ is less than
$10\times {\mathbf{RHOEND}}$, unless
RHOEND is so small that such accuracy is unattainable.
8 Parallelism and Performance
E04JCF is not threaded by NAG in any implementation.
E04JCF 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 routine. Please also consult the
Users' Note for your implementation for any additional implementationspecific information.
For each invocation of E04JCF, local workspace arrays of fixed length are allocated internally. The total size of these arrays amounts to
$\left({\mathbf{NPT}}+6\right)\times \left({\mathbf{NPT}}+{n}_{r}\right)+\frac{{n}_{r}\times \left(3{n}_{r}+21\right)}{2}$ real elements and
${n}_{r}$ integer elements, where
${n}_{r}$ denotes the number of nonfixed variables; that is, the total size is
$\mathcal{O}\left({n}_{r}^{4}\right)$. If you follow the recommendation for the choice of
NPT on entry, this total size reduces to
$\mathcal{O}\left({n}_{r}^{2}\right)$.
Usually the total number of function evaluations (
NF) is substantially less than
$\mathcal{O}\left({n}_{r}^{2}\right)$, and often, if
${\mathbf{NPT}}=2\times {n}_{r}+1$ on entry,
NF is only of magnitude
${n}_{r}$ or less.
10 Example
This example involves the minimization of
subject to
starting from the initial guess
$\left(3,1,0,1\right)$.
10.1 Program Text
Program Text (e04jcfe.f90)
10.2 Program Data
None.
10.3 Program Results
Program Results (e04jcfe.r)