NAG FL Interface
e04fff (handle_solve_dfls)
Note: this routine 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
e04fff is a forward communication Derivativefree Optimization (DFO) solver from the NAG optimization modelling suite (DFLS) for small to mediumscale nonlinear least squares problems with bound constraints.
2
Specification
Fortran Interface
Subroutine e04fff ( 
handle, objfun, monit, nvar, x, nres, rx, rinfo, stats, iuser, ruser, cpuser, ifail) 
Integer, Intent (In) 
:: 
nvar, nres 
Integer, Intent (Inout) 
:: 
iuser(*), ifail 
Real (Kind=nag_wp), Intent (Inout) 
:: 
x(nvar), ruser(*) 
Real (Kind=nag_wp), Intent (Out) 
:: 
rx(nres), rinfo(100), stats(100) 
Type (c_ptr), Intent (In) 
:: 
handle, cpuser 
External 
:: 
objfun, monit 

C Header Interface
#include <nag.h>
void 
e04fff_ (void **handle, void (NAG_CALL *objfun)(const Integer *nvar, const double x[], const Integer *nres, double rx[], Integer *inform, Integer iuser[], double ruser[], void **cpuser), void (NAG_CALL *monit)(const Integer *nvar, const double x[], Integer *inform, const double rinfo[], const double stats[], Integer iuser[], double ruser[], void **cpuser), const Integer *nvar, double x[], const Integer *nres, double rx[], double rinfo[], double stats[], Integer iuser[], double ruser[], void **cpuser, Integer *ifail) 

C++ Header Interface
#include <nag.h> extern "C" {
void 
e04fff_ (void *&handle, void (NAG_CALL *objfun)(const Integer &nvar, const double x[], const Integer &nres, double rx[], Integer &inform, Integer iuser[], double ruser[], void *&cpuser), void (NAG_CALL *monit)(const Integer &nvar, const double x[], Integer &inform, const double rinfo[], const double stats[], Integer iuser[], double ruser[], void *&cpuser), const Integer &nvar, double x[], const Integer &nres, double rx[], double rinfo[], double stats[], Integer iuser[], double ruser[], void *&cpuser, Integer &ifail) 
}

The routine may be called by the names e04fff or nagf_opt_handle_solve_dfls.
3
Description
e04fff is aimed at minimizing a sum of squares objective function subject to bound constraints:
Here the
${r}_{i}\left(x\right)$ are smooth nonlinear functions called residuals and
${l}_{x}$ and
${u}_{x}$ are
$n$dimensional vectors defining bounds on the variables. Typically, in a calibration or data fitting context, the residuals will be defined as the difference between the data points and a nonlinear model (see
Section 2.2.3 in the
E04 Chapter Introduction).
e04fff serves as a solver for compatible problems stored as a handle. The handle points to an internal data structure which defines the problem and serves as a means of communication for routines in the NAG optimization modelling suite. To define a compatible problem handle, you must call
e04raf followed by
e04rmf to initialize it and optionally call
e04rhf to define bounds on the variables. If
e04rhf is not called, all the variables will be considered free by the solver. It should be noted that
e04fff always assumes that the Jacobian of the residuals is dense, therefore defining a sparse structure for the residuals in the call to
e04rmf will have no effect. See
Section 3.1 in the
E04 Chapter Introduction for more details about the NAG optimization modelling suite.
The solver allows fixing variables with the definition of the bounds. However, the following constraint must be met in order to be able to call the solver:
 for all nonfixed variable ${x}_{i}$, the value of ${u}_{x}\left(i\right){l}_{x}\left(i\right)$ must be at least twice the starting trust region radius (see the consistency constraint of the optional parameter DFO Starting Trust Region).
The solver is based on a derivativefree trust region framework. This type of method is well suited for small to mediumscale problems (around 100 variables) for which the derivatives are unavailable or not easy to compute, and/or for which the function evaluations are expensive or noisy. For a detailed description of the algorithm see
Section 11.
The algorithm behaviour and solver strategy can be modified by various optional parameters (see
Section 12) which can be set by
e04zmf and
e04zpf at any time between the initialization of the handle by
e04raf and a call to the solver. The optional parameters' names specific for this solver start either with the prefix DFO (Derivativefree Optimization) or DFLS (Derivativefree Least Squares). The default values for these optional parameters are chosen to work well in the general case, but it is recommended you tune them to your particular problem. In particular, if the objective function is known to be noisy, it is highly recommended to set the optional parameter
DFO Noisy Problem to
$\mathrm{YES}$.
Once the solver has finished, options may be modified for the next solve. The solver may be called repeatedly with various starting points and/or optional parameters.
The underlying algorithm implemented for
e04fff is the same as the one used by
e04fgf.
e04fff serves as a forward communication interface to the derivativefree solver for nonlinear least squares problems.
4
References
Cartis C, Fiala J, Marteau B and Roberts L (2018) Improving the Flexibility and Robustness of ModelBased DerivativeFree Optimization Solvers Technical Report University of Oxford
Cartis C and Roberts L (2017) A DerivativeFree GaussNewton Method
Conn A R, Scheinberg K and Vicente L N (2009) Introduction to DerivativeFree Optimization, vol. 8 of MPSSIAM Series on Optimization MPS/SIAM, Philadelphia
Powell M J D (2009) The BOBYQA algorithm for bound constrained optimization without derivatives
Report DAMTP 2009/NA06 University of Cambridge
https://www.damtp.cam.ac.uk/user/na/NA_papers/NA2009_06.pdf
Zhang H, Conn A R and Scheinberg K (2010) A DerivativeFree Algorithm for LeastSquares Minimization SIAM J. Optim. 20(6) 3555–3576
5
Arguments

1:
$\mathbf{handle}$ – Type (c_ptr)
Input

On entry: the handle to the problem. It needs to be initialized by
e04raf and
must not be changed before the call to
e04fff.

2:
$\mathbf{objfun}$ – Subroutine, supplied by the user.
External Procedure

