e04jd: FL CL AD

NAG CL Interface
e04jdc (handle_solve_dfno)

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.

Keyword Search:

NAG Library Manual, Mark 27

Interfaces: FL CL AD

NAG CL Interface Introduction

E04 (Opt) Chapter Contents

E04 (Opt) Chapter Introduction

e04jd: FL CL AD

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

▸▿ 9 Further Comments

9.1 Description of the Printed Output

▸▿ 10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

▸▿ 11 Algorithmic Details

11.1 Derivative-free Trust Region Algorithm

11.2 Bounds on the Variables

11.3 Dealing with Noisy Problems

▸▿ 12 Optional Parameters

12.1 Description of the Optional Parameters

1 Purpose

e04jdc is a forward communication Derivative-free Optimization (DFO) solver from the NAG optimization modelling suite (DFNO) for small to medium-scale nonlinear problems with bound constraints.

2 Specification

#include <nag.h>

void

e04jdc (void *handle,

void	(objfun)(Integer nvar, const double x[], double fx, Integer inform, Nag_Comm comm),

void	(monit)(Integer nvar, const double x[], Integer inform, const double rinfo[], const double stats[], Nag_Comm *comm),

Integer nvar, double x[], double rinfo[], double stats[], Nag_Comm *comm, NagError *fail)

The function may be called by the names: e04jdc or nag_opt_handle_solve_dfno.

3 Description

e04jdc is aimed at minimizing a nonlinear objective function subject to bound constraints:

\begin{array}{l} \underset{x \in ℝ^{n}}{minimize} & f (x) \\ subject to & l_{x} \leq x \leq u_{x} . \end{array}

Here

f

is a smooth nonlinear function and

l_{x}

and

u_{x}

are

n

-dimensional vectors defining bounds on the variables.

e04jdc serves as a solver for compatible problems stored as a handle. The handle points to an internal data structure which defines the problem and serves as a means of communication for functions in the NAG optimization modelling suite. To define a compatible problem handle, you must call e04rac followed by e04rgc to initialize it and optionally call e04rhc to define bounds on the variables. If e04rhc is not called, all the variables will be considered free by the solver. It should be noted that e04jdc always assumes that the gradient of the objective is dense, therefore defining a sparse structure for the residuals in the call to e04rgc will have no effect. See Section 4.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 non-fixed variable $x_{i}$ , the value of $u_{x} (i) - l_{x} (i)$ 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 derivative-free trust region framework. This type of method is well suited for small to medium-scale 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 e04zmc and e04zpc at any time between the initialization of the handle by e04rac and a call to the solver. The optional parameters' names specific for this solver start either with the prefix DFO (Derivative-free Optimization) or DFNO (Derivative-free Nonlinear Optimization). 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

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 e04jdc is the same as the one used by e04jec. e04jdc serves as a forward communication interface to the derivative-free solver for nonlinear objective functions.

4 References

Cartis C, Fiala J, Marteau B and Roberts L (2018) Improving the Flexibility and Robustness of Model-Based Derivative-Free Optimization Solvers Technical Report University of Oxford

Conn A R, Scheinberg K and Vicente L N (2009) Introduction to Derivative-Free Optimization, vol. 8 of MPS-SIAM 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

5 Arguments

1: $handle$ – void * Input

On entry: the handle to the problem. It needs to be initialized by e04rac and the objective must be declared as nonlinear least squares by a call to the function e04rgc. The function e04rhc can optionally be called to define box bounds. It must not be changed between calls to the NAG optimization modelling suite.

2: $objfun$ – function, supplied by the user External Function

objfun calculates the value of the objective function

f (x)

at a specified point

x

The specification of objfun is:

void	objfun (Integer nvar, const double x[], double fx, Integer inform, Nag_Comm *comm)

1: $nvar$ – Integer Input

On entry:

n

, the number of variables in the problem.

2: $x [nvar]$ – const double Input

On entry:

x

, the vector of variable values at which the objective function is to be evaluated.

3: $fx$ – double * Output

On exit: the value of the objective function at

x

4: $inform$ – Integer * Input/Output

On entry: a non-negative value.

On exit: may be used to indicate that the requested objective value could not be computed. Specifically, it can be set to a negative value:

