naginterfaces.library.glopt.handle_​solve_​mcs

naginterfaces.library.glopt.handle_solve_mcs(handle, objfun=None, monit=None, data=None, io_manager=None)

handle_solve_mcs is designed to find the global minimum or maximum of an arbitrary function, subject to simple bound-constraints using a multi-level coordinate search method. Derivatives are not required, but convergence is only guaranteed if the objective function is continuous in a neighbourhood of a global optimum. It is not intended for large problems.

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

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

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/e05/e05kbf.html

Parameters

handleHandle

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

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., opt.handle_set_linobj or opt.handle_set_quadobj was called to define a linear or quadratic objective function), $objfun$ will never be called by handle_solve_mcs 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.

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

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

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

A step is complete when the procedure in which a sub-box is considered for splitting finishes correctly.

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

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$	Number of sweeps.
$2$–$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 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 sub-boxes.
$4$	Number of splits.
$5$	Cumulative number of splits by initialization list.
$6$	The current lowest level containing no split boxes.
$7$–$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.

‘MCS Initialization Method’str

Default $=\text{SIMPLE BOUNDS}$

The solver provides several methods to produce the initial set of sub-boxes. When $\text{‘MCS Initialization Method'}=\text{'SIMPLE BOUNDS'}$, $\text{'SIMPLE OFF-BOUNDS'}$, $\text{'LINESEARCH'}$ or $\text{'RANDOM'}$, handle_solve_mcs will generate the sub-boxes internally. Please refer to Initialization and Sweeps for more details about the differences between the automatic methods.

It is also possible to create a custom initialization list by setting $\text{‘MCS Initialization Method'}=\text{'CUSTOM'}$. Creating a Custom Initialization List describes how to provide the custom initialization list to the solver.

Constraint: $\text{‘MCS Initialization Method'}=\text{'SIMPLE BOUNDS'}$, $\text{'SIMPLE OFF-BOUNDS'}$, $\text{'LINESEARCH'}$, $\text{'RANDOM'}$ or $\text{'CUSTOM'}$

‘MCS Max Objective Calls’int

Default $=100n_r^2$

This puts an approximate limit on the number of function calls allowed. The total number of calls made is checked at the top of an internal iteration loop, so it is possible that a few calls more than ‘MCS Max Objective Calls’ may be made.

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

‘MCS 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{‘MCS Monitor Frequency'}\ge 0$.

‘MCS Print Frequency’int

Default $=1$

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

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

‘MCS Local Searches’str

Default $=\text{'ON'}$

If you want to try to accelerate convergence of handle_solve_mcs by starting local searches from candidate minima, you will require ‘MCS Local Searches’ to be ‘ON’.

Constraint: $\text{‘MCS Local Searches'}=\text{'ON'}$ or $\text{'OFF'}$

‘MCS Local Searches Limit’int

Default $=50$

This defines the maximal number of iterations to be used in the trust region loop of the local-search procedure.

Constraint: $\text{‘MCS Local Searches Limit'}>0$

‘MCS Local Searches Tolerance’float

Default $=2ϵ$

The value of ‘MCS Local Searches Tolerance’ is the multiplier used during local searches as a stopping criterion for when the approximated gradient is small, in the sense described in Local Search.

Constraint: $\text{‘MCS Local Searches Tolerance'}\ge 2ϵ$

‘MCS Repeatability’str

Default $=\text{'OFF'}$

For use with random initialization lists ($\text{‘MCS Initialization Method'}=RANDOM$). When set to ‘ON’, The initialization list will be consistent for every call of handle_solve_mcs.

Constraint: $\text{‘MCS Repeatability'}=\text{'ON'}$ or $\text{'OFF'}$

‘MCS Splits Limit’int

Default $=\lfloor d(n_r+2)/3\rfloor$

Along with the initialization list, this defines a limit on the number of times the root box will be split along any single coordinate direction. If ‘MCS Local Searches’ is ‘OFF’ you may find the default value to be too small.

Constraint: $\text{‘MCS Splits Limit'}>n_r+2$

‘MCS Static Limit’int

Default $=3n_r$

As the default termination criterion, computation stops when the best function value is static for ‘MCS Static Limit’ sweeps through levels. This argument is ignored if you have specified a target value to reach in ‘MCS Target Objective Value’.

Constraint: $\text{‘MCS Static Limit'}>0$

‘MCS Target Objective Error’float

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

If you have given a target objective value to reach in ‘MCS Target Objective Value’, this option sets your desired relative error between F(x) and ‘MCS Target Objective Value’, as described in Accuracy. See also the description of the option ‘MCS Target Objective Safeguard’.

Constraint: $\text{‘MCS Target Objective Error'}\ge 2ϵ$

‘MCS Target Objective Safeguard’float

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

If you have given a target objective value to reach in ‘MCS Target Objective Value’ (the value of the option ‘MCS Target Objective Value’), this option sets your desired safeguarded termination tolerance, for when ‘MCS Target Objective Value’ is close to zero.

Constraint: $\text{‘MCS Target Objective Safeguard'}\ge 2ϵ$

‘MCS Target Objective Value’float

This argument may be set if you wish handle_solve_mcs to use a specific value as the target function value to reach during the optimization. Setting ‘MCS Target Objective Value’ overrides the default termination criterion determined by the option ‘MCS Target Objective Value’.

‘Infinite Bound Size’float

Default $=r_{max}^{\frac{1}{4}}$

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

‘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'}$.

‘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'}$.

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

A finite initialization list could not be computed internally. Consider reformulating the bounds on the problem, try providing your own initialization list, use the randomization option ($\text{‘MCS Initialization Method'}=\text{'CUSTOM'}$) or vary the value of ‘Infinite Bound Size’.

(errno $3$)

The user-supplied initialization list contained infinite values, as determined by the option ‘Infinite Bound Size’.

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

On entry, user-supplied $\text{initpt}[i-1]=⟨value⟩$, $i=⟨value⟩$.

Constraint: if $x[i-1]$ is not fixed then $\text{initpt}[\text{i}-1]\ge 1$, for $\text{i}=1,2,\dots ,\text{nvar}$.

(errno $5$)

On entry, user-supplied $\text{initpt}[i-1]=⟨value⟩$, $i=⟨value⟩$ and $\text{sdlist}=⟨value⟩$.

Constraint: if $x[i-1]$ is not fixed then $\text{initpt}[\text{i}-1]\le \text{sdlist}$, for $\text{i}=1,2,\dots ,\text{nvar}$.

(errno $5$)

On entry, user-supplied $\text{list}[i,\text{j}]=⟨value⟩$, $i=⟨value⟩$, $\text{j}=⟨value⟩$, and $\text{bl}[i-1]=⟨value⟩$.

Constraint: if $x[i-1]$ is not fixed then $\text{list}[\text{i},\text{j}]\ge \text{bl}[\text{i}-1]$, for $\text{j}=1,2,\dots ,\text{numpts}[\text{i}-1]$, for $\text{i}=1,2,\dots ,\text{nvar}$.

(errno $5$)

On entry, user-supplied $\text{list}[i,\text{j}]=⟨value⟩$, $i=⟨value⟩$, $\text{j}=⟨value⟩$, and $\text{bu}[i-1]=⟨value⟩$.

Constraint: if $x[i-1]$ is not fixed then $\text{list}[i,\text{j}]\le \text{bu}[\text{i}-1]$, for $\text{j}=1,2,\dots ,\text{numpts}[\text{i}-1]$, for $\text{i}=1,2,\dots ,\text{nvar}$.

(errno $5$)

On entry, user-supplied $\text{numpts}[i-1]=⟨value⟩$, $i=⟨value⟩$.

Constraint: if $x[i-1]$ is not fixed then $\text{numpts}[\text{i}-1]\ge 3$, for $\text{i}=1,2,\dots ,\text{nvar}$.

(errno $5$)

On entry, user-supplied $\text{numpts}[i-1]=⟨value⟩$, $i=⟨value⟩$ and $\text{sdlist}=⟨value⟩$.

Constraint: if $x[i-1]$ is not fixed then $\text{numpts}[\text{i}-1]\le \text{sdlist}$, for $\text{i}=1,2,\dots ,\text{nvar}$.

(errno $5$)

On entry, user-supplied section $\text{list}[i,1:\text{numpts}[i-1\left]\right]$ contained $\text{ndist}$ distinct elements, and $\text{ndist}<\text{numpts}[i-1]$: $\text{ndist}=⟨value⟩$, $\text{numpts}[i-1]=⟨value⟩$, $i=⟨value⟩$.

(errno $5$)

On entry, user-supplied section $\text{list}[i,1:\text{numpts}[i-1\left]\right]$ was not in ascending order: $\text{numpts}[i-1]=⟨value⟩$, $i=⟨value⟩$.

(errno $5$)

The dimension of the array ‘MCS List’ is not a multiple of $\text{nvar}$.

(errno $6$)

There were $n=⟨value⟩$ variables and the option ‘MCS Splits Limit’ $\text{smax}=⟨value⟩$.

Constraint: $\text{smax}>n+2$.

Use opt.handle_opt_set to set compatible option values.

(errno $7$)

Please provide a proper $objfun$ function.

(errno $8$)

An error occurred during linesearching. It is likely that your objective function is badly scaled: try rescaling it. Also, try relaxing the bounds or use a different initialization method. If the problem persists, please contact NAG quoting error code $⟨value⟩$.

(errno $8$)

An error occurred during initialization. It is likely that points from the initialization list are very close together. Try relaxing the bounds on the variables or use a different initialization method.

(errno $11$)

The optional parameter ‘MCS Initialization Method’ was set to CUSTOM but one of the arrays $\text{list}$, $\text{initpt}$ or $\text{numpts}$ was not passed correctly to the handle.

Warns

NagAlgorithmicWarning

(errno $21$)

The function evaluations limit was exceeded.

Approximately ‘MCS Max Objective Calls’ function calls have been made without your chosen termination criterion being satisfied.

(errno $24$)

The division procedure completed but your target value could not be reached.

Despite every sub-box being processed ‘MCS Splits Limit’ times, the target value you provided in ‘MCS Target Objective Value’ could not be found to the tolerances given in ‘MCS Target Objective Error’ and ‘MCS Target Objective Safeguard’. You could try reducing ‘MCS Splits Limit’ or the objective tolerances.

NagCallbackTerminateWarning

(errno $20$)

User-supplied monitoring function requested termination.

(errno $20$)

User-supplied objective function requested termination.

Notes

handle_solve_mcs 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_mcs 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 opt.handle_init to initialize it followed, optionally, by opt.handle_set_nlnobj, opt.handle_set_linobj or opt.handle_set_quadobj to define the objective function and opt.handle_set_simplebounds to define bounds on the variables. If opt.handle_set_simplebounds is not called, all the variables will be considered free by the solver. It should be noted that handle_solve_mcs always assumes that the gradient of the objective is dense, therefore, defining a sparse structure for the residuals in the call to opt.handle_set_nlnobj will have no effect. Additionally, the multi-level coordinate search method used by this solver relies on dividing the feasible space in ‘boxes’ (see Algorithmic Details for a more thorough explanation) so it is advisable to define reasonable bounds for the variables using opt.handle_set_simplebounds. See the E04 Introduction for more details about the NAG optimization modelling suite.

The algorithm behaviour and solver strategy can be modified by various options (see Other Parameters) which can be set by opt.handle_opt_set and opt.handle_opt_set_file at any time between the initialization of the handle by opt.handle_init and a call to the solver. The options’ names specific for this solver start with the prefix MCS (Multi-level Coordinate Search). The default values for these options are chosen to work well in the general case, but it is recommended that you tune them to your particular problem. In particular, if the objective function is known to be numerically difficult, it could be desirable to define a customized initialization list for the algorithm with the option ‘MCS Initialization Method’. For more details on how to create a custom initialization list, please refer to Creating a Custom Initialization List. Once the solver has finished, options may be modified for the next solve. The solver may be called repeatedly with various initialization lists and/or options.

The method used by handle_solve_mcs is based on MCS, the Multi-level Coordinate Search method described in Huyer and Neumaier (1999), and the algorithm it uses is described in detail in Algorithmic Details.

References

Huyer, W and Neumaier, A, 1999, Global optimization by multi-level coordinate search, Journal of Global Optimization (14), 331–355

See also

naginterfaces.library.examples.glopt.handle_solve_mcs_ex.main()