objfun must evaluate the value of the nonlinear residuals
${r}_{i}\left(x\right)$ at a specified point
$x$.
The specification of
objfun is:
Fortran Interface
Integer, Intent (In) 
:: 
nvar, nres 
Integer, Intent (Inout) 
:: 
inform, iuser(*) 
Real (Kind=nag_wp), Intent (In) 
:: 
x(nvar) 
Real (Kind=nag_wp), Intent (Inout) 
:: 
ruser(*) 
Real (Kind=nag_wp), Intent (Out) 
:: 
rx(nres) 
Type (c_ptr), Intent (In) 
:: 
cpuser 

C++ Header Interface
#include <nag.h> extern "C" {
}


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

On entry:
$n$, the number of variables in the problem, as set during the initialization of the handle by
e04raf.

2:
$\mathbf{x}\left({\mathbf{nvar}}\right)$ – Real (Kind=nag_wp) array
Input

On entry: $x$, the vector of variable values at which the residuals ${r}_{i}$ are to be evaluated.

3:
$\mathbf{nres}$ – Integer
Input

On entry:
${m}_{r}$, the number of residuals in the problem, as set during the initialization of the handle by
e04rmf.

4:
$\mathbf{rx}\left({\mathbf{nres}}\right)$ – Real (Kind=nag_wp) array
Output

On exit: the value of the residuals ${r}_{i}\left(x\right)$ at $x$.

5:
$\mathbf{inform}$ – Integer
Input/Output

On entry: a nonnegative value.
On exit: may be used to indicate that the requested objective value could not be computed. Specifically, it can be set to a negative value:
 ${\mathbf{inform}}=1$
 The solver will attempt a rescue procedure and request an alternative point. If the rescue procedure fails, the solver will exit with ${\mathbf{ifail}}={\mathbf{17}}$.
 ${\mathbf{inform}}=2$
 The solver will cleanly exit with ${\mathbf{ifail}}={\mathbf{20}}$ and return the best available point as well as the solve statistics.

6:
$\mathbf{iuser}\left(*\right)$ – Integer array
User Workspace

7:
$\mathbf{ruser}\left(*\right)$ – Real (Kind=nag_wp) array
User Workspace

8:
$\mathbf{cpuser}$ – Type (c_ptr)
User Workspace

objfun is called with the arguments
iuser,
ruser and
cpuser as supplied to
e04fff. You should use the arrays
iuser and
ruser, and the data handle
cpuser to supply information to
objfun.
objfun must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which
e04fff is called. Arguments denoted as
Input must
not be changed by this procedure.
Note: objfun should not return floatingpoint NaN (Not a Number) or infinity values, since these are not handled by
e04fff. If your code inadvertently
does return any NaNs or infinities,
e04fff is likely to produce unexpected results.

3:
$\mathbf{monit}$ – Subroutine, supplied by the NAG Library or the user.
External Procedure

monit is provided to enable you to monitor the progress of the optimization and, if necessary, to halt the optimization process.
If no monitoring is required,
monit may be the dummy subroutine
e04ffu supplied in the NAG Library.
monit is called at the end of every
${i}^{\mathrm{th}}$ step where
$i$ is controlled by the optional parameter
DFO Monitor Frequency (default value
$0$,
monit is never called).
The specification of
monit is:
Fortran Interface
Integer, Intent (In) 
:: 
nvar 
Integer, Intent (Inout) 
:: 
inform, iuser(*) 
Real (Kind=nag_wp), Intent (In) 
:: 
x(nvar), rinfo(100), stats(100) 
Real (Kind=nag_wp), Intent (Inout) 
:: 
ruser(*) 
Type (c_ptr), Intent (In) 
:: 
cpuser 

C++ Header Interface
#include <nag.h> extern "C" {
}


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

On entry:
$n$, the number of variables in the problem, as set during the initialization of the handle by
e04raf.

2:
$\mathbf{x}\left({\mathbf{nvar}}\right)$ – Real (Kind=nag_wp) array
Input

On entry: the current best point.

3:
$\mathbf{inform}$ – Integer
Input/Output

On entry: a nonnegative value.
On exit: may be used to request the solver to stop immediately. Specifically, if
${\mathbf{inform}}<0$, then the value of
rx will be discarded and the solver will terminate immediately with
${\mathbf{ifail}}={\mathbf{20}}$ otherwise, the solver will proceed normally.

4:
$\mathbf{rinfo}\left(100\right)$ – Real (Kind=nag_wp) array
Input

On entry: best objective value computed and various indicators (the values are as described in the main argument
rinfo).

5:
$\mathbf{stats}\left(100\right)$ – Real (Kind=nag_wp) array
Input

On entry: solver statistics at monitoring steps or at the end of the current iteration (the values are as described in the main argument
stats).

6:
$\mathbf{iuser}\left(*\right)$ – Integer array
User Workspace

7:
$\mathbf{ruser}\left(*\right)$ – Real (Kind=nag_wp) array
User Workspace

8:
$\mathbf{cpuser}$ – Type (c_ptr)
User Workspace

monit is called with the arguments
iuser,
ruser and
cpuser as supplied to
e04fff. You should use the arrays
iuser and
ruser, and the data handle
cpuser to supply information to
monit.
monit must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which
e04fff is called. Arguments denoted as
Input must
not be changed by this procedure.

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

On entry:
$n$, the number of variables in the problem. It must be unchanged from the value set during the initialization of the handle by
e04raf.
Constraint:
${\mathbf{nvar}}\ge 1$.

5:
$\mathbf{x}\left({\mathbf{nvar}}\right)$ – Real (Kind=nag_wp) array
Input/Output

On entry: ${x}_{0}$, the initial estimates of the variables $x$.
On exit: the final values of the variables $x$.

6:
$\mathbf{nres}$ – Integer
Input

On entry:
${m}_{r}$, the number of residuals in the problem. It must be unchanged from the value set during the definition of the objective structure by
e04rmf.
Constraint:
${\mathbf{nres}}\ge 0$.

7:
$\mathbf{rx}\left({\mathbf{nres}}\right)$ – Real (Kind=nag_wp) array
Output

