naginterfaces.library.opt.handle_​solve_​dfno

naginterfaces.library.opt.handle_solve_dfno(handle, x, objfun=None, monit=None, data=None, io_manager=None)

handle_solve_dfno 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.

Note: this function uses optional algorithmic parameters, see also: handle_opt_set(), handle_opt_get().

For full information please refer to the NAG Library document for e04jd

https://www.nag.com/numeric/nl/nagdoc_29.3/flhtml/e04/e04jdf.html

Parameters

handleHandle

The handle to the problem. It needs to be initialized (e.g., by handle_init()) and to hold a problem formulation compatible with handle_solve_dfno. It must not be changed between calls to the NAG optimization modelling suite.

xfloat, array-like, shape $\left(\text{nvar}\right)$

$x_0$, the initial estimates of the variables, $x$.

objfunNone or callable (fx, inform) = objfun(x, inform, data=None), optional

Note: if this argument is None then a NAG-supplied facility will be used.

$objfun$ calculates the value of the objective function $f\left(x\right)$ at a specified point $x$.

If there is no nonlinear objective (e.g., handle_set_linobj() or handle_set_quadobj() was called to define a linear or quadratic objective function), $objfun$ will never be called by handle_solve_dfno and may be None.

Parameters

xfloat, ndarray, shape $\left(\text{nvar}\right)$

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

informint

A non-negative value.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

Returns

fxfloat

The value of the objective function at $x$.

informint

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 $errno$ = 17.

$inform=-2$

The solver will cleanly exit with $errno$ = 20 and return the best available point as well as the solve statistics.

monitNone or callable monit(x, rinfo, stats, data=None), optional

Note: if this argument is None then a NAG-supplied facility will be used.

$monit$ is provided to enable you to monitor the progress of the optimization.

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 None.

Parameters

xfloat, ndarray, shape $\left(\text{nvar}\right)$

$x$, the vector of decision variables at the current iteration.

rinfofloat, ndarray, shape $\left(100\right)$

Error measures and various indicators at the end of the current iteration as described in the main argument $rinfo$.

statsfloat, ndarray, shape $\left(100\right)$

Solver statistics at monitoring steps or at the end of the current iteration (the values are as described in the main argument $stats$).

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

dataarbitrary, optional

User-communication data for callback functions.

io_managerFileObjManager, optional

Manager for I/O in this routine.

Returns

xfloat, ndarray, shape $\left(\text{nvar}\right)$

The final values of the variables, $x$.

rinfofloat, ndarray, shape $\left(100\right)$

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\left(x\right)$.
$1$	$\rho$, the current lower bound of the trust region.
$2$	$\Delta$, the current size of the trust region.
$3$	The number of interpolation points used by the solver.
$4$–$99$	Reserved for future use.

statsfloat, ndarray, shape $\left(100\right)$

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.

Other Parameters

‘Defaults’valueless

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

‘DFNO Detect Unbounded’str

Default $=\text{'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: $\text{‘DFNO Detect Unbounded'}=\text{'YES'}$ or $\text{'NO'}$.

‘DFNO Objective Limit’float

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’int

Default $=20$

If $\text{‘DFO Maximum Slow Steps'}>0$, this argument defines the maximum number of consecutive slow iterations $n_{\text{slow}}$ allowed. Set $\text{‘DFO Maximum Slow Steps'}=0$ to deactivate the slow iteration detection. The algorithm can stop in two situations:

1. $n_{\text{slow}}>\text{‘DFO Maximum Slow Steps'}$ and $\rho <\text{‘DFO Trust Region Slow Tol'}$ with $errno$ = 50,