$inform = - 1$: The solver will attempt a rescue procedure and request an alternative point. If the rescue procedure fails, the solver will exit with $fail . code =$ NE_RESCUE_FAILED.
$inform = - 2$: The solver will cleanly exit with $fail . code =$ NE_USER_STOP and return the best available point as well as the solve statistics.

5: $comm$ – Nag_Comm *

Pointer to structure of type Nag_Comm; the following members are relevant to objfun.

user – double *
iuser – Integer *
p – Pointer: The type Pointer will be void *. Before calling e04jdc you may allocate memory and initialize these pointers with various quantities for use by objfun when called from e04jdc (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).

3: $monit$ – function, supplied by the user External Function

monit is provided to enable you to monitor the progress of the optimization and optionally to terminate the solver early if necessary, using argument inform. It is invoked at the end of every

i

th iteration where

i

is given by the

DFO Monitor Frequency

(the default is

0

, monit is not called).

If no monitoring is required, monit may be specified as NULLFN.

The specification of monit is:

void	monit (Integer nvar, const double x[], Integer inform, const double rinfo[], const double stats[], Nag_Comm comm)

1: $nvar$ – Integer Input

On entry:

n

, the number of variables in the problem.

2: $x [nvar]$ – const double Input

On entry:

x

, the vector of decision variables at the current iteration.

3: $inform$ – Integer * Input/Output

On entry: a non-negative value.

On exit: may be used to request the solver to stop immediately. Specifically, if

inform < 0

, then the solver will terminate immediately with

fail . code =

NE_USER_STOP. Otherwise, the solver will proceed normally.

4: $rinfo [100]$ – const double Input

On entry: error measures and various indicators at the end of the current iteration as described in the main argument rinfo.

5: $stats [100]$ – const double 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: $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 e04jdc you may allocate memory and initialize these pointers with various quantities for use by monit when called from e04jdc (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).

4: $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 e04rac.

Constraint:

nvar \geq 1

5: $x [nvar]$ – double Input/Output

On entry:

x_{0}

, the initial estimates of the variables

x

On exit: the final values of the variables

x

6: $rinfo [100]$ – double 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:

$0$	Objective function value $f (x)$ .
$1$	$ρ$ , the current lower bound of the trust region.
$2$	$Δ$ , the current size of the trust region.
$3$	The number of interpolation points used by the solver.
$4 - 99$	Reserved for future use.

7: $stats [100]$ – double Output

On exit: solver statistics at monitoring steps or at the end of the final iteration as given in the table below:

$0$	Number of calls to the objective function.
$1$	Total time spent in the solver (including time spent evaluating the objective).
$2$	Total time spent evaluating the objective function.
$3$	Number of steps.
$4 - 99$	Reserved for future use.

8: $comm$ – Nag_Comm *

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

9: $fail$ – NagError * Input/Output

The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).

6 Error Indicators and Warnings

NE_ALLOC_FAIL: Dynamic memory allocation failed.
See Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
NE_BAD_PARAM: On entry, argument $〈value〉$ had an illegal value.
NE_FAILED_START: The solver failed at the model building phase and the maximum number of restarts was reached. Check the specification of your objective and whether it needs rescaling. Try a different initial x.
NE_HANDLE: The supplied handle does not define a valid handle to the data structure for the NAG optimization modelling suite. It has not been initialized by e04rac or it has been corrupted.
NE_INT: The number of initial interpolation points is different from the total set by $DFO Number Interp Points$ .
Growing the interpolation set is not supported for this solver.

There were $n_{r} = 〈value〉$ unequal bounds and the optional parameter $DFO Number Interp Points$ $npt = 〈value〉$ .
Constraint: $n_{r} + 1 \leq npt \leq \frac{(n_{r} + 1) \times (n_{r} + 2)}{2}$ .
Use e04zmc to set compatible option values.
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_MAYBE_UNBOUNDED: The problem seems to be unbounded.
The unboundedness detection heuristic can be turned off with the option $DFNO Detect Unbounded$ .
NE_NO_IMPROVEMENT: No progress, the solver was stopped after $〈value〉$ 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 DFO Maximum Slow Steps$ consecutive slow steps and a trust region above the tolerance set by $DFO Trust Region Slow Tol$ .
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_PHASE: The problem is already being solved.
NE_REAL_2: Inconsistent optional parameters $DFO Trust Region Tolerance$ $ρ_{end}$ and $DFO Trust Region Slow Tol$ $ρ_{tol}$ .
Constraint: $ρ_{end} < ρ_{tol}$ .
Use e04zmc to set compatible option values.