On exit: the values of the residuals at the final point given in
x.

8:
$\mathbf{rinfo}\left(100\right)$ – Real (Kind=nag_wp) array
Output

On exit: optimal objective value and various indicators at monitoring steps or at the end of the final iteration. The measures are given in the table below:
$1$ 
Objective function value $f\left(x\right)$ (sum of the squared residuals). 
$2$ 
$\rho $, the current lower bound of the trust region. 
$3$ 
$\Delta $, the current size of the trust region. 
$4$ 
The number of interpolation points used by the solver. 
$5100$ 
Reserved for future use. 

9:
$\mathbf{stats}\left(100\right)$ – Real (Kind=nag_wp) array
Output

On exit: solver statistics at monitoring steps or at the end of the final iteration as given in the table below:
$1$ 
Number of calls to the objective function. 
$2$ 
Total time spent in the solver (including time spent evaluating the objective). 
$3$ 
Total time spent evaluating the objective function. 
$4$ 
Number of steps. 
$5100$ 
Reserved for future use. 

10:
$\mathbf{iuser}\left(*\right)$ – Integer array
User Workspace

11:
$\mathbf{ruser}\left(*\right)$ – Real (Kind=nag_wp) array
User Workspace

12:
$\mathbf{cpuser}$ – Type (c_ptr)
User Workspace

iuser,
ruser and
cpuser are not used by
e04fff, but are passed directly to
objfun and
monit and may be used to pass information to these routines. If you do not need to reference
cpuser, it should be initialized to
c_null_ptr.

13:
$\mathbf{ifail}$ – Integer
Input/Output

On entry:
ifail must be set to
$0$,
$1$ or
$1$ to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of $0$ causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of $1$ means that an error message is printed while a value of $1$ means that it is not.
If halting is not appropriate, the value
$1$ or
$1$ is recommended. If message printing is undesirable, then the value
$1$ is recommended. Otherwise, the value
$1$ is recommended since useful values can be provided in some output arguments even when
${\mathbf{ifail}}\ne {\mathbf{0}}$ on exit.
When the value $\mathbf{1}$ 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).
6
Error Indicators and Warnings
If on entry
${\mathbf{ifail}}=0$ or
$1$, explanatory error messages are output on the current error message unit (as defined by
x04aaf).
Errors or warnings detected by the routine:
Note: in some cases e04fff may return useful information.
 ${\mathbf{ifail}}=1$

The supplied
handle does not define a valid handle to the data structure for the NAG optimization modelling suite. It has not been initialized by
e04raf or it has been corrupted.
 ${\mathbf{ifail}}=2$

The problem is already being solved.
This solver does not support the model defined in the handle.
 ${\mathbf{ifail}}=4$

The information supplied does not match with that previously stored.
On entry,
${\mathbf{nres}}=\u2329\mathit{\text{value}}\u232a$ must match that given during the definition of the objective in the
handle, i.e.,
$\u2329\mathit{\text{value}}\u232a$.
The information supplied does not match with that previously stored.
On entry,
${\mathbf{nvar}}=\u2329\mathit{\text{value}}\u232a$ must match that given during initialization of the
handle, i.e.,
$\u2329\mathit{\text{value}}\u232a$.
 ${\mathbf{ifail}}=5$

Inconsistent optional parameters
DFO Trust Region Tolerance ${\rho}_{\mathrm{end}}$ and
DFO Trust Region Slow Tol ${\rho}_{\mathrm{tol}}$.
Constraint:
${\rho}_{\mathrm{end}}<{\rho}_{\mathrm{tol}}$.
Use
e04zmf to set compatible option values.
Inconsistent optional parameters
DFO Trust Region Tolerance ${\rho}_{\mathrm{end}}$ and
DFO Starting Trust Region ${\rho}_{\mathrm{beg}}$.
Constraint:
${\rho}_{\mathrm{end}}<{\rho}_{\mathrm{beg}}$.
Use
e04zmf to set compatible option values.
Optional parameter
DFO Starting Trust Region ${\rho}_{\mathrm{beg}}=\u2329\mathit{\text{value}}\u232a$,
${l}_{x}\left(i\right)=\u2329\mathit{\text{value}}\u232a$,
${u}_{x}\left(i\right)=\u2329\mathit{\text{value}}\u232a$ and
$i=\u2329\mathit{\text{value}}\u232a$.
Constraint: if
${l}_{x}\left(i\right)\ne {u}_{x}\left(i\right)$ in coordinate
$i$, then
${u}_{x}\left(i\right){l}_{x}\left(i\right)\ge 2\times {\rho}_{\mathrm{beg}}$.
Use
e04zmf to set compatible option values.
 ${\mathbf{ifail}}=6$

Initial number of interpolation points
$\mathit{ninit}=\u2329\mathit{\text{value}}\u232a$, total number of interpolation points
$\mathit{npts}=\u2329\mathit{\text{value}}\u232a$, number of variables
$\mathit{nvar}=\u2329\mathit{\text{value}}\u232a$.
Constraint: growing interpolation set is only supported for linear models (
$\mathit{npts}=\mathit{nvar}+1$).
Use
DFO Number Interp Points and
DFO Number Initial Points to control the number of interpolation points.
The number of initial interpolation points is greater than the maximum.
Use
DFO Number Interp Points and
DFO Number Initial Points to control the number of interpolation points.
There were
${n}_{r}=\u2329\mathit{\text{value}}\u232a$ unequal bounds and the optional parameter
DFO Number Interp Points $\mathit{npt}=\u2329\mathit{\text{value}}\u232a$.
Constraint:
${n}_{r}+1\le \mathit{npt}\le \frac{\left({n}_{r}+1\right)\times \left({n}_{r}+2\right)}{2}$.
Use
e04zmf to set compatible option values.
 ${\mathbf{ifail}}=8$

Maximization is not possible for a nonlinear least squares problem.
${\mathbf{nres}}=0$. There are no residuals, the objective function is empty.
 ${\mathbf{ifail}}=17$

