naginterfaces.library.glopt.bnd_​mcs_​solve

naginterfaces.library.glopt.bnd_mcs_solve(objfun, ibound, bl, bu, comm, iinit=0, sdlist=3, inlist=None, numpts=None, initpt=None, monit=None, data=None, io_manager=None)

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

The initialization function bnd_mcs_init() must have been called before calling bnd_mcs_solve.

Note: this function uses optional algorithmic parameters, see also: bnd_mcs_init(), bnd_mcs_optset_file(), bnd_mcs_optset_string(), bnd_mcs_optset_char(), bnd_mcs_optset_int(), bnd_mcs_optset_real(), bnd_mcs_option_check(), bnd_mcs_optget_char(), bnd_mcs_optget_int(), bnd_mcs_optget_real().

Deprecated since version 28.3.0.0: bnd_mcs_solve is deprecated. Please use handle_solve_mcs() instead. See also the Replacement Calls document.

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

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

Parameters

objfuncallable f = objfun(x, nstate, data=None)

$objfun$ must evaluate the objective function $F\left(x\right)$ for a specified $n$-vector $x$.

Parameters

xfloat, ndarray, shape $\left(n\right)$

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

nstateint

If $nstate=1$ then bnd_mcs_solve is calling $objfun$ for the first time. This argument setting allows you to save computation time if certain data must be read or calculated only once.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

Returns

ffloat

Must be set to the value of the objective function at $x$.

iboundint

Indicates whether the facility for dealing with bounds of special forms is to be used. $ibound$ must be set to one of the following values.

$ibound=0$

You will supply $\ell$ and $u$ individually.

$ibound=1$

There are no bounds on $x$.

$ibound=2$

There are semi-infinite bounds $0\le x$.

$ibound=3$

There are constant bounds $\ell ={\ell }_1$ and $u=u_1$.

Note that it only makes sense to fix any components of $x$ when $ibound=0$.

blfloat, array-like, shape $\left(n\right)$

$bl$ is $\ell$, the array of lower bounds.

bufloat, array-like, shape $\left(n\right)$

$bu$ is $u$, the array of upper bounds.

commdict, communication object, modified in place

Communication structure.

This argument must have been initialized by a prior call to bnd_mcs_init().

iinitint, optional

Selects which initialization method to use.

$iinit=0$

Simple initialization (boundary and midpoint), with

$numpts[i-1]=3$, $initpt[i-1]=2$ and

$inlist[i-1,0]=bl[i-1]$, $inlist[i-1,1]=\left(bl\right[i-1]+bu[i-1\left]\right)/2$, $inlist[i-1,2]=bu[i-1]$,

for $i=1,2,\dots ,n$.

$iinit=1$

Simple initialization (off-boundary and midpoint), with

$numpts[i-1]=3$, $initpt[i-1]=2$ and

$inlist[i-1,0]=\left(5bl\right[i-1]+bu[i-1\left]\right)/6$, $inlist[i-1,1]=\left(bl\right[i-1]+bu[i-1\left]\right)/2$, $inlist[i-1,2]=\left(bl\right[i-1]+5bu[i-1\left]\right)/6$,

for $i=1,2,\dots ,n$.

$iinit=2$

Initialization using linesearches.

$iinit=3$

You are providing your own initialization list.

$iinit=4$

Generate a random initialization list.

For more information on methods $iinit=2$, $3$ or $4$ see Initialization and Sweeps.

If ‘infinite’ values (as determined by the value of the option ‘Infinite Bound Size’) are detected by bnd_mcs_solve when you are using a simple initialization method ($iinit=0$ or $1$), a safeguarded initialization procedure will be attempted, to avoid overflow.

sdlistint, optional

When $iinit=4$, this argument is used to determine the maximal number of random initialization points to use in any given dimension. Otherwise a value is inferred internally.

inlistNone or float, array-like, shape $(n,sdlist)$, optional

This argument need not be set on entry if you wish to use one of the preset initialization methods ($iinit\ne 3$).