Inconsistent optional parameters $DFO Trust Region Tolerance$ $ρ_{end}$ and $DFO Starting Trust Region$ $ρ_{beg}$ .
Constraint: $ρ_{end} < ρ_{beg}$ .
Use e04zmc to set compatible option values.

Optional parameter $DFO Starting Trust Region$ $ρ_{beg} = 〈value〉$ , $l_{x} (i) = 〈value〉$ , $u_{x} (i) = 〈value〉$ and $i = 〈value〉$ .
Constraint: if $l_{x} (i) \neq u_{x} (i)$ in coordinate $i$ , then $u_{x} (i) - l_{x} (i) \geq 2 \times ρ_{beg}$ .
Use e04zmc to set compatible option values.
NE_REF_MATCH: The information supplied does not match with that previously stored.
On entry, $nvar = 〈value〉$ must match that given during initialization of the handle, i.e., $〈value〉$ .
NE_RESCUE_FAILED: 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 could not be provided. Rescue cannot be attempted at this stage.
Check the specification of your objective and whether it needs rescaling. Try a different initial x.
NE_SETUP_ERROR: This solver does not support the model defined in the handle.
NE_TIME_LIMIT: The solver terminated after the maximum time allowed was exceeded.
Maximum number of seconds exceeded. Use optional parameter $Time Limit$ to reset the limit.
NE_TOO_MANY_ITER: Maximum number of function evaluations exceeded.
NE_TR_STEP_FAILED: The predicted reduction in a trust region step was non-positive. Check the specification of your objective and whether it needs rescaling. Try a different initial x.
NE_USER_STOP: User requested termination after a call to the objective function. inform was set to a value lower than $- 1$ within the user-supplied function objfun.

User requested termination during a monitoring step. inform was set to a value lower than $0$ within the user-supplied function monit.
NW_NOT_CONVERGED: The problem was solved to an acceptable level after $〈value〉$ 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$ .

7 Accuracy

In a non-noisy case, the solver can declare convergence on two conditions.

(i)The trust region radius is below the tolerance $ρ_{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 ρ_{end}$ of a local minimum.
(ii)The objective value is lower than the optional parameter $DFNO Objective Limit$ . This criterion is only used if you have set a limit.

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

0

8 Parallelism and Performance

e04jdc is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.

e04jdc makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.

Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this function. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

9 Further Comments

9.1 Description of the Printed Output

The solver can print information to give an overview of the problem and the progress of the computation. The output may be sent to two independent file ID which are set by optional parameters

Print File

and

Monitoring File

. Optional parameters

Print Level

Print Options

Monitoring Level

and

Print Solution

determine the exposed level of detail. This allows, for example, a detailed log file to be generated while the condensed information is displayed on the screen.

By default (

Print File = 6

Print Level = 2

), four sections are printed to the standard output: a header, a list of options, an iteration log and a summary.

Header

The header contains statistics about the problem. It should look like:

--------------------------------------------------------
E04J(D|E)), Derivative-free solver for bound constrained
            nonlinear functions
--------------------------------------------------------

Problem statistics
  Number of variables                  2
  Number of unconstrained variables    1
  Number of fixed variables            0
  Total interpolation points           5

Optional parameters list

Print Options = YES

, a list of the optional parameters and their values is printed. The list shows all options of the solver, each displayed on one line. The line contains the option name, its current value and an indicator for how it was set. The options left at their defaults are noted by ‘d’ and the ones you set are noted by ‘U’. Note that the output format is compatible with the file format expected by e04zpc. The output looks as follows:

Stats Time                    =                  No     * d
Dfo Trust Region Tolerance    =         5.00000E-07     * U
Dfo Max Objective Calls       =                 500     * d
Dfo Starting Trust Region     =         1.00000E-01     * d

Iteration log