Rescue failed: the trust region could not be reduced further after some function evaluation could not be provided. Check the specification of your objective and whether it needs rescaling. Try a different initial
x.
Some initial interpolation points were not provided. Rescue cannot be attempted at this stage.
Check the specification of your objective and whether it needs rescaling. Try a different initial
x.
 ${\mathbf{ifail}}=18$

The predicted reduction in a trust region step was nonpositive. Check your specification of
objfun and whether the function needs rescaling. Try a different initial
x.
 ${\mathbf{ifail}}=19$

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 progress could be made. Check your specification of
objfun and whether the function needs rescaling. Try a different initial
x.
 ${\mathbf{ifail}}=20$

User requested termination after a call to the objective function.
inform was set to a value lower than
$1$ within the usersupplied function
objfun.
User requested termination during a monitoring step.
inform was set to a value lower than
$0$ within the usersupplied function
monit.
 ${\mathbf{ifail}}=21$

Maximum number of function evaluations exceeded.
 ${\mathbf{ifail}}=23$

The solver terminated after the maximum time allowed was exceeded.
Maximum number of seconds exceeded. Use optional parameter
Time Limit to reset the limit.
 ${\mathbf{ifail}}=24$

No progress, the solver was stopped after
$\u2329\mathit{\text{value}}\u232a$ consecutive slow steps.
Use the optional parameter
DFO Maximum Slow Steps to modify the maximum number of slow steps accepted.
The solver stopped after
$5\times {\mathbf{DFO\; Maximum\; Slow\; Steps}}$ consecutive slow steps and a trust region above the tolerance set by
DFO Trust Region Slow Tol.
 ${\mathbf{ifail}}=50$

The problem was solved to an acceptable level after
$\u2329\mathit{\text{value}}\u232a$ consecutive slow iterations.
Use the optional parameter
DFO Maximum Slow Steps to modify the maximum number of slow steps accepted.
The solver stopped after
DFO Maximum Slow Steps consecutive slow steps and a trust region below the tolerance set by
DFO Trust Region Slow Tol.
 ${\mathbf{ifail}}=99$
An unexpected error has been triggered by this routine. Please
contact
NAG.
See
Section 7 in the Introduction to the NAG Library FL Interface for further information.
 ${\mathbf{ifail}}=399$
Your licence key may have expired or may not have been installed correctly.
See
Section 8 in the Introduction to the NAG Library FL Interface for further information.
 ${\mathbf{ifail}}=999$
Dynamic memory allocation failed.
See
Section 9 in the Introduction to the NAG Library FL Interface for further information.
7
Accuracy
In a nonnoisy case, the solver can declare convergence on two conditions.

(i)The trust region radius is below the tolerance ${\rho}_{\mathrm{end}}$ set by the optional parameter DFO Trust Region Tolerance. When this condition is met, the corresponding solution will generally be at a distance smaller than $10\times {\rho}_{\mathrm{end}}$ of a local minimum.

(ii)The sum of the square of the residuals is below the tolerance set by the optional parameter DFLS Small Residuals Tol. In a data fitting context, this condition means that the error between the observed data and the model is smaller than the requested tolerance.
If the objective is declared as noisy by the optional parameter
DFO Noisy Problem, the solver declares convergence more conservatively. Instead of stopping with the first condition, the solver will trigger soft restarts (see
Section 11 for more details) to ensure it did not get stuck in a flat region because of the noise. The solver then declares convergence when it is reasonably sure that it has reached a local minimum.

(i)The total number of restarts is greater than the limit set by optional parameter DFO Max Soft Restarts and the trust region radius is below the tolerance.

(ii)The number of consecutive restarts that did not manage to decrease the objective function is greater than the limit set by the optional parameter DFO Max Unsucc Soft Restarts.
In addition, this solver can stop if the convergence is deemed too slow on two conditions.

(i)The trust region lower bound is lower than the value set by the optional parameter DFO Trust Region Slow Tol and the number of consecutive slow steps is greater than the value set by DFO Maximum Slow Steps.

(ii)The trust region lower bound is greater than the value set by the optional parameter DFO Trust Region Slow Tol and the number of consecutive slow steps is greater than five times the value set by DFO Maximum Slow Steps.
The slow convergence detection can be deactivated by setting
DFO Maximum Slow Steps to
$0$.
8
Parallelism and Performance
e04fff is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
e04fff 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.
9.1
Description of the Printed Output
The solver can print information to give an overview of the problem and the progress of the computation. The output may be sent to two independent
unit numbers
which are set by optional parameters
Print File and
Monitoring File. Optional parameters
Print Level,
Print Options,
Monitoring Level and
Print Solution determine the exposed level of detail. This allows, for example, a detailed log file to be generated while the condensed information is displayed on the screen.
By default (${\mathbf{Print\; File}}=6$, ${\mathbf{Print\; Level}}=2$), four sections are printed to the standard output: a header, a list of options, an iteration log and a summary.
Header
The header contains statistics about the problem. It should look like:

E04F(GF)), Derivativefree solver for data fitting
(nonlinear least squares problems)

Problem statistics
Number of variables 10
Number of unconstrained variables 10
Number of fixed variables 0
Starting interpolation points 11
Total interpolation points 11
Number of residuals 10
Optional parameters list
If
${\mathbf{Print\; Options}}=\mathrm{YES}$, a list of the optional parameters and their values is printed. The list shows all options of the solver, each displayed on one line. The line contains the option name, its current value and an indicator for how it was set. The options left at their defaults are noted by ‘d’ and the ones you have set are noted by ‘U’. Note that the output format is compatible with the file format expected by
e04zpf. The output looks as follows:
Stats Time = Yes * U
Dfo Trust Region Tolerance = 1.00000E07 * U
Dfo Max Objective Calls = 500 * d
Dfo Starting Trust Region = 1.10000E01 * U
Dfo Number Interp Points = 0 * d
Iteration log
If
${\mathbf{Print\; Level}}\ge 2$, the solver will print a summary line for each step. An iteration is considered successful when it yields a decrease of the objective sufficiently close to the decrease predicted by the quadratic model. Each line shows the step number (step), the value of the objective function (obj), the lower bound on the radius of the trust region (rho), and the cumulative number of objective function evaluations (nf). The output looks as follows:

