naginterfaces.library.opt.handle_​solve_​bounds_​foas

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

handle_solve_bounds_foas is a solver from the NAG optimization modelling suite for bound-constrained large-scale Nonlinear Programming (NLP) problems. It is a first-order active-set method (FOAS) that has low memory requirements and thus is suitable for very large-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 e04kf

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/e04/e04kff.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_bounds_foas. 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$ must calculate the value of the nonlinear 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_bounds_foas and may be None.

Parameters

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

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

informint

A non-negative value.

In some cases, it is known beforehand that the evaluations of the objective function and its gradient are required at the same point $x$, in such cases, $inform=1$.

This may help to optimize your code in order to avoid recalculations of common quantities when evaluating both the objective function and gradient; the objective function is always evaluated before the objective gradient.

This notification parameter may be safely ignored if such optimization is not required.

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 function cannot be evaluated at the requested point $x$ by setting $inform<0$. Returning NaN or $\pm \infty$ in $fx$ has the same effect. The algorithm will try to recover if the objective cannot be evaluated; if recovery is not possible it will stop with $errno$ = 25.

objgrdNone or callable inform = objgrd(x, fdx, inform, data=None), optional

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

$objgrd$ must calculate the values of the nonlinear objective function gradient $\frac{\partial f}{\partial x}$ at a specified point $x$.

Every call to $objgrd$ is preceded by a call to $objfun$ at the same point, if this is known in advance, both functions will be notified via $inform=1$.

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), $objgrd$ will never be called by handle_solve_bounds_foas and $objgrd$ may be None.

If the option $\text{‘FOAS Estimate Derivatives'}=\text{'YES'}$, then after returning from $objgrd$ the gradient vector is checked for missing entries which you have not supplied.

Missing entries are estimated using the finite difference method, see option ‘FOAS Estimate Derivatives’ description for more details.

Parameters

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

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

fdxfloat, ndarray, shape $\left(\text{nnzfd}\right)$, to be modified in place

On entry: the elements should only be assigned and not referenced.

On exit: the values of the nonzero elements in the sparse gradient vector of the objective function, in the order specified by $\text{idxfd}$ in a previous call to handle_set_nlnobj(). $fdx[\text{i}-1]$ will store the gradient element $\frac{\partial f}{\partial x_j}$, where $j=\text{idxfd}[\text{i}-1]$.

informint

A non-negative value.

If $inform=1$, then the previous call to $objfun$ was also made at the same point $x$ with $inform=1$.

This may help to optimize your code in order to avoid recalculations of common quantities when evaluating both the objective function and gradient.

This notification parameter may be safely ignored if such optimization is not required.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

Returns

informint

May be used to inform that the gradient cannot be evaluated at the requested point $x$ by setting $inform<0$. Returning NaN or $\pm \infty$ in any element of $fdx$ has the same effect. The algorithm will try to recover if the gradient cannot be evaluated; if recovery is not possible it will stop with $errno$ = 25.

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 and optionally to terminate the solver early if necessary.

It is invoked at the end of every $i$th iteration where $i$ is given by the ‘FOAS Monitor Frequency’ (the default is $0$, $monit$ is not called).

$monit$ may be None.

Parameters

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

The vector $x$ 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 $rinfo$.

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

Solver statistics at the end of the current iteration as described in $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)$

Error measures and various indicators at the end of the final iteration as given in the table below:

$0$	Objective function value $f\left(x\right)$.
$1$	Norm of inactive gradient, the objective gradient over the current search space. If the problem is unconstrained, then elements $1$–$3$ coincide. See Stopping Criteria for details.
$2$	Norm of projected direction, used in [equation], see Constrained Subproblem (NPG).
$3$	Norm of objective gradient.
$4$	Last step size (${\alpha }_k$) used in [equation] and [equation], see Constrained Subproblem (NPG) and Unconstrained Subproblem (CG).
$5$	Progress score, a positive value that measures the progress of the solver. A low score close to zero indicates poor progress, see [equation] in Stopping Criteria.
$6$–$99$	Reserved for future use.

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

Solver statistics at the end of the final iteration as given in the table below:

