naginterfaces.library.opt.handle_solve_bxnl¶
- naginterfaces.library.opt.handle_solve_bxnl(handle, lsqfun, lsqgrd, x, nres, lsqhes=None, lsqhprd=None, monit=None, data=None, io_manager=None, spiked_sorder='C')[source]¶
handle_solve_bxnl
is a bound-constrained nonlinear least squares trust region solver (BXNL) from the NAG optimization modelling suite aimed for small to medium-scale problems.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 e04gg
https://www.nag.com/numeric/nl/nagdoc_29.2/flhtml/e04/e04ggf.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 withhandle_solve_bxnl
. It must not be changed between calls to the NAG optimization modelling suite.- lsqfuncallable (rx, inform) = lsqfun(x, nres, inform, data=None)
must evaluate the value of the nonlinear residuals, , at a specified point .
- Parameters
- xfloat, ndarray, shape
, the vector of variable values at which the residuals, , are to be evaluated.
- nresint
, the current number of residuals in the model.
- informint
A non-negative value.
- dataarbitrary, optional, modifiable in place
User-communication data for callback functions.
- Returns
- rxfloat, array-like, shape
The value of the residual vector, , evaluated at .
- informint
May be used to indicate that some residuals could not be computed at the requested point. This can be done by setting to a negative value. The solver will attempt a rescue procedure and request an alternative point. If the rescue procedure fails, the solver will exit with = 25.
- lsqgrdcallable inform = lsqgrd(x, nres, rdx, inform, data=None)
evaluates the residual gradients, , at a specified point .
- Parameters
- xfloat, ndarray, shape
, the vector of variable values at which the residual gradients, , are to be evaluated.
- nresint
, the current number of residuals in the model.
- rdxfloat, ndarray, shape , to be modified in place
On entry: the elements should only be assigned and not referenced.
On exit: the vector containing the nonzero residual gradients evaluated at ,
where
The elements must be stored in the same order as the defined sparsity pattern provided in the call to
handle_set_nlnls()
.- informint
A non-negative value.
- dataarbitrary, optional, modifiable in place
User-communication data for callback functions.
- Returns
- informint
May be used to indicate that the residual gradients could not be computed at the requested point. This can be done by setting to a negative value. The solver will attempt a rescue procedure and request an alternative point. If the rescue procedure fails, the solver will exit with = 25.
- xfloat, array-like, shape
, the initial estimates of the variables, .
- nresint
, the current number of residuals in the model.
- lsqhesNone or callable inform = lsqhes(x, lamda, hx, inform, data=None), optional
Note: if this argument is None then a NAG-supplied facility will be used.
evaluates the residual Hessians, , at a specified point .
By default, the option and is never called. may be None.
This function will only be called if the option and if the model (see Models) requires second order information.
Under these circumstances, if you do not provide a valid the solver will terminate with either = 6 or = 21.
- Parameters
- xfloat, ndarray, shape
, the vector of decision variables at the current iteration.
- lamdafloat, ndarray, shape
, the vector containing the (weighted) residuals at , . See [equation] and Residual Weights.
- hxfloat, ndarray, shape , to be modified in place
On entry: the elements should only be assigned and not referenced.
On exit: a dense square (symmetric) matrix containing the weighted sum of residual Hessians,
where
is also a dense square (symmetric) matrix containing the th residual Hessian evaluated at the point . All matrix elements must be provided: both upper and lower triangular parts.
- informint
A non-negative value.
- dataarbitrary, optional, modifiable in place
User-communication data for callback functions.
- Returns
- informint
May be used to indicate that one or more elements of the residual Hessian could not be computed at the requested point. This can be done by setting to a negative value. The solver will attempt a rescue procedure and if the rescue procedure fails, the solver will exit with = 25.
- lsqhprdNone or callable (hxy, inform) = lsqhprd(x, y, hxy, inform, data=None), optional
Note: if this argument is None then a NAG-supplied facility will be used.
evaluates the residual Hessians, , at a specified point, , and performs matrix-vector products with a given vector, , returning the dense matrix .
If you do not supply this function, it may be None.
- Parameters
- xfloat, ndarray, shape
, the vector of decision variables at the current iteration.
- yfloat, ndarray, shape
, the vector used to perform the required matrix-vector products.
- hxyfloat, ndarray, shape
The elements should only be assigned and not referenced.
- informint
The first call to will have a non-zero value and can be used to optimize your code in order to avoid recalculations of common quantities when evaluating the Hessians. For all other instances will have a value of zero. This notification argument may be safely ignored if such optimization is not required.
- dataarbitrary, optional, modifiable in place
User-communication data for callback functions.
- Returns
- hxyfloat, array-like, shape
A dense matrix of size containing the following matrix-vector products,
- informint
May be used to indicate that one or more elements of the residual Hessian could not be computed at the requested point. This can be done by setting to a negative value. The solver will attempt a rescue procedure and if the rescue procedure fails, the solver will exit with = 25. The value of returned on the first call is ignored.
- monitNone or callable monit(x, rinfo, stats, data=None), optional
Note: if this argument is None then a NAG-supplied facility will be used.
is provided to enable monitoring of the progress of the optimization and, if necessary, to halt the optimization process.
If no monitoring is required, may be None.
is called at the end of every th step where is controlled by the option ‘Bxnl Monitor Frequency’ (the default value is , is not called).
- Parameters
- xfloat, ndarray, shape
The current best point.
- rinfofloat, ndarray, shape
Best objective value computed and various indicators (the values are as described in the main argument ).
- statsfloat, ndarray, shape
Solver statistics at monitoring steps or at the end of the current iteration (the values are as described in the main argument ).
- 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.
- spiked_sorderstr, optional
If in is spiked (i.e., has unit extent in all but one dimension, or has size ), selects the storage order to associate with it in the NAG Engine:
- spiked_sorder =
row-major storage will be used;
- spiked_sorder =
column-major storage will be used.
- Returns
- xfloat, ndarray, shape
The final values of the variables, .
- rxfloat, ndarray, shape
The values of the residuals at the final point given in .
- rinfofloat, ndarray, shape
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, .
Norm of the projected gradient at the current iterate, see PG STEP in Bound Constraints and [equation] in Stopping Criteria.
Norm of the scaled projected gradient at the current iterate, see [equation] in Stopping Criteria
Norm of the step between the current and previous iterate.
Convergence tests result. A scalar value between indicates whether a convergence test has passed. Specifically, indicates small objective test passed, indicates small (scaled) gradient test passed, indicates small step test passed. In the case where two or more tests passed, they are accumulated.
Norm of the current iterate . If regularization is requested, then this value was used in the regularization and it might differ from if has fixed or disabled elements.
–
Reserved for future use.
- statsfloat, ndarray, shape
Solver statistics at monitoring steps or at the end of the final iteration as given in the table below:
Number of iterations performed.
Total number of calls to the objective function .
Total number of calls to the objective gradient function .
Total number of calls to the objective Hessian function .
Total time in seconds spent in the solver. It includes time spent in user-supplied subroutines.
Number of calls to the objective function required by linesearch steps.
Number of calls to the objective gradient function required by linesearch steps.
Number of calls to the objective function required by projected gradient steps.
Number of calls to the objective gradient function required by projected gradient steps.
Number of inner iterations performed, see option .
Number of linesearch iterations performed.
Number of projected gradient iterations performed.
Total number of calls to the objective auxiliary Hessian function .
–
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.
- ‘Bxnl Basereg Pow’float
Default
This argument defines the regularization power in [equation] and for the tensor Newton subproblem (when ). Some values are restricted depending on the type of regularization specified, see ‘Bxnl Basereg Type’ for more details.
Constraint: .
- ‘Bxnl Basereg Term’float
Default
This argument defines the regularization term in [equation] and for the tensor Newton subproblem (when ).
Constraint: .
- ‘Bxnl Basereg Type’str
Default
This argument specifies the method used to incorporate the regularizer into [equation] and optionally into the tensor Newton subproblem (when and ).
The option reformulates the original problem by expanding it with degrees of freedom that is subsequently solved. For the case the residual vector is extended with a new term of the form ; for this method a value of is recommended.
If then the regularization power term must be , that is . For further details see Subproblems.
Constraint: , or .
- ‘Bxnl Save Covariance Matrix’str
Default
This argument indicates to the solver to store the covariance matrix into the handle.
If then the lower triangle part of the covariance matrix is stored in packed column order (see the F07 Introduction) into the handle and can be retrieved via
handle_set_get_real()
using with .In the special case where , only the diagonal elements of the covariance matrix are stored in the handle and can be retrieved via
handle_set_get_real()
using with .Similarly, if then the lower triangle part of the matrix is stored in packed column order into the handle and can be retrieved via
handle_set_get_real()
using with .Limitations: If the number of enabled residuals is not greater than the number of enabled variables, or the pseudo-inverse of could not be calculated, then the covariance matrix (variance vector) is not stored in the handle and will not be available.
For more information on how the covariance matrix is estimated, see
lsq_uncon_covariance()
.Constraint: , , or .
- ‘Bxnl Stop Abs Tol Fun’float
Default
This argument specifies the relative tolerance for the error test, specifically, it sets the value of of equation [equation] in Stopping Criteria. Setting ‘Bxnl Stop Abs Tol Fun’ to a large value may cause the solver to stop prematurely with a suboptimal solution.
Constraint: .
- ‘Bxnl Stop Abs Tol Grd’float
Default
This argument specifies the relative tolerance for the gradient test, specifically, it sets the value of of equation [equation] in Stopping Criteria. Setting ‘Bxnl Stop Abs Tol Grd’ to a large value may cause the solver to stop prematurely with a suboptimal solution.
Constraint: .
- ‘Bxnl Stop Rel Tol Fun’float
Default
This argument specifies the relative tolerance for the error test, specifically, it sets the value of of equation [equation] in Stopping Criteria. Setting ‘Bxnl Stop Rel Tol Fun’ to a large value may cause the solver to stop prematurely with a suboptimal solution.
Constraint: .
- ‘Bxnl Stop Rel Tol Grd’float
Default
This argument specifies the relative tolerance for the gradient test, specifically, it sets the value of of equation [equation] in Stopping Criteria. Setting ‘Bxnl Stop Rel Tol Grd’ to a large value may cause the solver to stop prematurely with a suboptimal solution.
Constraint: .
- ‘Bxnl Stop Step Tol’float
Default
Specifies the stopping tolerance for the step length test, specifically, it sets the value for of equation [equation] in Stopping Criteria. Setting ‘Bxnl Stop Step Tol’ to a large value may cause the solver to stop prematurely with a suboptimal solution.
Under certain circumstances, e.g., when in doubt of the quality of the first - or second-order derivatives, in the event of the solver exiting with a successful step length test, it is recommended to verify that either the error or the gradient norm is acceptably small.
Constraint: .
- ‘Bxnl Reg Order’str
Default
This argument specifies the order of the regularization in [equation] used when .
Some values for are restricted depending on the method chosen in ‘Bxnl Nlls Method’, see Regularization for more details.
Constraint: , or .
- ‘Bxnl Glob Method’str
Default
This argument specifies the globalization method used to estimate the next step . It also determines the class of subproblem to solve. The trust region subproblem finds the step by minimizing the specified model withing a given radius. On the other hand, when , the problem is reformulated by adding an aditional regularization term and minimized in order to find the next step . See Subproblems for more details.
Constraint: or .
- ‘Bxnl Nlls Method’str
Default
This argument defines the method used to estimate the next step in . It only applies to , or . When the globalization technique chosen is trust region () the methods for ‘Bxnl Nlls Method’ available are Powell’s dogleg method, a generalized eigenvalue method (AINT) Adachi et al. (2015), a variant of Moré–Sorensen’s method, and GALAHAD’s DTRS method. Otherwise, when the globalization method chosen is via regularization () the methods available are comprised by a linear system solver and GALAHAD’s DRQS method. See Subproblems for more details.
Constraint: , , , or .
- ‘Bxnl Model’str
Default
This argument specifies which model is used to approximate the objective function and estimate the next point that reduces the error. This is one of the most important options and should be chosen according to the problem characteristics. The models are briefly described in Models.
Constraint: , , or .
- ‘Bxnl Tn Method’str
Default
This argument specifies how to solve the subproblem and find the next step for the tensor Newton model, . The subproblems are solved using a range of regularization schemes. See Tensor Newton subproblem.
Constraint: , , , or .
- ‘Bxnl Use Second Derivatives’str
Default
This argument indicates whether the weighted sum of residual Hessians are available through the call-back . If and the specified model in ‘Bxnl Model’ requires user-suppied second derivatives, then the solver will terminate with = 6.
Constraint: or .
- ‘Bxnl Use Weights’str
Default
This argument indicates whether to use a weighted nonlinear least square model. If then the weights in [equation] must be supplied by you via
handle_set_get_real()
. If weights are to be used, then all elements must be provided, see Residual Weights. If the solver is expecting to use weights but they are not provided or have non-positive values, then the solver will terminate with = 11.Constraint: or .
- ‘Bxnl Iteration Limit’int
Default
This argument specifies the maximum amount of major iterations the solver is alloted. If this limit is reached, then the solver will terminate with = 22.
Constraint: .
- ‘Bxnl Monitor Frequency’int
Default
If , the user-supplied function will be called at the end of every th step for monitoring purposes.
Constraint: .
- ‘Bxnl Print Header’int
Default
This argument defines, in number of iterations, the frequency with which to print the iteration log header.
Constraint: .
- ‘Infinite Bound Size’float
Default
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 option does not influence constraints which have already been defined; only the constraints formulated after the change will be affected.
Constraint: .
- ‘Monitoring File’int
Default
If , the unit number for the secondary (monitoring) output. If , no secondary output is provided. The information output to this unit is controlled by ‘Monitoring Level’.
Constraint: .
- ‘Monitoring Level’int
Default
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 for ‘Print Level’.
Constraint: .
- ‘Print File’int
Default
If , the unit number 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 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: .
- ‘Print Level’int
Default
This argument defines how detailed information should be printed by the solver to the primary and secondary output.
Output
No output from the solver.
The Header and Summary.
, , ,
Additionally, the Iteration log.
Constraint: .
- ‘Print Options’str
Default
If , a listing of options will be printed to the primary output and is always printed to the secondary output.
Constraint: or .
- ‘Print Solution’str
Default
If , the final values of the primal variables are printed on the primary and secondary outputs.
If or , in addition to the primal variables, the final values of the dual variables are printed on the primary and secondary outputs.
Constraint: , , or .
- ‘Stats Time’str
Default
This argument turns on timing. 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: , , or .
- ‘Time Limit’float
Default
A limit to the number of seconds that the solver can use to solve one problem. If at the end of an iteration this limit is exceeded, the solver will terminate with = 23.
Constraint: .
- Raises
- NagValueError
- (errno )
has not been initialized.
- (errno )
does not belong to the NAG optimization modelling suite, has not been initialized properly or is corrupted.
- (errno )
has not been initialized properly or is corrupted.
- (errno )
This solver does not support the model defined in the handle.
- (errno )
The problem is already being solved.
- (errno )
Unsupported option combinations.
- (errno )
Unsupported model and method chosen.
- (errno )
On entry, , expected .
Constraint: must match the current number of variables of the model in the .
- (errno )
The information supplied does not match with that previously stored.
On entry, must match that given during the definition of the objective in the , i.e., .
- (errno )
There are no decision variables. must be greater than zero.
- (errno )
Exact second derivatives needed for tensor model.
- (errno )
Data for residual weights not found or is invalid.
- (errno )
The current starting point is unusable.
- Warns
- NagAlgorithmicMajorWarning
- (errno )
Numerical difficulties encountered and solver was terminated.
- (errno )
Iteration limit reached while solving a subproblem.
- (errno )
Line Search failed.
- (errno )
Maximum number of iterations reached.
- (errno )
The solver terminated after the maximum time allowed was exceeded.
- (errno )
The solver was terminated because no further progress could be achieved.
- (errno )
Invalid number detected in user-supplied function and recovery failed.
- NagCallbackTerminateWarning
- (errno )
User requested termination during a monitoring step.
- Notes
handle_solve_bxnl
computes a solution to the nonlinear least squares problemwhere , are smooth nonlinear functions called residuals, are weights (by default they are all defined to , see Residual Weights on how to change them), and the rightmost element represents the regularization term with argument and power (by default the regularization term is not used, see Algorithmic Details on how to enable it). The constraint elements and are -dimensional vectors defining the bounds on the variables.
Typically in a calibration or data fitting context, the residuals will be defined as the difference between the observed values at and the values provided by a nonlinear model , i.e., . If these residuals (errors) follow a Gaussian distribution, then the values of the optimal parameter vector are the maximum likelihood estimates. For a description of the various algorithms implemented for solving this problem see Algorithmic Details. It is also recommended that you read the E04 Introduction.
handle_solve_bxnl
serves as a solver for 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. First, the problem handle is initialized by callinghandle_init()
. A nonlinear least square residual objective can be added by callinghandle_set_nlnls()
and, optionally, (simple) box constraints can be defined by callinghandle_set_simplebounds()
. It should be noted thathandle_solve_bxnl
internally works with a dense representation of the residual Jacobian even if a sparse structure was defined in the call tohandle_set_nlnls()
. Once the problem is fully described, the handle may be passed to the solverhandle_solve_bxnl
. When the handle is not needed anymore,handle_free()
should be called to destroy it and deallocate the memory held within. For more information refer to the NAG optimization modelling suite in the E04 Introduction.The algorithm is based on the trust region framework and its behaviour can be modified by various options (see Other Parameters) which can be set by
handle_opt_set()
andhandle_opt_set_file()
anytime between the initialization of the handle byhandle_init()
and a call to the solver. 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 option getterhandle_opt_get()
can be called to retrieve the current value of any option.Several options might have significant impact on the performance of the solver. Even though the defaults were chosen to suit the majority of anticipated problems, it is recommended that you experiment with the option settings to find the most suitable set of options for a particular problem, see Algorithmic Details and Other Parameters for further details.
- References
Adachi, S, Iwata, S, Nakatsukasa, Y, and Takeda, A, 2015, Solving the trust region subproblem by a generalized eigenvalue problem, Technical report, METR 2015-14., Mathematical Engineering, The University of Tokyo, https://www.keisu.t.u-tokyo.ac.jp/data/2015/METR15-14.pdf
Conn, A R, Gould, N I M and Toint, Ph L, 2000, Trust Region Methods, SIAM, Philadephia
Gould, N I M, Orban, D, and Toint, Ph L, 2003, GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization, ACM Transactions on Mathematical Software (TOMS) (29(4)), 353–372
Gould, N I M, Rees, T, and Scott, J A, 2017, A higher order method for solving nonlinear least-squares problems, Technical report, RAL-P-1027-010, RAL Library. STFC Rutherford Appleton Laboratory, http://www.numerical.rl.ac.uk/people/rees/pdf/RAL-P-2017-010.pdf
Kanzow, C, Yamashita, N, and Fukushima, M, 2004, Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints, Journal of Computational and Applied Mathematics (174), 375–397
Lanczos, C, 1956, Applied Analysis, 272–280, Prentice Hall, Englewood Cliffs, NJ, USA
Nielsen, H B, 1999, Damping parameter in Marquadt’s Method, Technical report TR IMM-REP-1999-05., Department of Mathematical Modelling, Technical University of Denmark, http://www2.imm.dtu.dk/documents/ftp/tr99/tr05_99.pdf
Nocedal, J and Wright, S J, 2006, Numerical Optimization, (2nd Edition), Springer Series in Operations Research, Springer, New York