step  obj rho  nf 

1  3.87E+01 1.00E01  12 
2  3.39E+01 1.00E01  13 
3  1.78E+01 1.00E01  14 
4  3.95E29 1.00E01  15 
Occasionally, the letter ‘s’ is printed at the end of the line indicating that the progress is considered slow by the slow convergence detection heuristic. After a certain number of consecutive slow steps, the solver is stopped. The limit on the number of slow iterations can be controlled by the optional parameter
DFO Maximum Slow Steps and the tolerance on the trust region radius before the solver can be stopped is driven by
DFO Trust Region Slow Tol.
If
${\mathbf{Print\; Level}}\ge 3$, each line additionally shows the current value of the trust region radius (delta) as well as the step length (d) taken. It might look as follows:

step  obj rho delta d  nf 

1  4.02E+00 1.00E01 4.00E01 1.00E01  4 
2  3.66E+00 1.00E01 4.00E01 4.00E01  5 
3  3.48E+00 1.00E01 4.00E01 4.00E01  6 
4  2.32E+00 1.00E01 4.00E01 1.00E01  9 
Summary
Once the solver finishes, a summary is produced:
Status: Converged, small residuals
Value of the objective 3.95417E29
Number of objective function evaluations 15
Number of steps 4
Note that only the iterations that decrease the objective function are printed in the iteration log, meaning that objective evaluations are likely to happen between the last printed iteration and the convergence. This leads to a small difference between the last line of the iteration log and the final summary in terms of the number of function evaluations.
Optionally, if
${\mathbf{Stats\; Time}}=\mathrm{YES}$, the timings are printed:
Timings
Total time spent in the solver 0.056
Time spent in the objective evaluation 0.012
Additionally, if
${\mathbf{Print\; Solution}}=\mathrm{YES}$, the solution is printed along with the bounds:
Computed Solution:
idx Lower bound Value Upper bound
1 inf 1.00000E+00 inf
2 inf 1.00000E+00 inf
3 inf 1.00000E+00 inf
4 inf 1.00000E+00 inf
9.2
Internal Changes
Internal changes have been made to this routine as follows:
 At Mark 27:
Even though the interface of
e04fff stays the same, the underlying algorithm underwent a complete overhaul, meaning the results obtained can differ significantly with those of the previous release. The new implementation generally provides better performances as well as:

•additional features to better deal with noisy problems (see Section 11.5)

•an option to start the optimization before the full interpolation set is computed (see Section 11.4).
An option to use the previous implementation instead of the new one has also been added: if
DFO Version is set to
$26$, the algorithm will behave the same way as in the Mark 26 release. The results may still vary slightly as the internal model optimization algorithm has been improved. When using the Mark 26 implementation, some optional parameter descriptions in the documentation may be slightly inaccurate, please refer to the Mark 26 documentation.
Some optional parameter names have also changed, namely the prefix ‘DFLS’ has been changed to ‘DFO’ for the options that are common between the derivative free leastsquare solvers (DFLS) and the derivative free solver for general nonlinear objective solvers. The old names still work but are not documented anymore.
The name of the argument ‘mon’ has been updated to
monit to be consistent with the rest of the NAG Optimization Suite routines.
For details of all known issues which have been reported for the NAG Library please refer to the
Known Issues.
10
Example
In this example, we minimize the Kowalik and Osborne function with bounds on some of the variables. In this problem, the number of variables
$n=4$ and the number of residuals
${m}_{r}=11$. The residuals
${r}_{i}$ are computed by
where
The following bounds are defined on the variables
10.1
Program Text
10.2
Program Data
None.
10.3
Program Results
11
Algorithmic Details
This section contains a short description of the algorithm used in
e04fff which is based on the collaborative work between NAG and the University of Oxford (
Cartis and Roberts (2017) and
Cartis et al. (2018)). It uses a modelbased derivativefree trust region framework adapted to exploit least squares problems structure.
11.1
Derivativefree Trust Region Algorithm
In this section, we are interested in generic problems of the form
where the derivatives of the objective function
$f$ are not easily available. A modelbased DFO algorithm maintains a set of points
${Y}_{k}$ centred on an iterate
${x}_{k}$ to build quadratic interpolation models of the objective
where
${g}_{k}$ and
${H}_{k}$ are built with the interpolation conditions
Note that if the number of interpolation points
$\mathit{npt}$ is smaller than
$\frac{\left({n}_{r}+1\right)\times \left({n}_{r}+2\right)}{2}$, the model chosen is the one for which the Hessian
${H}_{k}$ is the closest to
${H}_{k1}$ in the Frobenius norm sense.
This model is iteratively optimized over a trust region, updated and moved around the new computed points. More precisely, it can be described as:
 DFO Algorithm


1.Initialization
Choose an initial interpolation set ${Y}_{0}$, trust region radius ${\rho}_{\mathrm{beg}}$ and build the first quadratic model ${\varphi}_{0}$.

2.Iteration k

(i)Minimize the model in the trust region to obtain a step ${s}_{k}$.

(ii)If the step is too small, adjust the geometry of the interpolation set and the trust region size ${\rho}_{k}$ and restart the iteration.

(iii)Evaluate the objective at the new point ${x}_{k}+{s}_{k}$.

(iv)Replace a far away point from ${Y}_{k}$ by ${x}_{k}+{s}_{k}$ to obtain ${Y}_{k+1}$.

(v)If the decrease of the objective is sufficient (successful step), choose ${x}_{k+1}={x}_{k}+{s}_{k}$, else choose ${x}_{k+1}={x}_{k}$.

(vi)Choose ${\rho}_{k+1}$ and adjust the geometry of ${Y}_{k+1}$, if necessary.

(vii)Build ${\varphi}_{k+1}$ using the new interpolation set.