$inlist$ is the ‘initialization list’: whenever a sub-box in the algorithm is split for the first time (either during the initialization procedure or later), for each non-fixed coordinate $i$ the split is done at the values $inlist[i-1,0:numpts[i-1\left]\right]$, as well as at some adaptively chosen intermediate points.

The array sections $inlist[\text{i}-1,0:numpts[\text{i}-1\left]\right]$, for $\text{i}=1,2,\dots ,n$, must be in ascending order with each entry being distinct.

In this context, ‘distinct’ should be taken to mean relative to the safe-range parameter (see machine.real_safe).

numptsNone or int, array-like, shape $\left(n\right)$, optional

This argument need not be set on entry if you wish to use one of the preset initialization methods ($iinit\ne 3$).

$numpts$ encodes the number of splitting points in each non-fixed dimension.

initptNone or int, array-like, shape $\left(n\right)$, optional

This argument need not be set on entry if you wish to use one of the preset initialization methods ($iinit\ne 3$).

You must designate a point stored in $inlist$ that you wish bnd_mcs_solve to consider as an ‘initial point’ for the purposes of the splitting procedure.

Call this initial point $x^{\ast }$.

The coordinates of $x^{\ast }$ correspond to a set of indices $J_{\text{i}}$, for $\text{i}=1,2,\dots ,n$, such that $x_{\text{i}}^{\ast }$ is stored in $inlist[\text{i}-1,J_{\text{i}}-1]$, for $\text{i}=1,2,\dots ,n$.

You must set $initpt[\text{i}-1]=J_{\text{i}}$, for $\text{i}=1,2,\dots ,n$.

monitNone or callable monit(ncall, xbest, icount, inlist, numpts, initpt, xbaskt, boxl, boxu, nstate, data=None), optional

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

$monit$ may be used to monitor the optimization process.

It is invoked upon every successful completion of the procedure in which a sub-box is considered for splitting.

It will also be called just before bnd_mcs_solve exits if that splitting procedure was not successful.

If no monitoring is required, $monit$ may be None.

Parameters

ncallint

The cumulative number of calls to $objfun$.

xbestfloat, ndarray, shape $\left(n\right)$

The current best point.

icountint, ndarray, shape $\left(6\right)$

An array of counters.

$icount\left[0\right]$

$\text{nboxes}$, the current number of sub-boxes.

$icount\left[1\right]$

$\text{ncloc}$, the cumulative number of calls to $objfun$ made in local searches.

$icount\left[2\right]$

$\text{nloc}$, the cumulative number of points used as start points for local searches.

$icount\left[3\right]$

$\text{nsweep}$, the cumulative number of sweeps through levels.

$icount\left[4\right]$

$\text{m}$, the cumulative number of splits by initialization list.

$icount\left[5\right]$

$\text{s}$, the current lowest level containing non-split boxes.

inlistfloat, ndarray, shape $(n,\text{ninit})$

The initialization list.

numptsint, ndarray, shape $\left(n\right)$

The number of points in each coordinate at which to split according to the initialization list $inlist$.

initptint, ndarray, shape $\left(n\right)$

A pointer to the ‘initial point’ in $inlist$. Element $initpt[i-1]$ is the column index in $inlist$ of the $i$th coordinate of the initial point.

xbasktfloat, ndarray, shape $(n,\text{nbaskt})$

Note: the $j$th candidate minimum has its $i$th coordinate stored in $xbaskt[\text{j}-1,\text{i}-1]$, for $\text{j}=1,2,\dots ,\text{nbaskt}$, for $\text{i}=1,2,\dots ,n$.

The ‘shopping basket’ of candidate minima.

boxlfloat, ndarray, shape $\left(n\right)$

The array of lower bounds of the current search box.

boxufloat, ndarray, shape $\left(n\right)$

The array of upper bounds of the current search box.

nstateint

Is set by bnd_mcs_solve to indicate at what stage of the minimization $monit$ was called.

$nstate=1$

This is the first time that $monit$ has been called.

$nstate=-1$

This is the last time $monit$ will be called.

$nstate=0$

This is the first and last time $monit$ will be called.

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

blfloat, ndarray, shape $\left(n\right)$