Print Level \geq 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 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 |  4.32E+00  1.00E-01  |     6   |
    2 |  4.18E+00  1.00E-02  |    12   |
    3 |  4.11E+00  1.00E-02  |    13   |
    4 |  3.85E+00  1.00E-02  |    14   |

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

Summary

Once the solver finishes, a summary is produced:

Status: Converged, small trust region size

Value of the objective                    1.17772E-15
Number of objective function evaluations          205
Number of steps                                   116

Note that only the iterations that decrease the objective function are printed in the iteration log, meaning that objective evaluations are likely to happen between the last printed iteration and the convergence. This leads to a small difference between the last line of the iteration log and the final summary in terms of the number of function evaluations.

Optionally, if

Stats Time = YES

, the timings are printed:

Timings
      Total time spent in the solver            0.056
      Time spent in the objective evaluation    0.012

Additionally, if

Print Solution = YES

, the solution is printed along with the bounds:

Primal variables:
  idx   Lower bound        Value      Upper bound
    1       -inf       1.00000E+00         inf
    2  -2.00000E+00    1.00000E+00         inf

10 Example

In this example, we minimize this four-dimension function under some bound constraints:

f (x) = {(x_{1} + 10 x_{2})}^{2} + 5 {(x_{3} - x_{4})}^{2} + {(x_{2} - 2 x_{3})}^{4} + 10 {(x_{1} - x_{4})}^{4} .

The following bounds are defined on the variables

\begin{matrix} 1 \leq x_{1} \leq 3, \\ - 2 \leq x_{2} \leq 0, \\ 1 \leq x_{4} \leq 3 . \end{matrix}

The initial guess is

x_{0} = (3.0, - 1.0, 0.0, 1.0) .

10.1 Program Text

Program Text (e04jdce.c)

10.2 Program Data

None.

10.3 Program Results

Program Results (e04jdce.r)

11 Algorithmic Details

This section contains a short description of the algorithm used in e04jdc which is based on the collaborative work between NAG and the University of Oxford (Cartis et al. (2018)). It uses a model-based derivative-free trust region framework.

11.1 Derivative-free Trust Region Algorithm

In this section, we are interested in generic problems of the form

\begin{matrix} \underset{x \in ℝ^{n}}{minimize} & f (x) \end{matrix}

where the derivatives of the objective function

f

are not easily available. A model-based DFO algorithm maintains a set of points

Y_{k}

centred on an iterate

x_{k}

to build quadratic interpolation models of the objective

f (x_{k} + s) \approx ϕ_{k} (s) = f (x_{k}) + g_{k}^{T} s + \frac{1}{2} s^{T} H_{k} s,

where

g_{k}

and

H_{k}

are built with the interpolation conditions

\forall y \in Y_{k}, ​ ϕ_{k} (y - x_{k}) = f (y) .

(1)

Note that if the number of interpolation points

npt

is smaller than

\frac{(n_{r} + 1) \times (n_{r} + 2)}{2}

, the model chosen is the one for which the Hessian

H_{k}

is the closest to

H_{k - 1}

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. 1.Initialization
  Choose an initial interpolation set $Y_{0}$ , trust region radius $ρ_{beg}$ and build the first quadratic model $ϕ_{0}$ .