(viii)Stop the algorithm if ${\rho}_{k+1}$is below the chosen tolerance ${\rho}_{\mathrm{end}}$.
In the following sections, we call an iteration ‘successful’ when the trial point ${x}_{k}+{s}_{k}$ is accepted as the next iterate.
11.2
Bounds on the Variables
The bounds on the variables are handled during the model optimization step (step
2(i) of
DFO Algorithm) with an active set method. If a bound is hit, it is fixed and step
2(i) is restarted.
11.3
Adaptation to Nonlinear Least Squares Problems
In the specific case where
$f$ is a sum of square
$f\left(x\right)={\displaystyle \sum _{i=1}^{{m}_{r}}}{{r}_{i}\left(x\right)}^{2}$, a good approximation of the Hessian of the objective can be
where
$J$ is the
${m}_{r}$ by
$n$ first derivative matrix of
$f$. This approximation is the main idea behind the Gauss–Newton and Levenberg–Marquardt methods. Following the work of
Zhang et al. (2010), it is possible to adapt it to the DFO framework. In
e04fff, one linear model is built for each residual
${r}_{i}$
Let
$J={\left({g}^{\left(1\right)},{g}^{\left(2\right)},\dots \right)}^{\mathrm{T}}$. To build the model of the objective
$f$, we then choose
where
${g}_{f}$ is chosen as
and
${H}_{f}$ as
The first expression amounts to making a Gauss–Newton approximation when we are far from a stationary point and the second to a Levenberg–Marquardt approximation when we are close to a stationary point with small residuals.
e04fff integrates this method of building models into the framework presented in the
DFO Algorithm.
11.4
Growing the Interpolation Set
In the case where the function is very expensive, it might be desirable for the solver to make some progress before the
${n}_{r}+1$ evaluations necessary to build the first interpolation model are done. To get that behaviour, you can set the optional parameter
DFO Number Initial Points, controlling the number of initial interpolation points, to a value that is lower than
${n}_{r}+1$. The solver will then start its iteration earlier while adding random perturbations to the interpolation models to ensure that the full space is explored.
It is to be noted that this mode will typically not lead to a faster convergence to the solution and should only be used if early progress is desirable.
11.5
Dealing with Noisy Problems
If the problem solved is known to be noisy, declaring it as such to the solver with the optional parameter
DFO Noisy Problem will modify the behaviour of the solver to take into account the uncertainty of the function evaluations. The two main features implemented to handle noisy objective functions are:

(i)slow update of the trust regions;

(ii)soft restarts of the algorithm can be performed instead of declaring convergence to ensure the solver did not get stuck in a flat region due to the noise.
A soft restart consists of a reset of the trust region's values to the starting ones and a few objective evaluations to improve the geometry of the interpolation set in the new trust region. It is possible to control the number of objective evaluations performed during a soft restart with the optional parameter
DFO Number Soft Restarts Pts. After a set maximum number of restarts (
DFO Max Soft Restarts) or maximum number of unsuccessful restarts (
DFO Max Unsucc Soft Restarts), the solver will declare convergence in the usual way.
12
Optional Parameters
Several optional parameters in e04fff define choices in the problem specification or the algorithm logic. In order to reduce the number of formal arguments of e04fff these optional parameters have associated default values that are appropriate for most problems. Therefore, you need only specify those optional parameters whose values are to be different from their default values.
The remainder of this section can be skipped if you wish to use the default values for all optional parameters.
The optional parameters can be changed by calling
e04zmf anytime between the initialization of the handle and the call to the solver. Modification of the optional parameters during intermediate monitoring stops is not allowed. Once the solver finishes, the optional parameters can be altered again for the next solve.
The option values may be retrieved by
e04znf.
The following is a list of the optional parameters available. A full description of each optional parameter is provided in
Section 12.1.
12.1
Description of the Optional Parameters
For each option, we give a summary line, a description of the optional parameter and details of constraints.
The summary line contains:
 the keywords, where the minimum abbreviation of each keyword is underlined;
 a parameter value,
where the letters $a$, $i$ and $r$ denote options that take character, integer and real values respectively;
 the default value, where the symbol $\epsilon $ is a generic notation for machine precision (see x02ajf).
All options accept the value $\mathrm{DEFAULT}$ to return single options to their default states.
Keywords and character values are case and white space insensitive.
This special keyword may be used to reset all optional parameters to their default values. Any value given with this keyword will be ignored.
DFLS Small Residuals Tol  $r$  Default $={\epsilon}^{0.75}$ 
This option defines the tolerance on the value of the residuals. Namely, the solver declares convergence if
Constraint: ${\mathbf{DFLS\; Small\; Residuals\; Tol}}>{\epsilon}^{2}$.
DFO Initial Interp Points  $a$  Default $=\mathrm{Coordinate}$ 
Determines how the initial interpolation points are chosen. If
${\mathbf{DFO\; Initial\; Interp\; Points}}=\mathrm{Coordinate}$, the interpolation points are chosen along the coordinate directions around the initial point. If
${\mathbf{DFO\; Initial\; Interp\; Points}}=\mathrm{Random}$, the initial interpolation points are chosen along random orthogonal directions around the initial point. Set
DFO Random Seed to a positive value to fix the random seed and get reproducible results.
Constraint: ${\mathbf{DFO\; Initial\; Interp\; Points}}=\mathrm{Coordinate}$ or $\mathrm{Random}$.
DFO Maximum Slow Steps  $i$  Default $=20$ 
If
${\mathbf{DFO\; Maximum\; Slow\; Steps}}>0$, this parameter defines the maximum number of consecutive slow iterations
${n}_{\mathrm{slow}}$ allowed. Set
${\mathbf{DFO\; Maximum\; Slow\; Steps}}=0$ to deactivate the slow iteration detection. The algorithm can stop in two situations:

(i)${n}_{\mathrm{slow}}>{\mathbf{DFO\; Maximum\; Slow\; Steps}}$ and $\rho <{\mathbf{DFO\; Trust\; Region\; Slow\; Tol}}$ with ${\mathbf{ifail}}={\mathbf{50}}$,