$bl$ is $\ell$, the array of lower bounds.

bufloat, ndarray, shape $\left(n\right)$

$bu$ is $u$, the array of upper bounds.

inlistfloat, ndarray, shape $(n,sdlist)$

Unless $errno$ = 1, 2 or NagMemoryError on exit, the actual initialization data used by bnd_mcs_solve. If you wish to monitor the contents of $inlist$ you are advised to do so solely through $monit$, not through the output value here.

numptsint, ndarray, shape $\left(n\right)$

Unless $errno$ = 1, 2 or NagMemoryError on exit, the actual initialization data used by bnd_mcs_solve.

initptint, ndarray, shape $\left(n\right)$

Unless $errno$ = 1, 2 or NagMemoryError on exit, the actual initialization data used by bnd_mcs_solve.

xfloat, ndarray, shape $\left(n\right)$

If no exception or warning is raised, contains an estimate of the global optimum (see also Accuracy).

objfloat

If no exception or warning is raised, contains the function value at $x$.

If you request early termination of bnd_mcs_solve in $objfun$ or $monit$, there is no guarantee that the function value at $x$ equals $obj$.

Other Parameters

‘Defaults’valueless

This special keyword is used to reset all options to their default values, and any random state stored in the array $\text{comm}$ will be destroyed.

Any option value given with this keyword will be ignored. This option cannot be queried or got.

‘Function Evaluations Limit’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 $\text{nf}$ may be made.

‘Infinite Bound Size’float

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

This defines the ‘infinite’ bound $\text{infbnd}$ in the definition of the problem constraints. Any upper bound greater than or equal to $\text{infbnd}$ will be regarded as $\infty$ (and similarly any lower bound less than or equal to $-\text{infbnd}$ will be regarded as $-\infty$).

‘Local Searches’str

Default $=\text{'ON'}$

If you want to try to accelerate convergence of bnd_mcs_solve by starting local searches from candidate minima, you will require $\text{lcsrch}$ to be ‘ON’.

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

‘Local Searches Tolerance’float

Default $=2ϵ$

The value of $\text{loctol}$ 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.

‘Minimize’valueless

Default

These keywords specify the required direction of optimization. Any option value given with these keywords will be ignored.

‘Maximize’valueless

These keywords specify the required direction of optimization. Any option value given with these keywords will be ignored.

‘Nolist’valueless

Default

Option ‘List’ enables printing of each option specification as it is supplied. ‘Nolist’ suppresses this printing.

‘List’valueless

Option ‘List’ enables printing of each option specification as it is supplied. ‘Nolist’ suppresses this printing.

‘Repeatability’str

Default $=\text{'OFF'}$

For use with random initialization lists ($iinit=4$). When set to ‘ON’, an internally-initialized random state is stored in the array $\text{comm}$ for use in subsequent calls to bnd_mcs_solve.

‘Splits Limit’int

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

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

‘Static Limit’int

Default $=3n_r$

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

‘Target Objective Error’float

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

If you have given a target objective value to reach in $\text{objval}$ (the value of the option ‘Target Objective Value’), $\text{objerr}$ sets your desired relative error (from above if ‘Minimize’ is set, from below if ‘Maximize’ is set) between $obj$ and $\text{objval}$, as described in Accuracy. See also the description of the option ‘Target Objective Safeguard’.

‘Target Objective Safeguard’float

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

If you have given a target objective value to reach in $\text{objval}$ (the value of the option ‘Target Objective Value’), $\text{objsfg}$ sets your desired safeguarded termination tolerance, for when $\text{objval}$ is close to zero.

‘Target Objective Value’float

This argument may be set if you wish bnd_mcs_solve to use a specific value as the target function value to reach during the optimization. Setting $\text{objval}$ overrides the default termination criterion determined by the option ‘Static Limit’.

Raises

NagValueError

(errno $1$)

Initialization function bnd_mcs_init() has not been called.

(errno $2$)

On entry, $n=⟨value⟩$.

Constraint: $n>0$.

(errno $2$)

On entry, $ibound=⟨value⟩$.