$0$	Number of function evaluations performed by NPG, see Constrained Subproblem (NPG).
$1$	Number of gradient evaluations performed by NPG.
$2$	Number of function evaluations performed by CG, see Unconstrained Subproblem (CG).
$3$	Number of gradient evaluations performed by CG.
$4$	Number of function evaluations performed by LCG.
$5$	Number of gradient evaluations performed by LCG.
$6$	Number of function evaluations used by the finite difference method to estimate missing components of the gradient.
$7$	Number of iterations.
$8$	Total time spent in the solver (including user-supplied function calls).
$9$	Total time spent in user-supplied objective function.
$10$	Total time spent in user-supplied objective gradient.
$11$–$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.

‘FOAS Estimate Derivatives’str

Default $=\text{'NO'}$

This option indicates whether to check for and estimate missing entries of the user-supplied gradient vector. Since the associated cost of estimating missing elements can be high, this option should only be used if strictly necessary. In general terms, if the gradient is not provided (in its entirety or for arbitrary points) potential degradation in the progress of the solver is to be expected. Depending on the complexity of the objective, the function may not achieve the desired optimality accuracy or even terminate with no possible further progress error $errno$ = 24, it is advisable to increase the values of ‘FOAS Stop Tolerance’ and ‘FOAS Rel Stop Tolerance’ when using this option.

Missing elements from the gradient vector are estimated by finite-differences using the perturbation interval specified by the option ‘FOAS Finite Diff Interval’.