(ii)${n}_{\mathrm{slow}}>5\times {\mathbf{DFO\; Maximum\; Slow\; Steps}}$ with ${\mathbf{ifail}}={\mathbf{24}}$.
Constraint: ${\mathbf{DFO\; Maximum\; Slow\; Steps}}\ge 0$.
DFO Max Objective Calls  $i$  Default $=500$ 
A limit on the number of objective function evaluations the solver is allowed to compute. If the limit is reached, the solver stops with ${\mathbf{ifail}}={\mathbf{21}}$.
Constraint: ${\mathbf{DFO\; Max\; Objective\; Calls}}\ge 1$.
DFO Max Soft Restarts  $i$  Default $=5$ 
The maximum total number of soft restarts that can be performed if the objective function is declared as noisy (${\mathbf{DFO\; Noisy\; Problem}}=\mathrm{YES}$).
Constraint: ${\mathbf{DFO\; Max\; Soft\; Restarts}}\ge 1$.
DFO Max Unsucc Soft Restarts  $i$  Default $=3$ 
The maximum number of consecutive unsuccessful soft restarts that can be performed if the objective function is declared as noisy (${\mathbf{DFO\; Noisy\; Problem}}=\mathrm{YES}$).
Constraint: ${\mathbf{DFO\; Max\; Unsucc\; Soft\; Restarts}}\ge 1$.
DFO Monitor Frequency  $i$  Default $=0$ 
If
${\mathbf{DFO\; Monitor\; Frequency}}>0$,
monit will be called at the end of every
$i$th step for monitoring purposes.
Constraint: ${\mathbf{DFO\; Monitor\; Frequency}}\ge 0$.
DFO Noise Level  $r$  Default $=0.0$ 
Indicates the noise level expected when evaluating the objective function if ${\mathbf{DFO\; Noisy\; Problem}}=\mathrm{YES}$.
Constraint: ${\mathbf{DFO\; Noise\; Level}}\ge 0.0$.
DFO Noisy Problem  $a$  Default $=\mathrm{NO}$ 
Indicates if the function evaluations provided to the solver are noisy. If
${\mathbf{DFO\; Noisy\; Problem}}=\mathrm{YES}$, some algorithmic features will be activated:

(i)The trust region update becomes slower to reflect the decreased confidence in the objective values.

(ii)Soft restarts of the algorithm can be performed to ensure the algorithm did not get stuck because of the noise (see DFO Max Soft Restarts, DFO Max Unsucc Soft Restarts and DFO Number Soft Restarts Pts to control the restart characteristics).

(iii)In addition, if ${\mathbf{DFO\; Noise\; Level}}>0.0$, the solver will trigger a soft restart if all the function values are within the noise level.
DFO Number Initial Points  $i$  Default $=0$ 
The initial number of interpolation points in
${Y}_{0}$ (1) used to build the linear models of the residuals. If
${\mathbf{DFO\; Number\; Initial\; Points}}=0$, the number of points is chosen to be equal to the total number of interpolation points set by
DFO Number Interp Points.
If this parameter is chosen to be lower than the maximum set by
DFO Number Interp Points, the solver will progressively increase the number of interpolation points until it reaches that value. In this release, it is only possible to grow the interpolation set if
DFO Number Interp Points is set to the default value.
Constraint: ${\mathbf{DFO\; Number\; Initial\; Points}}\ge 0$.
Consistency constraint, the solver stops with
${\mathbf{ifail}}={\mathbf{6}}$ if not met:
 $0\le {\mathbf{DFO\; Number\; Initial\; Points}}\le {\mathbf{DFO\; Number\; Interp\; Points}}$.
 If ${\mathbf{DFO\; Number\; Initial\; Points}}<{\mathbf{DFO\; Number\; Interp\; Points}}$, DFO Number Interp Points must be set to the default value.
DFO Number Interp Points  $i$  Default $=0$ 
The maximum number of interpolation points in
${Y}_{k}$ (1) used to build the linear models of the residuals. If
${\mathbf{DFO\; Number\; Interp\; Points}}=0$, the number of points is chosen to be
${n}_{r}+1$ where
${n}_{r}$ is the number of nonfixed variables.
Constraint: ${\mathbf{DFO\; Number\; Interp\; Points}}\ge 0$.
Consistency constraint, the solver stops with
${\mathbf{ifail}}={\mathbf{6}}$ if not met:
 ${n}_{r}+1\le {\mathbf{DFO\; Number\; Interp\; Points}}\le \frac{\left({n}_{r}+1\right)\times \left({n}_{r}+2\right)}{2}$.
DFO Number Soft Restarts Pts  $i$  Default $=3$ 
The number of interpolation points that are replaced during a soft restart.
Constraint: ${\mathbf{DFO\; Number\; Soft\; Restarts\; Pts}}\ge 1$.
DFO Print Frequency  $i$  Default $=1$ 
If ${\mathbf{DFO\; Print\; Frequency}}>0$, the solver prints the iteration log to the appropriate units at the end of every $i$th step.
Constraint: ${\mathbf{DFO\; Print\; Frequency}}\ge 0$.
DFO Random Seed  $i$  Default $\text{}=1$ 
The random seed used to generate the random points used to build the initial model or build the underdetermined models when the interpolation set has not fully grown (${\mathbf{DFO\; Number\; Initial\; Points}}<{\mathbf{DFO\; Number\; Interp\; Points}}$). If ${\mathbf{DFO\; Random\; Seed}}<0$, the random seed will be based on values taken from the realtime clock, potentially resulting in the solver taking a different path each time it is run. Set it to a positive value to get fully reproducible runs.
Constraint: ${\mathbf{DFO\; Print\; Frequency}}\ge 1$.
DFO Starting Trust Region  $r$  Default $=0.1$ 
${\rho}_{\mathrm{beg}}$, the initial trust region radius. This parameter should be set to 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 ${\rho}_{\mathrm{beg}}$ along each coordinate direction. The default value assumes that the variables have an order of magnitude $1$.
Constraint: ${\mathbf{DFO\; Starting\; Trust\; Region}}>\epsilon $.
Consistency constraints, the solver stops with
${\mathbf{ifail}}={\mathbf{5}}$ if not met:
 ${\mathbf{DFO\; Starting\; Trust\; Region}}\le {\mathbf{DFO\; Trust\; Region\; Tolerance}}$.
 ${\mathbf{DFO\; Starting\; Trust\; Region}}\le \frac{1}{2}{\displaystyle \underset{i}{\mathrm{min}}}\phantom{\rule{0.25em}{0ex}}\left({u}_{x}\left(i\right){l}_{x}\left(i\right)\right)$.
