Note:this routine usesoptional parametersto 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.
The routine may be called by the names e04jdf or nagf_opt_handle_solve_dfno.
e04jdf is aimed at minimizing a nonlinear objective function subject to bound constraints:
Here is a smooth nonlinear function and and are -dimensional vectors defining bounds on the variables.
e04jdf 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 e04rgf 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 e04jdf always assumes that the gradient of the objective is dense, therefore, defining a sparse structure for the residuals in the call to e04rgf 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 non-fixed variable , the value of 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 e04zmfande04zpf 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 (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 to .
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 e04jdf is the same as the one used by e04jef. e04jdf serves as a forward communication interface to the derivative-free solver for nonlinear objective functions.
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
On entry: the handle to the problem. It needs to be initialized (e.g., by e04raf) and to hold a problem formulation compatible with e04jdf. It must not be changed between calls to the NAG optimization modelling suite.
2: – Subroutine, supplied by the NAG Library or the user.External Procedure
objfun calculates the value of the objective function at a specified point . If there is no nonlinear objective (e.g., e04refore04rff was called to define a linear or quadratic objective function), objfun will never be called by e04jdf and may be the dummy routine e04jdv (included in the NAG Library.)
objfun must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which e04jdf is called. Arguments denoted as Input must not be changed by this procedure.
Note:objfun should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by e04jdf. If your code inadvertently does return any NaNs or infinities, e04jdf is likely to produce unexpected results.
3: – Subroutine, supplied by the NAG Library or the user.External Procedure
monit is provided to enable you to monitor the progress of the optimization. It is invoked at the end of every th iteration where is given by the DFO Monitor Frequency (the default is , monit is not called).
If no monitoring is required, monit may be the dummy subroutine e04jdu supplied in the NAG Library.
monit must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which e04jdf is called. Arguments denoted as Input must not be changed by this procedure.
4: – IntegerInput
On entry: , the current number of decision variables in the model.
5: – Real (Kind=nag_wp) arrayInput/Output
On entry: , the initial estimates of the variables, .
On exit: the final values of the variables, .
6: – Real (Kind=nag_wp) arrayOutput
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:
Objective function value .
, the current lower bound of the trust region.
, the current size of the trust region.
The number of interpolation points used by the solver.
Reserved for future use.
7: – Real (Kind=nag_wp) arrayOutput
On exit: solver statistics at monitoring steps or at the end of the final iteration as given in the table below:
Number of calls to the objective function.
Total time spent in the solver (including time spent evaluating the objective).
Total time spent evaluating the objective function.
Number of steps.
Reserved for future use.
8: – Integer arrayUser Workspace
9: – Real (Kind=nag_wp) arrayUser Workspace
10: – Type (c_ptr)User Workspace
iuser, ruser and cpuser are not used by e04jdf, 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.
11: – IntegerInput/Output
On entry: ifail must be set to , or to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of means that an error message is printed while a value of means that it is not.
If halting is not appropriate, the value or is recommended. If message printing is undesirable, then the value is recommended. Otherwise, the value is recommended since useful values can be provided in some output arguments even when on exit. When the value or is used it is essential to test the value of ifail on exit.
On exit: unless the routine detects an error or a warning has been flagged (see Section 6).
6Error Indicators and Warnings
If on entry or , 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 e04jdf may return useful information.
The supplied handle does not define a valid handle to the data structure for the NAG optimization modelling suite. It has not been properly initialized or it has been corrupted.
The problem is already being solved.
This solver does not support the model defined in the handle.
On entry, , expected .
Constraint: nvar must match the current number of variables of the model in the handle.
The dummy objfun routine was called but the problem requires these values. Please provide a proper objfun routine.
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.
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.
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.
User requested termination after a call to the objective function. inform was set to a value lower than within the user-supplied function objfun.
User requested termination during a monitoring step. inform was set to a value lower than within the user-supplied function monit.
Maximum number of function evaluations exceeded.
The solver terminated after the maximum time allowed was exceeded.
Maximum number of seconds exceeded. Use optional parameter Time Limit to reset the limit.
No progress, the solver was stopped after consecutive slow steps. Use the optional parameter DFO Maximum Slow Steps to modify the maximum number of slow steps accepted.
The problem seems to be unbounded. The unboundedness detection heuristic can be turned off with the option DFNO Detect Unbounded.
An unexpected error has been triggered by this routine. Please
See Section 7 in the Introduction to the NAG Library FL Interface for further information.
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.
Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.
In a non-noisy case, the solver can declare convergence on two conditions.
(i)The trust region radius is below the tolerance 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 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.
e04jdf is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
e04jdf 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 implementation-specific information.
9.1Description 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
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 (, ), four sections are printed to the standard output: a header, a list of options, an iteration log and a summary.
The header contains statistics about the problem. It should look like:
E04J(D|E), Derivative-free solver for bound constrained nonlinear functions
Optional parameters list
If , 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 e04zpf. The output looks as follows:
Dfo Max Objective Calls = 500 * d
Dfo Max Soft Restarts = 5 * d
Dfo Max Unsucc Soft Restarts = 3 * d
Dfo Maximum Slow Steps = 20 * d
Dfo Noise Level = 0.00000E+00 * d
If , statistics on the problem are printed, for example:
No of variables 4
free (unconstrained) 1
Objective function Nonlinear
If , 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:
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.
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 , the timings are printed:
Total time spent in the solver 0.056
Time spent in the objective evaluation 0.012
Additionally, if , the solution is printed along with the bounds:
This section contains a short description of the algorithm used in e04jdf 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.1Derivative-free Trust Region Algorithm
In this section, we are interested in generic problems of the form
where the derivatives of the objective function are not easily available. A model-based DFO algorithm maintains a set of points centred on an iterate to build quadratic interpolation models of the objective
where and are built with the interpolation conditions
Note that if the number of interpolation points is smaller than , the model chosen is the one for which the Hessian is the closest to 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:
Choose an initial interpolation set , trust region radius and build the first quadratic model .
(i)Minimize the model in the trust region to obtain a step .
(ii)If the step is too small, adjust the geometry of the interpolation set and the trust region size and restart the iteration.
(iii)Evaluate the objective at the new point .
(iv)Replace a far away point from by to create .
(v)If the decrease of the objective is sufficient (successful step), choose , else choose .
(vi)Choose and adjust the geometry of , if necessary.
(vii)Build using the new interpolation set.
(viii)Stop the algorithm if is below the chosen tolerance .
In the following sections, we call an iteration ‘successful’ when the trial point is accepted as the next iterate.
11.2Bounds 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.3Dealing 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.
Several optional parameters in e04jdf define choices in the problem specification or the algorithm logic. In order to reduce the number of formal arguments of e04jdf 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.
(iii)In addition, if , the solver will trigger a soft restart if all the function values are within the noise level.
DFO Number Interp Points
The maximum number of interpolation points in (1) used to build the linear models of the residuals. If , the number of points is chosen to be where is the number of non-fixed variables.
Consistency constraint, the solver stops with if not met:
DFO Number Soft Restarts Pts
The number of interpolation points that are replaced during a soft restart.
DFO Print Frequency
If , the solver prints the iteration log to the appropriate units at the end of every th step.
DFO Random Seed
The random seed used to generate the random points used to build the initial model. If , 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.
DFO Starting Trust Region
, 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 of length along each coordinate direction. The default value assumes that the variables have an order of magnitude .
Consistency constraints, the solver stops with if not met:
DFO Trust Region Slow Tol
The minimal acceptable trust region radius for the solution to be declared as acceptable. The solver stops if:
Consistency constraint, the solver stops with if not met:
DFO Trust Region Tolerance
, 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.
Consistency constraints, the solver stops with if not met:
Infinite Bound Size
This defines the ‘infinite’ bound in the definition of the problem constraints. Any upper bound greater than or equal to will be regarded as (and similarly any lower bound less than or equal to will be regarded as ). 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.
If , the
for the secondary (monitoring) output. If , no secondary output is provided. The information output to this unit is controlled by Monitoring Level.
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.
If , the
for the primary output of the solver. If , 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.
This parameter defines how detailed information should be printed by the solver to the primary and secondary output.
No output from the solver.
The Header and Summary.
, , ,
Additionally, the Iteration log.
If , a listing of optional parameters will be printed to the primary output and is always printed to the secondary output.
Constraint: or .
If , the solution will be printed to the primary and secondary output.
Constraint: or .
This parameter specifies the required direction of the optimization. If , 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: , or .
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 is equivalent to .
Constraint: , , or .
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 .