If $\text{‘FOAS Estimate Derivatives'}=\text{'NO'}$, the entries are not checked and all derivative elements need to be provided.

Constraint: $\text{‘FOAS Estimate Derivatives'}=\text{'YES'}$ or $\text{'NO'}$.

‘FOAS Finite Diff Interval’float

Default $=\sqrt{ϵ}$

Specifies the relative perturbation size used to estimate a derivative using the forward (or backward) finite-difference method. Setting the value too small or too big may lead handle_solve_bounds_foas to terminated with $errno$ = 24 or 25.

Constraint: ${10}^{-12}\le \text{‘FOAS Finite Diff Interval'}\le {10}^{-1}$.

‘FOAS Iteration Limit’int

Default $={10}^7$

This argument sets the maximum number of iterations to be performed by handle_solve_bounds_foas. Setting the option too low might lead to $errno$ = 22.

Constraint: $\text{‘FOAS Iteration Limit'}\ge 1$.

‘FOAS Memory’int

Default $=11$

This argument specifies the maximum number of memory vectors to use in the LCG solver.

Constraint: $0\le \text{‘FOAS Memory'}\le 100$.

‘FOAS Monitor Frequency’int

Default $=0$

This argument specifies the frequency on which to call the monitor function $monit$. If zero, the monitor function will not be called.

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

‘FOAS Print Frequency’int

Default $=\text{'1'}$

This argument specifies the frequency with which to print information regarding each iteration to ‘Print File’ and/or ‘Monitoring File’. By default, it will print information of every iteration.

Constraint: $\text{‘FOAS Print Frequency'}\ge 1$.

‘FOAS Progress Tolerance’float

Default $={ϵ}^{\frac{3}{4}}$

Specifies the tolerance for ${ϵ}_{prog}$ (see [equation]) for which the function characterises a poor rate of progress given that it deems to be far from a solution. If this behaviour is persistent, then the function asserts that no substantial further progress can be achieved and the process is terminated with $errno$ = 24. Setting a high tolerance can lead to misinterpret reasonable progress for unsatisfactory progress or even issue a premature stop, see [equation] in Stopping Criteria.

Constraint: $0<\text{‘FOAS Progress Tolerance'}<1$.

‘FOAS Rel Stop Tolerance’float

Default $={ϵ}^{\frac{3}{4}}$

This argument sets the value of ${ϵ}_{\text{rel}}$ which specifies the relative tolerance for the convergence measures in the stopping criteria, see [equation] and [equation] in Stopping Criteria.

Constraint: $0\le {ϵ}_{\text{rel}}<1$.

‘FOAS Restart Factor’float

Default $=6.0$

This factor specifies the frequency $\text{nvar}\times \text{‘FOAS Restart Factor'}$ with which the CG/LCG directions are replaced by the steepest descent direction ($d_k=-g_k$). Setting the value too small can potentially slow the convergence speed.

Constraint: $\text{‘FOAS Restart Factor'}\ge 0$.

‘FOAS Slow Tolerance’float

Default $={ϵ}^{\frac{1}{8}}$

Specifies the tolerance for ${ϵ}_{slow}$ (see [equation]) for which the function characterises a slow rate of convergence. If this behaviour is deemed permanent, then the function asserts that no substantial improvement can be achieved and the process is terminated with $errno$ = 50. Setting a large tolerance can lead to incorrectly identifying a suboptimal solution, see [equation] in Stopping Criteria.

Constraint: $\text{‘FOAS Slow Tolerance'}>0$.

‘FOAS Stop Tolerance’float

Default $=max({10}^{-6},\sqrt{ϵ})$

This argument sets the value of ${ϵ}_{\text{tol}}$ which specifies the tolerance for the convergence measures in the stopping criteria, see [equation] and [equation] in Stopping Criteria.

Constraint: $0\le {ϵ}_{\text{tol}}<1$.

‘FOAS Tolerance Norm’str

Default $=\text{'INFINITY'}$

This argument specifies the norm used to measure some stopping metrics, such as optimality tolerances (see Stopping Criteria). It is possible to choose between 2-norm and ∞-norm. Solving problems using ∞-norm generally has lower computational costs than those based on 2-norm.

Constraint: $\text{‘FOAS Tolerance Norm'}=\text{'INFINITY'}$ or $\text{'TWO'}$.

‘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 set to $-1$, no secondary output is provided. The following information is output to the unit:

• a listing of the options;

• problem statistics, the iteration log and the final status as set by ‘Monitoring Level’;

• the solution if set by ‘Print Solution’.

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 ‘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 option’s initialization, e.g., at the initialization of the handle. The following information is output to the unit:

• a listing of options if set by ‘Print Options’;

• problem statistics, the iteration log and the final status from the solver as set by ‘Print Level’;

• the solution if set by ‘Print Solution’.

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

$i$	Output
$0$	No output from the solver
$1$	Only the final status and the objective value
$2$	Problem statistics, one line per iteration showing the progress of the solution with respect to the convergence measures, final status and statistics
$3$	As level $2$ but each iteration line is longer and includes step length and progress measure
$4,5$	As level $3$ but further details of each iteration are presented

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.

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

‘Print Solution’str

Default $=\text{'NO'}$

If $\text{‘Print Solution'}=\text{'YES'}$, the final values of the solution vector are printed on the primary and secondary outputs.

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

‘Stats Time’str

Default $=\text{'NO'}$

This argument allows you to turn 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'}$.

‘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. If no objective function is set, ‘Task’ reverts to ‘FEASIBLE POINT’ automatically.

Constraint: $\text{‘Task'}=\text{'MINIMIZE'}$, $\text{'MAXIMIZE'}$ or $\text{'FEASIBLE POINT'}$.

‘Time Limit’float

Default $={10}^6$

This argument specifies a limit in 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 error message.

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

‘Verify Derivatives’str

Default $=\text{'NO'}$

This argument specifies whether the function should perform numerical checks on the consistency of the user-supplied gradient function. If any discrepancies are found, $errno$ = 26 is returned. It is recommended that such checks are enabled when first developing the formulation of the problem, however, the verification process results in a significant increase of the number of the function evaluations and thus it shouldn’t be used in production code.

Constraint: $\text{‘Verify Derivatives'}=\text{'YES'}$ or $\text{'NO'}$.

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

Please provide a proper $objfun$ function.

(errno $7$)

Please provide a proper $objgrd$ function.

(errno $21$)

The current starting point is unusable.

(errno $26$)

User-provided gradient is likely to be incorrect.

Warns

NagAlgorithmicWarning

(errno $50$)

Problem was solved to an acceptable level; full accuracy was not achieved.

(errno $54$)

The problem seems to be unbounded and the algorithm was stopped.

NagAlgorithmicMajorWarning

(errno $22$)

Maximum number of iterations reached.

(errno $23$)

The solver terminated after the maximum time allowed was exhausted.

(errno $24$)

The solver was terminated because no further progress could be achieved.

(errno $25$)

Invalid number detected in user-supplied function and recovery failed.

(errno $25$)

Invalid number detected in user-supplied gradient and recovery failed.

NagCallbackTerminateWarning

(errno $20$)

User requested termination during a monitoring step.

Notes

handle_solve_bounds_foas solves large-scale bound-constrained nonlinear optimization problems of the form

$${\text{minimize}}_{x\in R^n}f\left(x\right)\text{subject to}{\ell }_x\le x\le u_x\text{,}$$

where $n$ is the number of decision variables, ${\ell }_x$, $u_x$, and $x$ are $n$-dimensional vectors, and the nonlinear objective function $f\left(x\right)$ is assumed to be sufficiently smooth.

The solver is a first-order method (i.e., uses only first derivatives) that has very low memory requirements and, therefore, is suitable for very large bound-constrained problems. It is based on an active-set method coupled to a nonmonotone projected gradient algorithm (NPG), nonlinear conjugate gradient method (CG) and its limited-memory variant (LCG). The active-set method is based on alternating between both solvers, the NPG step handles the box constraints and identifies a suitable search space while the CG step explores it for a solution.

For a detailed description of the algorithm see Algorithmic Details. Under standard assumptions on the problem (smoothness of the first derivative of the objective) the algorithm converges to a local solution or to a critical point.

handle_solve_bounds_foas 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 calling handle_init(). Then some of the functions handle_set_linobj(), handle_set_quadobj(), handle_set_nlnobj() or handle_set_simplebounds() may be called to formulate the objective and to define (simple) box constraints for the problem. Once the problem is fully described, the handle may be passed to the solver handle_solve_bounds_foas. When the handle is no longer needed, handle_free() should be called to destroy it and deallocate the memory held within. See the E04 Introduction for more details about the NAG optimization modelling suite.

The algorithm behaviour can be modified by various options (see Other Parameters) which can be set by handle_opt_set() and handle_opt_set_file() anytime between the initialization of the handle by handle_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. Option getter handle_opt_get() can be called to retrieve the current value of any option.

The option ‘Task’ may be used to switch the problem to maximization, while ‘FOAS Estimate Derivatives’ can be used to complete missing elements from the gradient. Option ‘Verify Derivatives’ may help verify the correctness of the gradient vector before starting to solve a problem.

Several options may have significant impact on the performance of the solver. Even if the defaults were chosen to suit the majority of problems, it is recommended that you experiment in order to find the most suitable set of options for a particular problem, see Algorithmic Details and Other Parameters for further details.

References

Dai, Y-H and Kou, C-X, 2013, A Nonlinear Conjugate Gradient Algorithm with an Optimal Property and an Improved Wolfe Line Search, SIAM J. Optim. (23(1)), 296–320

Gill, P E and Leonard, M W, 2003, Limited-Memory Reduced-Hessian Methods for Large-Scale Unconstrained Optimization, SIAM J. Optim. (14(2)), 380–401

Hager, W W and Zhang, H, 2005, A New Conjugate Gradient Method with Guaranteed Descent and an Efficient Line Search, SIAM J. Optim. (16(1)), 170–192

Hager, W W and Zhang, H, 2006, Algorithm 851: CG DESCENT, a Conjugate Gradient Method with Guaranteed Descent, ACM Trans. Math. Software (32(1)), 113–137

Hager, W W and Zhang, H, 2006, A New Active Set Algorithm for Box Constrained Optimization, SIAM J. Optim. (17(2)), 525–557

Hager, W W and Zhang, H, 2013, The Limited Memory Conjugate Gradient Method, SIAM J. Optim. (23(4)), 2150–2168

Nocedal, J and Wright, S J, 2006, Numerical Optimization, (2nd Edition), Springer Series in Operations Research, Springer, New York

See also

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