2. 2.Iteration k
  1. (i)Minimize the model in the trust region to obtain a step $s_{k}$ .
  2. (ii)If the step is too small, adjust the geometry of the interpolation set and the trust region size $ρ_{k}$ and restart the iteration.
  3. (iii)Evaluate the objective at the new point $x_{k} + s_{k}$ .
  4. (iv)Replace a far away point from $Y_{k}$ by $x_{k} + s_{k}$ to create $Y_{k + 1}$ .
  5. (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}$ .
  6. (vi)Choose $ρ_{k + 1}$ and adjust the geometry of $Y_{k + 1}$ , if necessary.
  7. (vii)Build $ϕ_{k + 1}$ using the new interpolation set.
  8. (viii)Stop the algorithm if $ρ_{k + 1}$ is below the chosen tolerance $ρ_{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 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 e04jdc define choices in the problem specification or the algorithm logic. In order to reduce the number of formal arguments of e04jdc these optional parameters have associated default values that are appropriate for most problems. Therefore, you need only specify those optional parameters whose values are to be different from their default values.

The remainder of this section can be skipped if you wish to use the default values for all optional parameters.

The optional parameters can be changed by calling e04zmc anytime between the initialization of the handle and the call to the solver. Modification of the optional parameters during intermediate monitoring stops is not allowed. Once the solver finishes, the optional parameters can be altered again for the next solve.

The option values may be retrieved by e04znc.

The following is a list of the optional parameters available. A full description of each optional parameter is provided in Section 12.1.

12.1 Description of the Optional Parameters

For each option, we give a summary line, a description of the optional parameter and details of constraints.

The summary line contains:

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 $ε$ is a generic notation for machine precision (see X02AJC).

All options accept the value

DEFAULT

to return single options to their default states.

Keywords and character values are case and white space insensitive.

Defaults

This special keyword may be used to reset all optional parameters to their default values. Any value given with this keyword will be ignored.

DFNO Detect Unbounded

a

Default

= YES

The solver can try to detect whether the problem is unbounded. This option allows you to turn on or off the unboundedness detection heuristic.

Constraint:

DFNO Detect Unbounded = YES

NO

DFNO Objective Limit

r

Default

= - \infty

This option sets an additional convergence criterion. The solver will stop if it finds a point for which the function value is lower than this parameter.

DFO Maximum Slow Steps

i

Default

= 20

DFO Maximum Slow Steps > 0

, this parameter defines the maximum number of consecutive slow iterations

n_{slow}

allowed. Set

DFO Maximum Slow Steps = 0

to deactivate the slow iteration detection. The algorithm can stop in two situations:

(i) $n_{slow} > DFO Maximum Slow Steps$ and $ρ < DFO Trust Region Slow Tol$ with $fail . code =$ NW_NOT_CONVERGED,
(ii) $n_{slow} > 5 \times DFO Maximum Slow Steps$ with $fail . code =$ NE_NO_IMPROVEMENT.

Constraint:

DFO Maximum Slow Steps \geq 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

fail . code =

NE_TOO_MANY_ITER.

Constraint:

DFO Max Objective Calls \geq 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 (

DFO Noisy Problem = YES

Constraint:

DFO Max Soft Restarts \geq 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 (

DFO Noisy Problem = YES

Constraint:

DFO Max Unsucc Soft Restarts \geq 1

DFO Monitor Frequency

i

Default

= 0

DFO Monitor Frequency > 0

, monit will be called at the end of every

i

th step for monitoring purposes.

Constraint:

DFO Monitor Frequency \geq 0

DFO Noise Level

r

Default

= 0.0

Indicates the noise level expected when evaluating the objective function if

DFO Noisy Problem = YES

Constraint:

DFO Noise Level \geq 0.0

DFO Noisy Problem

a

Default

= NO

Indicates if the function evaluations provided to the solver are noisy. If

DFO Noisy Problem = 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 $DFO Noise Level > 0.0$ , the solver will trigger a soft restart if all the function values are within the noise level.

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

DFO Number Interp Points = 0

, the number of points is chosen to be

n_{r} + 1

where

n_{r}

is the number of non-fixed variables.

Constraint:

DFO Number Interp Points \geq 0

Consistency constraint, the solver stops with

fail . code =

NE_INT if not met:

$n_{r} + 1 \leq DFO Number Interp Points \leq \frac{(n_{r} + 1) \times (n_{r} + 2)}{2}$ .

DFO Number Soft Restarts Pts

i

Default

= 3

The number of interpolation points that are replaced during a soft restart.

Constraint:

DFO Number Soft Restarts Pts \geq 1

DFO Print Frequency

i

Default

= 1

DFO Print Frequency > 0

, the solver prints the iteration log to the appropriate units at the end of every

i

th step.

Constraint:

DFO Print Frequency \geq 0

DFO Random Seed

i

Default

= - 1

The random seed used to generate the random points used to build the initial model. If

DFO Random Seed < 0

, the random seed will be based on values taken from the real-time 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:

DFO Print Frequency \geq - 1

DFO Starting Trust Region

r

Default

= 0.1

ρ_{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

ρ_{beg}

along each coordinate direction. The default value assumes that the variables have an order of magnitude

1

Constraint:

DFO Starting Trust Region > ε

Consistency constraints, the solver stops with

fail . code =

NE_REAL_2 if not met:

$DFO Starting Trust Region \leq DFO Trust Region Tolerance$ .
$DFO Starting Trust Region \leq \frac{1}{2} \min_{i} (u_{x} (i) - l_{x} (i))$ .

DFO Trust Region Slow Tol

r

Default

= ε^{0.25}

The minimal acceptable trust region radius for the solution to be declared as acceptable. The solver stops if:

$n_{slow} > DFO Maximum Slow Steps$ and $ρ_{k} < DFO Trust Region Slow Tol$ .

Constraint:

DFO Trust Region Slow Tol > ε

Consistency constraint, the solver stops with

fail . code =

NE_REAL_2 if not met:

$DFO Trust Region Slow Tol > DFO Trust Region Tolerance$ .

DFO Trust Region Tolerance

r

Default

= ε^{0.37}

ρ_{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:

DFO Trust Region Tolerance > ε

Consistency constraints, the solver stops with

fail . code =

NE_REAL_2 if not met:

$DFO Starting Trust Region > DFO Trust Region Tolerance$ .
$DFO Trust Region Slow Tol > DFO Trust Region Tolerance$ .

Infinite Bound Size

r

Default

= 10^{20}

This defines the ‘infinite’ bound

bigbnd

in the definition of the problem constraints. Any upper bound greater than or equal to

bigbnd

will be regarded as

+ \infty

(and similarly any lower bound less than or equal to

- 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:

Infinite Bound Size \geq 1000

Monitoring File

i

Default

= - 1

(See Section 3.1.1 in the Introduction to the NAG Library CL Interface for further information on NAG data types.)

i \geq 0

, the Nag_FileID number (as returned from x04acc) for the secondary (monitoring) output. If

Monitoring File = - 1

, no secondary output is provided. The information output to this file ID is controlled by

Monitoring Level

Constraint:

Monitoring File \geq - 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 \leq Monitoring Level \leq 5

Print File

i

Default

= Nag_FileID number associated with stdout

(See Section 3.1.1 in the Introduction to the NAG Library CL Interface for further information on NAG data types.)

i \geq 0

, the Nag_FileID number (as returned from x04acc, stdout as the default) for the primary output of the solver. If

Print File = - 1

, the primary output is completely turned off independently of other settings. The information output to this unit is controlled by

Print Level

Constraint:

Print File \geq - 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 \leq Print Level \leq 5

Print Options

a

Default

= YES

Print Options = YES

, a listing of optional parameters will be printed to the primary output and is always printed to the secondary output.

Constraint:

Print Options = YES

NO

Print Solution

a

Default

= NO

Print Solution = YES

, the solution will be printed to the primary and secondary output.

Constraint:

Print Solution = YES

NO

Task

a

Default

= MINIMIZE

This parameter specifies the required direction of the optimization. If

Task = FEASIBLE POINT

, the objective function (if set) is ignored and the algorithm stops as soon as a feasible point is found with respect to the given tolerance.

Constraint:

Task = MINIMIZE

MAXIMIZE

FEASIBLE POINT

Stats Time

a

Default

= NO

This parameter turns on timings of various parts of the algorithm to give a better overview of where most of the time is spent. This might be helpful for a choice of different solving approaches. It is possible to choose between CPU and wall clock time. Choice

YES

is equivalent to

WALL CLOCK

Constraint:

Stats Time = YES

NO

CPU

WALL CLOCK

Time Limit

r

Default

= 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

fail . code =

NE_TIME_LIMIT.

Constraint:

Time Limit > 0

NAG Library Manual, Mark 27

Interfaces: FL CL AD

NAG CL Interface Introduction

E04 (Opt) Chapter Contents

E04 (Opt) Chapter Introduction

e04jd: FL CL AD

NAG CL Interfacee04jdc (handle_​solve_​dfno)

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

9.1 Description of the Printed Output

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

11 Algorithmic Details

11.1 Derivative-free Trust Region Algorithm

11.2 Bounds on the Variables

11.3 Dealing with Noisy Problems

12 Optional Parameters

12.1 Description of the Optional Parameters

NAG CL Interface
e04jdc (handle_solve_dfno)