Constraint: $ibound=0$, $1$, $2$ or $3$.

(errno $2$)

On entry, $ibound=0$ or $3$ and $bl[i-1]=⟨value⟩$, $bu[i-1]=⟨value⟩$ and $i=⟨value⟩$.

Constraint: if $ibound=0$ then $bl[\text{i}-1]\le bu[\text{i}-1]$, for $\text{i}=1,2,\dots ,n$; if $ibound=3$ then $bl\left[0\right]<bu\left[0\right]$.

(errno $2$)

On entry, $ibound=3$ and $bl\left[0\right]=bu\left[0\right]=⟨value⟩$.

Constraint: if $ibound=3$ then $bl\left[0\right]<bu\left[0\right]$.

(errno $2$)

On entry, $iinit=⟨value⟩$.

Constraint: $iinit=0$, $1$, $2$, $3$ or $4$.

(errno $2$)

On entry, $iinit=⟨value⟩$ and $sdlist=⟨value⟩$.

Constraint: if $iinit\ne 2$ then $sdlist\ge 3$.

(errno $2$)

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

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

(errno $2$)

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

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

(errno $2$)

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

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

(errno $2$)

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

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

(errno $2$)

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

(errno $2$)

On entry, user-supplied $inlist[i-1,j-1]=⟨value⟩$, $i=⟨value⟩$, $j=⟨value⟩$, and $bl[i-1]=⟨value⟩$.

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

(errno $2$)

On entry, user-supplied $inlist[i-1,j-1]=⟨value⟩$, $i=⟨value⟩$, $j=⟨value⟩$, and $bu[i-1]=⟨value⟩$.

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

(errno $2$)

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

(errno $2$)

The number of non-fixed variables $n_r=0$.

Constraint: $n_r>0$.

(errno $2$)

A value of ‘Splits Limit’ ($\text{smax}$) smaller than $n_r+3$ was set: $\text{smax}=⟨value⟩$, $n_r=⟨value⟩$.

(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 ($iinit=4$) 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 $7$)

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

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.

Warns

NagAlgorithmicWarning

(errno $4$)

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

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

(errno $5$)

The function evaluations limit was exceeded.

Approximately ‘Function Evaluations Limit’ function calls have been made without your chosen termination criterion being satisfied.

NagCallbackTerminateWarning

(errno $6$)

User-supplied monitoring function requested termination.

(errno $6$)

User-supplied objective function requested termination.

Notes

bnd_mcs_solve is designed to solve modestly sized global optimization problems having simple bound-constraints only; it finds the global optimum of a nonlinear function subject to a set of bound constraints on the variables. Without loss of generality, the problem is assumed to be stated in the following form:

$${\text{minimize}}_{x\in R^n}F\left(x\right)\text{subject to}\ell \le x\le u\text{and}\ell \le u\text{,}$$

where $F\left(x\right)$ (the objective function) is a nonlinear scalar function (assumed to be continuous in a neighbourhood of a global minimum), and the bound vectors are elements of ${\overline{R}}^n$, where $\overline{R}$ denotes the extended reals $R\cup \{-\infty ,\infty \}$. Relational operators between vectors are interpreted elementwise.

The option ‘Maximize’ should be set if you wish to solve maximization, rather than minimization, problems.

If certain bounds are not present, the associated elements of $\ell$ or $u$ can be set to special values that will be treated as $-\infty$ or $+\infty$. See the description of the option ‘Infinite Bound Size’. Phrases in this document containing terms like ‘unbounded values’ should be understood to be taken relative to this option.

Fixing variables (that is, setting $l_i=u_i$ for some $i$) is allowed in bnd_mcs_solve.

The initialization function bnd_mcs_init() does not need to be called before each invocation of bnd_mcs_solve. You should be aware that a call to the initialization function will reset each option to its default value, and, if you are using repeatable randomized initialization lists (see the description of the argument $iinit$), the random state stored in the array $\text{comm}$ will be destroyed.

You must supply a function that evaluates $F\left(x\right)$; derivatives are not required.

The method used by bnd_mcs_solve 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