2. $n_{\text{slow}}>5\times \text{‘DFO Maximum Slow Steps'}$ with $errno$ = 24.

Constraint: $\text{‘DFO Maximum Slow Steps'}\ge 0$.

‘DFO Max Objective Calls’int

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 $errno$ = 21.

Constraint: $\text{‘DFO Max Objective Calls'}\ge 1$.

‘DFO Max Soft Restarts’int

Default $=5$

The maximum total number of soft restarts that can be performed if the objective function is declared as noisy ($\text{‘DFO Noisy Problem'}=\text{'YES'}$).

Constraint: $\text{‘DFO Max Soft Restarts'}\ge 1$.

‘DFO Max Unsucc Soft Restarts’int

Default $=3$

The maximum number of consecutive unsuccessful soft restarts that can be performed if the objective function is declared as noisy ($\text{‘DFO Noisy Problem'}=\text{'YES'}$).

Constraint: $\text{‘DFO Max Unsucc Soft Restarts'}\ge 1$.

‘DFO Monitor Frequency’int

Default $=0$

If $\text{‘DFO Monitor Frequency'}>0$, $monit$ will be called at the end of every $i$th step for monitoring purposes.

Constraint: $\text{‘DFO Monitor Frequency'}\ge 0$.

‘DFO Noise Level’float

Default $=0.0$

Indicates the noise level expected when evaluating the objective function if $\text{‘DFO Noisy Problem'}=\text{'YES'}$.

Constraint: $\text{‘DFO Noise Level'}\ge 0.0$.

‘DFO Noisy Problem’str

Default $=\text{'NO'}$

Indicates if the function evaluations provided to the solver are noisy. If $\text{‘DFO Noisy Problem'}=\text{'YES'}$, some algorithmic features will be activated:

1. The trust region update becomes slower to reflect the decreased confidence in the objective values.

2. 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’, ‘DFO Number Soft Restarts Pts’ to control the restart characteristics).

3. In addition, if $\text{‘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’int

Default $=0$

The maximum number of interpolation points in $Y_k$ (9) used to build the linear models of the residuals. If $\text{‘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: $\text{‘DFO Number Interp Points'}\ge 0$.

Consistency constraint, the solver stops with $errno$ = 6 if not met:

$n_r+1\le \text{‘DFO Number Interp Points'}\le \frac{(n_r+1)\times (n_r+2)}{2}$.

‘DFO Number Soft Restarts Pts’int

Default $=3$

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

Constraint: $\text{‘DFO Number Soft Restarts Pts'}\ge 1$.

‘DFO Print Frequency’int

Default $=1$

If $\text{‘DFO Print Frequency'}>0$, the solver prints the iteration log to the appropriate units at the end of every $i$th step.

Constraint: $\text{‘DFO Print Frequency'}\ge 0$.

‘DFO Random Seed’int

Default $=-1$

The random seed used to generate the random points used to build the initial model. If $\text{‘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: $\text{‘DFO Print Frequency'}\ge -1$.

‘DFO Starting Trust Region’float

Default $=0.1$

${\rho }_{\text{beg}}$, the initial trust region radius. This argument 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 }_{\text{beg}}$ along each coordinate direction. The default value assumes that the variables have an order of magnitude $1$.

Constraint: $\text{‘DFO Starting Trust Region'}>ϵ$.

Consistency constraints, the solver stops with $errno$ = 5 if not met:

$\text{‘DFO Starting Trust Region'}\le \text{‘DFO Trust Region Tolerance'}$.

$\text{‘DFO Starting Trust Region'}\le \frac{1}{2}{min}_i(u_x\left(i\right)-l_x\left(i\right))$.

‘DFO Trust Region Slow Tol’float

Default $={ϵ}^{0.25}$

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

$n_{\text{slow}}>\text{‘DFO Maximum Slow Steps'}$ and ${\rho }_k<\text{‘DFO Trust Region Slow Tol'}$.

Constraint: $\text{‘DFO Trust Region Slow Tol'}>ϵ$.

Consistency constraint, the solver stops with $errno$ = 5 if not met:

$\text{‘DFO Trust Region Slow Tol'}>\text{‘DFO Trust Region Tolerance'}$.

‘DFO Trust Region Tolerance’float

Default $={ϵ}^{0.37}$

${\rho }_{\text{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: $\text{‘DFO Trust Region Tolerance'}>ϵ$.

Consistency constraints, the solver stops with $errno$ = 5 if not met:

$\text{‘DFO Starting Trust Region'}>\text{‘DFO Trust Region Tolerance'}$.

$\text{‘DFO Trust Region Slow Tol'}>\text{‘DFO Trust Region Tolerance'}$.

‘Infinite Bound Size’float

Default $={10}^{20}$

This defines the ‘infinite’ bound $\text{bigbnd}$ in the definition of the problem constraints. Any upper bound greater than or equal to $\text{bigbnd}$ will be regarded as $+\infty$ (and similarly any lower bound less than or equal to $-\text{bigbnd}$ will be regarded as $-\infty$). Note that a modification of this option does not influence constraints which have already been defined; only the constraints formulated after the change will be affected.

Constraint: $\text{‘Infinite Bound Size'}\ge 1000$.

‘Monitoring File’int

Default $=-1$

If $i\ge 0$, the unit number for the secondary (monitoring) output. If $\text{‘Monitoring File'}=-1$, no secondary output is provided. The information output to this unit is controlled by ‘Monitoring Level’.

Constraint: $\text{‘Monitoring File'}\ge -1$.

‘Monitoring Level’int

Default $=4$

This argument 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 \text{‘Monitoring Level'}\le 5$.

‘Print File’int

Default $=\text{advisory message unit number}$

If $i\ge 0$, the unit number for the primary output of the solver. If $\text{‘Print File'}=-1$, the primary output is completely turned off independently of other settings. The default value is the advisory message unit number at the time of the options initialization, e.g., at the initialization of the handle. The information output to this unit is controlled by ‘Print Level’.

Constraint: $\text{‘Print File'}\ge -1$.

‘Print Level’int

Default $=2$

This argument 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 \text{‘Print Level'}\le 5$.

‘Print Options’str

Default $=\text{'YES'}$

If $\text{‘Print Options'}=\text{'YES'}$, a listing of options will be printed to the primary output and is always printed to the secondary output.

Constraint: $\text{‘Print Options'}=\text{'YES'}$ or $\text{'NO'}$.

‘Print Solution’str

Default $=\text{'NO'}$

If $\text{‘Print Solution'}=\text{'YES'}$, the solution will be printed to the primary and secondary output.

Constraint: $\text{‘Print Solution'}=\text{'YES'}$ or $\text{'NO'}$.

‘Task’str

Default $=\text{'MINIMIZE'}$

This argument specifies the required direction of the optimization. If $\text{‘Task'}=\text{'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: $\text{‘Task'}=\text{'MINIMIZE'}$, $\text{'MAXIMIZE'}$ or $\text{'FEASIBLE POINT'}$.

‘Stats Time’str

Default $=\text{'NO'}$

This argument 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: $\text{‘Stats Time'}=\text{'YES'}$, $\text{'NO'}$, $\text{'CPU'}$ or $\text{'WALL CLOCK'}$.

‘Time Limit’float

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 $errno$ = 23.

Constraint: $\text{‘Time Limit'}>0$.

Raises

NagValueError

(errno $1$)

$handle$ has not been initialized.

(errno $1$)

$handle$ does not belong to the NAG optimization modelling suite, has not been initialized properly or is corrupted.

(errno $1$)

$handle$ has not been initialized properly or is corrupted.

(errno $2$)

This solver does not support the model defined in the handle.

(errno $2$)

The problem is already being solved.

(errno $4$)

On entry, $\text{nvar}=⟨value⟩$, expected $value=⟨value⟩$.

Constraint: $\text{nvar}$ must match the current number of variables of the model in the $handle$.

(errno $5$)

Inconsistent options ‘DFO Trust Region Tolerance’ ${\rho }_{\text{end}}$ and ‘DFO Starting Trust Region’ ${\rho }_{\text{beg}}$.

Constraint: ${\rho }_{\text{end}}<{\rho }_{\text{beg}}$.

Use handle_opt_set() to set compatible option values.

(errno $5$)

Inconsistent options ‘DFO Trust Region Tolerance’ ${\rho }_{\text{end}}$ and ‘DFO Trust Region Slow Tol’ ${\rho }_{\text{tol}}$.

Constraint: ${\rho }_{\text{end}}<{\rho }_{\text{tol}}$.

Use handle_opt_set() to set compatible option values.

(errno $5$)

Option ‘DFO Starting Trust Region’ ${\rho }_{\text{beg}}=⟨value⟩$, $l_x\left(i\right)=⟨value⟩$, $u_x\left(i\right)=⟨value⟩$ and $i=⟨value⟩$.

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 }_{\text{beg}}$.

Use handle_opt_set() to set compatible option values.

(errno $6$)

There were $n_r=⟨value⟩$ unequal bounds and the option ‘DFO Number Interp Points’ $\text{npt}=⟨value⟩$.

Constraint: $n_r+1\le \text{npt}\le \frac{(n_r+1)\times (n_r+2)}{2}$.

Use handle_opt_set() to set compatible option values.

(errno $6$)

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.

(errno $7$)

Please provide a proper $objfun$ function.

Warns

NagAlgorithmicWarning

(errno $50$)

The problem was solved to an acceptable level after $⟨value⟩$ consecutive slow iterations.

Use the option ‘DFO Maximum Slow Steps’ to modify the maximum number of slow steps accepted.

NagAlgorithmicMajorWarning

(errno $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$.

(errno $17$)

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$.

(errno $18$)

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$.

(errno $19$)

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$.

(errno $20$)

User requested termination after a call to the objective function.

(errno $21$)

Maximum number of function evaluations exceeded.

(errno $23$)

The solver terminated after the maximum time allowed was exceeded.

(errno $24$)

No progress, the solver was stopped after $⟨value⟩$ consecutive slow steps.

Use the option ‘DFO Maximum Slow Steps’ to modify the maximum number of slow steps accepted.

(errno $54$)

The problem seems to be unbounded.

The unboundedness detection heuristic can be turned off with the option ‘DFNO Detect Unbounded’.

NagCallbackTerminateWarning

(errno $20$)

User requested termination during a monitoring step.

Notes

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

$$\begin{array}{c}\begin{array}{cc}{minimize}_{x\in R^n}& f\left(x\right)\\ \text{subject to}& l_x\le x\le u_x\text{.}\end{array}\end{array}$$

Here $f$ is a smooth nonlinear function and $l_x$ and $u_x$ are $n$-dimensional vectors defining bounds on the variables.

handle_solve_dfno 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 handle_init() followed by handle_set_nlnobj() to initialize it and optionally call handle_set_simplebounds() to define bounds on the variables. If handle_set_simplebounds() is not called, all the variables will be considered free by the solver. It should be noted that handle_solve_dfno always assumes that the gradient of the objective is dense, therefore, defining a sparse structure for the residuals in the call to handle_set_nlnobj() will have no effect. See the E04 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\left(i\right)-l_x\left(i\right)$ must be at least twice the starting trust region radius (see the consistency constraint of the option ‘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 Algorithmic Details.

The algorithm behaviour and solver strategy can be modified by various options (see Other Parameters) which can be set by handle_opt_set() and handle_opt_set_file() at any time between the initialization of the handle by handle_init() and a call to the solver. The options’ 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 options 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 option ‘DFO Noisy Problem’ to ‘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 options.

The underlying algorithm implemented for handle_solve_dfno is the same as the one used by handle_solve_dfno_rcomm(). handle_solve_dfno serves as a forward communication interface to the derivative-free solver for nonlinear objective functions.

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

See also

naginterfaces.library.examples.opt.handle_solve_dfno_ex.main()