DFO Trust Region Slow Tol  $r$  Default $\text{}={\epsilon}^{0.25}$ 
The minimal acceptable trust region radius for the solution to be declared as acceptable. The solver stops if:
 ${n}_{\mathrm{slow}}>{\mathbf{DFO\; Maximum\; Slow\; Steps}}$ and ${\rho}_{k}<{\mathbf{DFO\; Trust\; Region\; Slow\; Tol}}$.
Constraint: ${\mathbf{DFO\; Trust\; Region\; Slow\; Tol}}>\epsilon $.
Consistency constraint, the solver stops with
${\mathbf{ifail}}={\mathbf{5}}$ if not met:
 ${\mathbf{DFO\; Trust\; Region\; Slow\; Tol}}>{\mathbf{DFO\; Trust\; Region\; Tolerance}}$.
DFO Trust Region Tolerance  $r$  Default $={\epsilon}^{0.37}$ 
${\rho}_{\mathrm{end}}$, the requested trust region radius. The algorithm declares convergence when the trust region radius reaches this limit. It should indicate the absolute accuracy that is required in the final values of the variables.
Constraint: ${\mathbf{DFO\; Trust\; Region\; Tolerance}}>\epsilon $.
Consistency constraints, the solver stops with
${\mathbf{ifail}}={\mathbf{5}}$ if not met:
 ${\mathbf{DFO\; Starting\; Trust\; Region}}>{\mathbf{DFO\; Trust\; Region\; Tolerance}}$.
 ${\mathbf{DFO\; Trust\; Region\; Slow\; Tol}}>{\mathbf{DFO\; Trust\; Region\; Tolerance}}$.
DFO Version  $a$  Default $=\mathrm{Latest}$ 
At Mark 27, the underlying algorithm of e04fff underwent significant changes. This option allows you to continue using the Mark 26 version if it is set to '$\mathrm{26}$'. By default (recommended), the latest version of the code is called.
Constraint: ${\mathbf{DFO\; Version}}=\mathrm{Latest}$ or $\mathrm{26}$.
Infinite Bound Size  $r$  Default $\text{}={10}^{20}$ 
This defines the ‘infinite’ bound $\mathit{bigbnd}$ in the definition of the problem constraints. Any upper bound greater than or equal to $\mathit{bigbnd}$ will be regarded as $+\infty $ (and similarly any lower bound less than or equal to $\mathit{bigbnd}$ will be regarded as $\infty $). Note that a modification of this optional parameter does not influence constraints which have already been defined; only the constraints formulated after the change will be affected.
Constraint: ${\mathbf{Infinite\; Bound\; Size}}\ge 1000$.
Monitoring File  $i$  Default $\text{}=1$ 
If
$i\ge 0$, the
unit number
for the secondary (monitoring) output. If
${\mathbf{Monitoring\; File}}=1$, no secondary output is provided. The information output to this unit is controlled by
Monitoring Level.
Constraint: ${\mathbf{Monitoring\; File}}\ge 1$.
Monitoring Level  $i$  Default $=4$ 
This parameter sets the amount of information detail that will be printed by the solver to the secondary output. The meaning of the levels is the same as with
Print Level.
Constraint: $0\le {\mathbf{Monitoring\; Level}}\le 5$.
Print File  $i$  Default
$=\text{advisory message unit number}$

If
$i\ge 0$, the
unit number
for the primary output of the solver. If
${\mathbf{Print\; File}}=1$, the primary output is completely turned off independently of other settings. The default value is the advisory message unit number as defined by
x04abf at the time of the optional parameters initialization, e.g., at the initialization of the handle. The information output to this unit is controlled by
Print Level.
Constraint: ${\mathbf{Print\; File}}\ge 1$.
Print Level  $i$  Default $=2$ 
This parameter defines how detailed information should be printed by the solver to the primary and secondary output.
$i$ 
Output 
$0$ 
No output from the solver. 
$1$ 
The Header and Summary. 
$2$, $3$, $4$, $5$ 
Additionally, the Iteration log. 
Constraint: $0\le {\mathbf{Print\; Level}}\le 5$.
Print Options  $a$  Default $=\mathrm{YES}$ 
If ${\mathbf{Print\; Options}}=\mathrm{YES}$, a listing of optional parameters will be printed to the primary output and is always printed to the secondary output.
Constraint: ${\mathbf{Print\; Options}}=\mathrm{YES}$ or $\mathrm{NO}$.
Print Solution  $a$  Default $=\mathrm{NO}$ 
If ${\mathbf{Print\; Solution}}=\mathrm{YES}$, the solution will be printed to the primary and secondary output.
Constraint: ${\mathbf{Print\; Solution}}=\mathrm{YES}$ or $\mathrm{NO}$.
Stats Time  $a$  Default $=\mathrm{NO}$ 
This parameter turns on timings of various parts of the algorithm to give a better overview of where most of the time is spent. This might be helpful for a choice of different solving approaches. It is possible to choose between CPU and wall clock time. Choice $\mathrm{YES}$ is equivalent to $\mathrm{WALL\; CLOCK}$.
Constraint: ${\mathbf{Stats\; Time}}=\mathrm{YES}$, $\mathrm{NO}$, $\mathrm{CPU}$ or $\mathrm{WALL\; CLOCK}$.
Time Limit  $r$  Default $\text{}={10}^{6}$ 
A limit to the number of seconds that the solver can use to solve one problem. If during the convergence check this limit is exceeded, the solver will terminate with ${\mathbf{ifail}}={\mathbf{23}}$.
Constraint: ${\mathbf{Time\; Limit}}>0$.