Note:this function 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.
e05sac is designed to search for the global minimum or maximum of an arbitrary function, using Particle Swarm Optimization (PSO). Derivatives are not required, although these may be used by an accompanying local minimization function if desired. e05sac is essentially identical to e05sbc, but with a simpler interface and with various optional parameters removed; otherwise most arguments are identical. In particular, e05sac does not handle general constraints.
The function may be called by the names: e05sac or nag_glopt_bnd_pso.
Before calling e05sac, e05zkcmust be called with optstr set to ‘Initialize = e05sac’. Optional parameters may also be specified by calling e05zkc before the call to e05sac.
3Description
e05sac uses a stochastic method based on Particle Swarm Optimization (PSO) to search for the global optimum of a nonlinear function $F$, subject to a set of bound constraints on the variables. In the PSO algorithm (see Section 11), a set of particles is generated in the search space, and advances each iteration to (hopefully) better positions using a heuristic velocity based upon inertia, cognitive memory and global memory. The inertia is provided by a decreasingly weighted contribution from a particles current velocity, the cognitive memory refers to the best candidate found by an individual particle and the global memory refers to the best candidate found by all the particles. This allows for a global search of the domain in question.
Further, this may be coupled with a selection of local minimization functions, which may be called during the iterations of the heuristic algorithm, the interior phase, to hasten the discovery of locally optimal points, and after the heuristic phase has completed to attempt to refine the final solution, the exterior phase. Different options may be set for the local optimizer in each phase.
Without loss of generality, the problem is assumed to be stated in the following form:
$$\underset{\mathbf{x}\in {R}^{\mathit{ndim}}}{\mathrm{minimize}}\phantom{\rule{0.25em}{0ex}}\hspace{0.17em}F\left(\mathbf{x}\right)\text{\hspace{1em} subject to \hspace{1em}}\mathbf{\ell}\le \mathbf{x}\le \mathbf{u}\text{,}$$
where the objective $F\left(\mathbf{x}\right)$ is a scalar function, $\mathbf{x}$ is a vector in ${R}^{\mathit{ndim}}$ and the vectors $\mathbf{\ell}\le \mathbf{u}$ are lower and upper bounds respectively for the $\mathit{ndim}$ variables. The objective function may be nonlinear. Continuity of $F$ is not essential. For functions which are smooth and primarily unimodal, faster solutions will almost certainly be achieved by using Chapter E04 functions directly.
For functions which are smooth and multi-modal, gradient dependent local minimization functions may be coupled with e05sac.
For multi-modal functions for which derivatives cannot be provided, particularly functions with a significant level of noise in their evaluation, e05sac should be used either alone, or coupled with e04cbc.
The $\mathit{ndim}$ lower and upper box bounds on the variable $\mathbf{x}$ are included to initialize the particle swarm into a finite hypervolume, although their subsequent influence on the algorithm is user determinable (see the option ${\mathbf{Boundary}}$ in Section 12). It is strongly recommended that sensible bounds are provided for all variables.
e05sac may also be used to maximize the objective function (see the option ${\mathbf{Optimize}}$).
Due to the nature of global optimization, unless a predefined target is provided, there is no definitive way of knowing when to end a computation. As such several stopping heuristics have been implemented into the algorithm. If any of these is achieved, e05sac will exit with ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$NW_SOLUTION_NOT_GUARANTEED, and the parameter inform will indicate which criteria was reached. See inform for more information.
In addition, you may provide your own stopping criteria through monmod and objfun.
e05sbc provides a comprehensive interface, allowing for the inclusion of general nonlinear constraints.
4References
Gill P E, Murray W and Wright M H (1981) Practical Optimization Academic Press
Kennedy J and Eberhart R C (1995) Particle Swarm Optimization Proceedings of the 1995 IEEE International Conference on Neural Networks 1942–1948
Koh B, George A D, Haftka R T and Fregly B J (2006) Parallel Asynchronous Particle Swarm Optimization International Journal for Numerical Methods in Engineering67(4) 578–595
Vaz A I and Vicente L N (2007) A Particle Swarm Pattern Search Method for Bound Constrained Global Optimization Journal of Global Optimization39(2) 197–219 Kluwer Academic Publishers
5Arguments
Note: for descriptions of the symbolic variables, see Section 11.
1: $\mathbf{ndim}$ – IntegerInput
On entry: $\mathit{ndim}$, the number of dimensions.
Constraint:
${\mathbf{ndim}}\ge 1$.
2: $\mathbf{npar}$ – IntegerInput
On entry: $\mathit{npar}$, the number of particles to be used in the swarm. Assuming all particles remain within bounds, each complete iteration will perform at least npar function evaluations. Otherwise, significantly fewer objective function evaluations may be performed.
On entry: ${\mathbf{bl}}$ is $\mathbf{\ell}$, the array of lower bounds, bu is $\mathbf{u}$, the array of upper bounds. The ndim entries in bl and bu must contain the lower and upper simple (box) bounds of the variables respectively. These must be provided to initialize the sample population into a finite hypervolume, although their subsequent influence on the algorithm is user determinable (see the option ${\mathbf{Boundary}}$ in Section 12).
If ${\mathbf{bl}}\left[i-1\right]={\mathbf{bu}}\left[i-1\right]$ for any $i\in \{1,\dots ,{\mathbf{ndim}}\}$, variable $i$ will remain locked to ${\mathbf{bl}}\left[i-1\right]$ regardless of the ${\mathbf{Boundary}}$ option selected.
It is strongly advised that you place sensible lower and upper bounds on all variables, even if your model allows for variables to be unbounded (using the option ${\mathbf{Boundary}}=\mathrm{ignore}$) since these define the initial search space.
Constraints:
${\mathbf{bl}}\left[\mathit{i}-1\right]\le {\mathbf{bu}}\left[\mathit{i}-1\right]$, for $\mathit{i}=1,2,\dots ,{\mathbf{ndim}}$;
${\mathbf{bl}}\left[i-1\right]\ne {\mathbf{bu}}\left[i-1\right]$ for at least one $i\in \{1,\dots ,{\mathbf{ndim}}\}$.
7: $\mathbf{objfun}$ – function, supplied by the userExternal Function
objfun must, depending on the value of mode, calculate the objective function and/or calculate the gradient of the objective function for a $\mathit{ndim}$-variable vector $\mathbf{x}$. Gradients are only required if a local minimizer has been chosen which requires gradients. See the option ${\mathbf{Local\; Minimizer}}$ for more information.
On entry: indicates which functionality is required.
${\mathbf{mode}}=0$
$F\left(\mathbf{x}\right)$ should be returned in objf. The value of objf on entry may be used as an upper bound for the calculation. Any expected value of $F\left(\mathbf{x}\right)$ that is greater than objf may be approximated by this upper bound; that is objf can remain unaltered.
${\mathbf{mode}}=1$
${\mathbf{Local\; Minimizer}}=\mathrm{e04ucc}$ only First derivatives can be evaluated and returned in vecout. Any unaltered elements of vecout will be approximated using finite differences.
${\mathbf{mode}}=2$
${\mathbf{Local\; Minimizer}}=\mathrm{e04ucc}$ only $F\left(\mathbf{x}\right)$must be calculated and returned in objf, and available first derivatives can be evaluated and returned in vecout. Any unaltered elements of vecout will be approximated using finite differences.
${\mathbf{mode}}=5$
$F\left(\mathbf{x}\right)$must be calculated and returned in objf. The value of objf on entry may not be used as an upper bound.
${\mathbf{mode}}=6$
${\mathbf{Local\; Minimizer}}=\mathrm{e04dgc}$ only All first derivatives must be evaluated and returned in vecout.
${\mathbf{mode}}=7$
${\mathbf{Local\; Minimizer}}=\mathrm{e04dgc}$ only $F\left(\mathbf{x}\right)$must be calculated and returned in objf, and all first derivatives must be evaluated and returned in vecout.
On exit: if the value of mode is set to be negative, e05sac will exit as soon as possible with ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$NE_USER_STOP and ${\mathbf{inform}}={\mathbf{mode}}$.
On entry: $\mathbf{x}$, the point at which the objective function and/or its gradient are to be evaluated.
4: $\mathbf{objf}$ – double *Input/Output
On entry: the value of objf passed to objfun varies with the argument mode.
${\mathbf{mode}}=0$
objf is an upper bound for the value of $F\left(\mathbf{x}\right)$, often equal to the best value of $F\left(\mathbf{x}\right)$ found so far by a given particle. Only objective function values less than the value of objf on entry will be used further. As such this upper bound may be used to stop further evaluation when this will only increase the objective function value above the upper bound.
On entry: if ${\mathbf{Local\; Minimizer}}=\mathrm{e04ucc}$, the values of vecout are used internally to indicate whether a finite difference approximation is required. See e04ucc.
On exit: the required values of vecout returned to the calling function depend on the value of mode.
vecout can contain components of the gradient of the objective function $\frac{\partial F}{\partial {x}_{i}}$ for some $i=1,2,\dots {\mathbf{ndim}}$, or acceptable approximations. Any unaltered elements of vecout will be approximated using finite differences.
${\mathbf{mode}}=6$ or $7$
vecout must contain the gradient of the objective function $\frac{\partial F}{\partial {x}_{i}}$ for all $i=1,2,\dots {\mathbf{ndim}}$. Approximation of the gradient is strongly discouraged, and no finite difference approximations will be performed internally (see e04dgc).
6: $\mathbf{nstate}$ – IntegerInput
On entry: nstate indicates various stages of initialization throughout the function. This allows for permanent global arguments to be initialized the least number of times. For example, you may initialize a random number generator seed.
${\mathbf{nstate}}=2$
objfun is called for the very first time. You may save computational time if certain data must be read or calculated only once.
${\mathbf{nstate}}=1$
objfun is called for the first time by a NAG local minimization function. You may save computational time if certain data required for the local minimizer need only be calculated at the initial point of the local minimization.
${\mathbf{nstate}}=0$
Used in all other cases.
7: $\mathbf{comm}$ – Nag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to objfun.
user – double *
iuser – Integer *
p – Pointer
The type Pointer will be void *. Before calling e05sac you may allocate memory and initialize these pointers with various quantities for use by objfun when called from e05sac (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).
Note:objfun should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by e05sac. If your code inadvertently does return any NaNs or infinities, e05sac is likely to produce unexpected results.
8: $\mathbf{monmod}$ – function, supplied by the userExternal Function
A user-specified monitoring and modification function. monmod is called once every complete iteration after a finalization check. It may be used to modify the particle locations that will be evaluated at the next iteration. This permits the incorporation of algorithmic modifications such as including additional advection heuristics and genetic mutations. monmod is only called during the main loop of the algorithm, and as such will be unaware of any further improvement from the final local minimization. If no monitoring and/or modification is required, monmod may be NULLFN.
Note: the $i$th component of the $j$th particle, ${x}_{j}\left(i\right)$, is stored in ${\mathbf{x}}\left[\left(j-1\right)\times {\mathbf{ndim}}+i-1\right]$.
On entry: the npar particle locations, ${\mathbf{x}}_{j}$, which will currently be used during the next iteration unless altered in monmod.
On exit: the particle locations to be used during the next iteration.
Note: the $i$th component of the position of the $j$th particle's cognitive memory, ${\hat{x}}_{j}\left(i\right)$, is stored in ${\mathbf{xbest}}\left[\left(j-1\right)\times {\mathbf{ndim}}+i-1\right]$.
On entry: the locations currently in the cognitive memory,
${\hat{\mathbf{x}}}_{\mathit{j}}$, for $\mathit{j}=1,2,\dots ,{\mathbf{npar}}$ (see Section 11).
On entry: the objective values currently in the cognitive memory,
$F\left({\hat{\mathbf{x}}}_{\mathit{j}}\right)$, for $\mathit{j}=1,2,\dots ,{\mathbf{npar}}$.
On entry: iteration and function evaluation counters (see description of itt below).
9: $\mathbf{comm}$ – Nag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to monmod.
user – double *
iuser – Integer *
p – Pointer
The type Pointer will be void *. Before calling e05sac you may allocate memory and initialize these pointers with various quantities for use by monmod when called from e05sac (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).
10: $\mathbf{inform}$ – Integer *Input/Output
On entry: ${\mathbf{inform}}=0$
On exit: setting ${\mathbf{inform}}<0$ will cause near immediate exit from e05sac. This value will be returned as inform with ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$NE_USER_STOP. You need not set inform unless you wish to force an exit.
Note:monmod should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by e05sac. If your code inadvertently does return any NaNs or infinities, e05sac is likely to produce unexpected results.
Note: the dimension, $\mathit{dim}$, of this array is dictated by the requirements of associated functions that must have been previously called. This array MUST be the same array passed as argument iopts in the previous call to e05zkc.
On entry: optional parameter array as generated and possibly modified by calls to e05zkc. The contents of iopts MUST NOT be modified directly between calls to e05sac, e05zkcore05zlc.
Note: the dimension, $\mathit{dim}$, of this array is dictated by the requirements of associated functions that must have been previously called. This array MUST be the same array passed as argument opts in the previous call to e05zkc.
On entry: optional parameter array as generated and possibly modified by calls to e05zkc. The contents of opts MUST NOT be modified directly between calls to e05sac, e05zkcore05zlc.
11: $\mathbf{comm}$ – Nag_Comm *
The NAG communication argument (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).
12: $\mathbf{itt}\left[6\right]$ – IntegerOutput
On exit: integer iteration counters for e05sac.
${\mathbf{itt}}\left[0\right]$
Number of complete iterations.
${\mathbf{itt}}\left[1\right]$
Number of complete iterations without improvement to the current optimum.
${\mathbf{itt}}\left[2\right]$
Number of particles converged to the current optimum.
${\mathbf{itt}}\left[3\right]$
Number of improvements to the optimum.
${\mathbf{itt}}\left[4\right]$
Number of function evaluations performed.
${\mathbf{itt}}\left[5\right]$
Number of particles reset.
13: $\mathbf{inform}$ – Integer *Output
On exit: indicates which finalization criterion was reached. The possible values of inform are:
The provided objective target has been achieved. (${\mathbf{Target\; Objective\; Value}}$).
2
The standard deviation of the location of all the particles is below the set threshold (${\mathbf{Swarm\; Standard\; Deviation}}$). If the solution returned is not satisfactory, you may try setting a smaller value of ${\mathbf{Swarm\; Standard\; Deviation}}$, or try adjusting the options governing the repulsive phase (${\mathbf{Repulsion\; Initialize}}$, ${\mathbf{Repulsion\; Finalize}}$).
3
The total number of particles converged (${\mathbf{Maximum\; Particles\; Converged}}$) to the current global optimum has reached the set limit. This is the number of particles which have moved to a distance less than ${\mathbf{Distance\; Tolerance}}$ from the optimum with regard to the ${L}^{2}$ norm. If the solution is not satisfactory, you may consider lowering the ${\mathbf{Distance\; Tolerance}}$. However, this may hinder the global search capability of the algorithm.
4
The maximum number of iterations without improvement (${\mathbf{Maximum\; Iterations\; Static}}$) has been reached, and the required number of particles (${\mathbf{Maximum\; Iterations\; Static\; Particles}}$) have converged to the current optimum. Increasing either of these options will allow the algorithm to continue searching for longer. Alternatively if the solution is not satisfactory, re-starting the application several times with ${\mathbf{Repeatability}}=\mathrm{OFF}$ may lead to an improved solution.
5
The maximum number of iterations (${\mathbf{Maximum\; Iterations\; Completed}}$) has been reached. If the number of iterations since improvement is small, then a better solution may be found by increasing this limit, or by using the option ${\mathbf{Local\; Minimizer}}$ with corresponding exterior options. Otherwise if the solution is not satisfactory, you may try re-running the application several times with ${\mathbf{Repeatability}}=\mathrm{OFF}$ and a lower iteration limit, or adjusting the options governing the repulsive phase (${\mathbf{Repulsion\; Initialize}}$, ${\mathbf{Repulsion\; Finalize}}$).
6
The maximum allowed number of function evaluations (${\mathbf{Maximum\; Function\; Evaluations}}$) has been reached. As with ${\mathbf{inform}}=5$, increasing this limit if the number of iterations without improvement is small, or decreasing this limit and running the algorithm multiple times with ${\mathbf{Repeatability}}=\mathrm{OFF}$, may provide a superior result.
14: $\mathbf{fail}$ – NagError *Input/Output
The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).
e05sac will return ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_NOERROR if and only if a finalization criterion has been reached which can guarantee success. This may only happen if the option ${\mathbf{Target\; Objective\; Value}}$ has been set and reached at a point within the search domain. The finalization criterion ${\mathbf{Target\; Objective\; Value}}$ is not activated using default option settings, and must be explicitly set using e05zkc if required.
e05sac will return ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$NW_SOLUTION_NOT_GUARANTEED if no error has been detected, and a finalization criterion has been achieved which cannot guarantee success. This does not indicate that the function has failed, merely that the returned solution cannot be guaranteed to be the true global optimum.
The value of inform should be examined to determine which finalization criterion was reached.
6Error Indicators and Warnings
NE_ALLOC_FAIL
Dynamic memory allocation failed.
See Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
NE_BAD_PARAM
On entry, argument $\u27e8\mathit{\text{value}}\u27e9$ had an illegal value.
NE_BOUND
On entry, ${\mathbf{bl}}\left[i\right]={\mathbf{bu}}\left[i\right]$ for all $i$.
Constraint: ${\mathbf{bu}}\left[i\right]>{\mathbf{bl}}\left[i\right]$ for at least one $i$.
On entry, ${\mathbf{bl}}\left[\u27e8\mathit{\text{value}}\u27e9\right]=\u27e8\mathit{\text{value}}\u27e9$ and ${\mathbf{bu}}\left[\u27e8\mathit{\text{value}}\u27e9\right]=\u27e8\mathit{\text{value}}\u27e9$.
Constraint: ${\mathbf{bu}}\left[i\right]\ge {\mathbf{bl}}\left[i\right]$ for all $i$.
NE_DERIV_ERRORS
Derivative checks indicate possible errors in the supplied derivatives.
Gradient checks may be disabled by setting ${\mathbf{Verify\; Gradients}}=\mathrm{OFF}$.
NE_INT
On entry, ${\mathbf{ndim}}=\u27e8\mathit{\text{value}}\u27e9$.
Constraint: ${\mathbf{ndim}}\ge 1$.
On entry, ${\mathbf{npar}}=\u27e8\mathit{\text{value}}\u27e9$.
Constraint: ${\mathbf{npar}}\ge 5\times \mathbf{num\_threads}$, where num_threads is the value returned by the OpenMP environment variable OMP_NUM_THREADS, or num_threads is $1$ for a serial version of this function.
NE_INTERNAL_ERROR
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
See Section 7.5 in the Introduction to the NAG Library CL Interface for further information.
NE_INVALID_OPTION
Either the option arrays have not been initialized for e05sac, or they have become corrupted.
NE_NO_LICENCE
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library CL Interface for further information.
NE_USER_STOP
User requested exit $\u27e8\mathit{\text{value}}\u27e9$ during call to monmod.
User requested exit $\u27e8\mathit{\text{value}}\u27e9$ during call to objfun.
NW_FAST_SOLUTION
If the option ${\mathbf{Target\; Warning}}$ has been activated, this indicates that the ${\mathbf{Target\; Objective\; Value}}$ has been achieved to specified tolerances at a sufficiently constrained point, either during the initialization phase, or during the first two iterations of the algorithm. While this is not necessarily an error, it may occur if:
(i)The target was achieved at the first point sampled by the function. This will be the mean of the lower and upper bounds.
(ii)The target may have been achieved at a randomly generated sample point. This will always be a possibility provided that the domain under investigation contains a point with a target objective value.
(iii)If the ${\mathbf{Local\; Minimizer}}$ has been set, then a sample point may have been inside the basin of attraction of a satisfactory point. If this occurs repeatedly when the function is called, it may imply that the objective is largely unimodal, and that it may be more efficient to use the function selected as the ${\mathbf{Local\; Minimizer}}$ directly.
Assuming that objfun is correct, you may wish to set a better ${\mathbf{Target\; Objective\; Value}}$, or a stricter ${\mathbf{Target\; Objective\; Tolerance}}$.
NW_SOLUTION_NOT_GUARANTEED
A finalization criterion was reached that cannot guarantee success.
On exit, ${\mathbf{inform}}=\u27e8\mathit{\text{value}}\u27e9$.
7Accuracy
If ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_NOERROR (or ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$NW_FAST_SOLUTION) or ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$NW_SOLUTION_NOT_GUARANTEED on exit, either a ${\mathbf{Target\; Objective\; Value}}$ or finalization criterion has been reached, depending on user selected options. As with all global optimization software, the solution achieved may not be the true global optimum. Various options allow for either greater search diversity or faster convergence to a (local) optimum (See Sections 11 and 12).
Provided the objective function and constraints are sufficiently well behaved, if a local minimizer is used in conjunction with e05sac, then it is more likely that the final result will at least be in the near vicinity of a local optimum, and due to the global search characteristics of the particle swarm, this solution should be superior to many other local optima.
Caution should be used in accelerating the rate of convergence, as with faster convergence, less of the domain will remain searchable by the swarm, making it increasingly difficult for the algorithm to detect the basin of attraction of superior local optima. Using the options ${\mathbf{Repulsion\; Initialize}}$ and ${\mathbf{Repulsion\; Finalize}}$ described in Section 12 will help to overcome this, by causing the swarm to diverge away from the current optimum once no more local improvement is likely.
On successful exit with guaranteed success, ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_NOERROR. This may only happen if a ${\mathbf{Target\; Objective\; Value}}$ is assigned and is reached by the algorithm.
On successful exit without guaranteed success, ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$NW_SOLUTION_NOT_GUARANTEED is returned. This will happen if another finalization criterion is achieved without the detection of an error.
In both cases, the value of inform provides further information as to the cause of the exit.
8Parallelism and Performance
The code for e05sac is not directly threaded for parallel execution. In particular, none of the user-supplied functions will be called from within a parallel region generated by e05sac.
9Further Comments
The memory used by e05sac is relatively static throughout. As such, e05sac may be used in problems with high dimension number (${\mathbf{ndim}}>100$) without the concern of computational resource exhaustion, although the probability of successfully locating the global optimum will decrease dramatically with the increase in dimensionality.
Due to the stochastic nature of the algorithm, the result will vary over multiple runs. This is particularly true if arguments and options are chosen to accelerate convergence at the expense of the global search. However, the option ${\mathbf{Repeatability}}=\mathrm{ON}$ may be set to initialize the internal random number generator using a preset seed, which will result in identical solutions being obtained.
10Example
This example uses a particle swarm to find the global minimum of the Schwefel function:
In two dimensions the optimum is ${f}_{\mathrm{min}}=\mathrm{-837.966}$, located at $\mathbf{x}=(\mathrm{-420.97},\mathrm{-420.97})$.
The example demonstrates how to initialize and set the options arrays using e05zkc, how to query options using e05zlc, and finally how to search for the global optimum using e05sac. The function is minimized several times to demonstrate using e05sac alone, and coupled with local minimizers. This program uses the non-default option ${\mathbf{Repeatability}}=\mathrm{ON}$ to produce repeatable solutions.
an array of random numbers whose $i$th element is drawn from a uniform distribution in the range $({{\mathbf{\ell}}_{\mathrm{box}}}_{\mathit{i}},{{\mathbf{u}}_{\mathrm{box}}}_{\mathit{i}})$, for $\mathit{i}=1,2,\dots ,{\mathbf{ndim}}$
${O}_{i}$
local optimizer interior options
${O}_{e}$
local optimizer exterior options
$\mathrm{LOCMIN}(\mathbf{x},f,O)$
apply local optimizer using the set of options $O$ using the solution $(\mathbf{x},f)$ as the starting point, if used (not default)
monitor progress and possibly modify ${\mathbf{x}}_{j}$
BOUNDARY
apply required behaviour for ${\mathbf{x}}_{j}$ outside bounding box, (see ${\mathbf{Boundary}}$)
new ($\stackrel{~}{f}$)
true if $\stackrel{~}{\mathbf{x}}$, $\stackrel{~}{\mathbf{c}}$, $\stackrel{~}{f}$ were updated at this iteration
Additionally a repulsion phase can be introduced by changing from the default values of options ${\mathbf{Repulsion\; Finalize}}$ (${r}_{f}$), ${\mathbf{Repulsion\; Initialize}}$ (${r}_{i}$) and ${\mathbf{Repulsion\; Particles}}$ (${r}_{p}$). If the number of static particles is denoted ${n}_{s}$ then the following can be inserted after the new($\stackrel{~}{f}$) check in the pseudo-code above.
This section can be skipped if you wish to use the default values for all optional parameters, otherwise, the following is a list of the optional parameters available and a full description of each optional parameter is provided in Section 12.1.
For each option, we give a summary line, a description of the optional parameter and details of constraints.
The summary line contains:
the keywords;
a parameter value,
where the letters $a$, $i$ and $r$ denote options that take character, integer and real values respectively;
the default value, where the symbol $\epsilon $ is a generic notation for machine precision (see X02AJC), and $\mathit{Imax}$ represents the largest representable integer value (see X02BBC).
All options accept the value ‘DEFAULT’ in order to return single options to their default states.
Keywords and character values are case insensitive, however they must be separated by at least one space.
For e05sac the maximum length of the argument cvalue used by e05zlc is $15$.
Advance Cognitive
$r$
Default $\text{}=2.0$
The cognitive advance coefficient, ${C}_{s}$. When larger than the global advance coefficient, this will cause particles to be attracted toward their previous best positions. Setting $r=0.0$ will cause e05sac to act predominantly as a local optimizer. Setting $r>2.0$ may cause the swarm to diverge, and is generally inadvisable. At least one of the global and cognitive coefficients must be nonzero.
Advance Global
$r$
Default $\text{}=2.0$
The global advance coefficient, ${C}_{g}$. When larger than the cognitive coefficient this will encourage convergence toward the best solution yet found. Values $r\in (0,1)$ will inhibit particles overshooting the optimum. Values $r\in [1,2)$ cause particles to fly over the optimum some of the time. Larger values can prohibit convergence. Setting $r=0.0$ will remove any attraction to the current optimum, effectively generating a Monte Carlo multi-start optimization algorithm. At least one of the global and cognitive coefficients must be nonzero.
Boundary
$a$
Default $\text{}=\mathrm{FLOATING}$
Determines the behaviour if particles leave the domain described by the box bounds. This only affects the general PSO algorithm, and will not pass down to any NAG local minimizers chosen.
This option is only effective in those dimensions for which ${\mathbf{bl}}\left[i-1\right]\ne {\mathbf{bu}}\left[i-1\right]$, $i=1,2,\dots ,{\mathbf{ndim}}$.
IGNORE
The box bounds are ignored. The objective function is still evaluated at the new particle position.
RESET
The particle is re-initialized inside the domain. ${\hat{\mathbf{x}}}_{j}$ and ${\hat{f}}_{j}$ are not affected.
FLOATING
The particle position remains the same, however the objective function will not be evaluated at the next iteration. The particle will probably be advected back into the domain at the next advance due to attraction by the cognitive and global memory.
HYPERSPHERICAL
The box bounds are wrapped around an $\mathit{ndim}$-dimensional hypersphere. As such a particle leaving through a lower bound will immediately re-enter through the corresponding upper bound and vice versa. The standard distance between particles is also modified accordingly.
FIXED
The particle rests on the boundary, with the corresponding dimensional velocity set to $0.0$.
Distance Scaling
$a$
Default $\text{}=\mathrm{ON}$
Determines whether distances should be scaled by box widths.
ON
When a distance is calculated between $\mathbf{x}$ and $\mathbf{y}$, a scaled ${L}^{2}$ norm is used.
This is the distance, $\mathit{dtol}$ between particles and the global optimum which must be reached for the particle to be considered converged, i.e., that any subsequent movement of such a particle cannot significantly alter the global optimum. Once achieved the particle is reset into the box bounds to continue searching.
Constraint:
$r>0.0$.
Function Precision
$r$
Default $\text{}={\epsilon}^{0.9}$
The parameter defines ${\epsilon}_{r}$, which is intended to be a measure of the accuracy with which the problem function $F\left(\mathbf{x}\right)$ can be computed. If $r<\epsilon $ or $r\ge 1$, the default value is used.
The value of ${\epsilon}_{r}$ should reflect the relative precision of $1+\left|F\left(\mathbf{x}\right)\right|$; i.e., ${\epsilon}_{r}$ acts as a relative precision when $\left|F\right|$ is large, and as an absolute precision when $\left|F\right|$ is small. For example, if $F\left(\mathbf{x}\right)$ is typically of order $1000$ and the first six significant digits are known to be correct, an appropriate value for ${\epsilon}_{r}$ would be ${10}^{\mathrm{-6}}$. In contrast, if $F\left(\mathbf{x}\right)$ is typically of order ${10}^{\mathrm{-4}}$ and the first six significant digits are known to be correct, an appropriate value for ${\epsilon}_{r}$ would be ${10}^{\mathrm{-10}}$. The choice of ${\epsilon}_{r}$ can be quite complicated for badly scaled problems; see Chapter 8 of Gill et al. (1981) for a discussion of scaling techniques. The default value is appropriate for most simple functions that are computed with full accuracy. However when the accuracy of the computed function values is known to be significantly worse than full precision, the value of ${\epsilon}_{r}$ should be large enough so that no attempt will be made to distinguish between function values that differ by less than the error inherent in the calculation.
Local Boundary Restriction
$r$
Default $\text{}=0.5$
Contracts the box boundaries used by a box constrained local minimizer to, $[{\beta}_{l},{\beta}_{u}]$, containing the start point $x$, where
Smaller values of $r$ thereby restrict the size of the domain exposed to the local minimizer, possibly reducing the amount of work done by the local minimizer.
Constraint:
$0.0\le r\le 1.0$.
Local Interior Iterations
${i}_{1}$
Local Interior Major Iterations
${i}_{1}$
Local Exterior Iterations
${i}_{2}$
Local Exterior Major Iterations
${i}_{2}$
The maximum number of iterations or function evaluations the chosen local minimizer will perform inside (outside) the main loop if applicable. For the NAG minimizers these correspond to:
Unless set, these are functions of the parameters passed to e05sac.
Setting $i=0$ will disable the local minimizer in the corresponding algorithmic region. For example, setting ${\mathbf{Local\; Interior\; Iterations}}=0$ and ${\mathbf{Local\; Exterior\; Iterations}}=30$ will cause the algorithm to perform no local minimizations inside the main loop of the algorithm, and a local minimization with upto $30$ iterations after the main loop has been exited.
Constraint:
${i}_{1}\ge 0$, ${i}_{2}\ge 0$.
Local Interior Tolerance
${r}_{1}$
Default $\text{}={10}^{\mathrm{-4}}$
Local Exterior Tolerance
${r}_{2}$
Default $\text{}={10}^{\mathrm{-4}}$
This is the tolerance provided to a local minimizer in the interior (exterior) of the main loop of the algorithm.
Constraint:
${r}_{1}>0.0$,${r}_{2}>0.0$.
Local Interior Minor Iterations
${i}_{1}$
Local Exterior Minor Iterations
${i}_{2}$
Where applicable, the secondary number of iterations the chosen local minimizer will use inside (outside) the main loop. Currently the relevant default values are:
Accurate derivatives must be provided, and will not be approximated internally. Additionally, each call to objfun during a local minimization will require either the objective to be evaluated alone, or both the objective and its gradient to be evaluated. Hence on a call to objfun, ${\mathbf{mode}}=5$ or $7$.
${\mathbf{Local\; Minimizer}}=\mathrm{e04ucc}$
Use e04ucc as the local minimizer.
This operates such that any derivatives of the objective function that you cannot supply, will be approximated internally using finite differences.
Either, the objective, objective gradient, or both may be requested during a local minimization, and as such on a call to objfun, ${\mathbf{mode}}=1$, $2$ or $5$.
The box bounds forwarded to this function from e05sac will have been acted upon by ${\mathbf{Local\; Boundary\; Restriction}}$. As such, the domain exposed may be greatly smaller than that provided to e05sac.
Maximum Function Evaluations
$i$
Default $=\mathit{Imax}$
The maximum number of evaluations of the objective function. When reached this will return ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$NW_SOLUTION_NOT_GUARANTEED and ${\mathbf{inform}}=6$.
Constraint:
$i>0$.
Maximum Iterations Completed
$i$
Default $\text{}=1000\times {\mathbf{ndim}}$
The maximum number of complete iterations that may be performed. Once exceeded e05sac will exit with ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$NW_SOLUTION_NOT_GUARANTEED and ${\mathbf{inform}}=5$.
Unless set, this adapts to the parameters passed to e05sac.
Constraint:
$i\ge 1$.
Maximum Iterations Static
$i$
Default $\text{}=100$
The maximum number of iterations without any improvement to the current global optimum. If exceeded e05sac will exit with ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$NW_SOLUTION_NOT_GUARANTEED and ${\mathbf{inform}}=4$. This exit will be hindered by setting ${\mathbf{Maximum\; Iterations\; Static\; Particles}}$ to larger values.
Constraint:
$i\ge 1$.
Maximum Iterations Static Particles
$i$
Default $\text{}=0$
The minimum number of particles that must have converged to the current optimum before the function may exit due to ${\mathbf{Maximum\; Iterations\; Static}}$ with ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$NW_SOLUTION_NOT_GUARANTEED and ${\mathbf{inform}}=4$.
Constraint:
$i\ge 0$.
Maximum Particles Converged
$i$
Default $=\mathit{Imax}$
The maximum number of particles that may converge to the current optimum. When achieved, e05sac will exit with ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$NW_SOLUTION_NOT_GUARANTEED and ${\mathbf{inform}}=3$. This exit will be hindered by setting ‘Repulsion’ options, as these cause the swarm to re-expand.
Constraint:
$i>0$.
Maximum Particles Reset
$i$
Default $=\mathit{Imax}$
The maximum number of particles that may be reset after converging to the current optimum. Once achieved no further particles will be reset, and any particles within ${\mathbf{Distance\; Tolerance}}$ of the global optimum will continue to evolve as normal.
Constraint:
$i>0$.
Maximum Variable Velocity
$r$
Default $\text{}=0.25$
Along any dimension $j$, the absolute velocity is bounded above by $\left|{\mathbf{v}}_{j}\right|\le r\times ({\mathbf{u}}_{j}-{\mathbf{\ell}}_{j})={\mathbf{V}}_{\mathrm{max}}$. Very low values will greatly increase convergence time. There is no upper limit, although larger values will allow more particles to be advected out of the box bounds, and values greater than $4.0$ may cause significant and potentially unrecoverable swarm divergence.
Constraint:
$r>0.0$.
Optimize
$a$
Default $\text{}=\mathrm{MINIMIZE}$
Determines whether to maximize or minimize the objective function.
MINIMIZE
The objective function will be minimized.
MAXIMIZE
The objective function will be maximized. This is accomplished by minimizing the negative of the objective.
Repeatability
$a$
Default $\text{}=\mathrm{OFF}$
Allows for the same random number generator seed to be used for every call to e05sac. ${\mathbf{Repeatability}}=\mathrm{OFF}$ is recommended in general.
OFF
The internal generation of random numbers will be nonrepeatable.
ON
The same seed will be used.
Repulsion Finalize
$i$
Default $=\mathit{Imax}$
The number of iterations performed in a repulsive phase before re-contraction. This allows a re-diversified swarm to contract back toward the current optimum, allowing for a finer search of the near optimum space.
Constraint:
$i\ge 2$.
Repulsion Initialize
$i$
Default $=\mathit{Imax}$
The number of iterations without any improvement to the global optimum before the algorithm begins a repulsive phase. This phase allows the particle swarm to re-expand away from the current optimum, allowing more of the domain to be investigated. The repulsive phase is automatically ended if a superior optimum is found.
Constraint:
$i\ge 2$.
Repulsion Particles
$i$
Default $\text{}=0$
The number of particles required to have converged to the current optimum before any repulsive phase may be initialized. This will prevent repulsion before a satisfactory search of the near optimum area has been performed, which may happen for large dimensional problems.
Constraint:
$i\ge 0$.
Seed
$i$
Default $\text{}=0$
Sets the random number generator seed to be used when ${\mathbf{Repeatability}}=\mathrm{ON}$. If set to 0, the default seed will be used. If not, the absolute value of ${\mathbf{Seed}}$ will be used to generate the random number generator seed.
Swarm Standard Deviation
$r$
Default $\text{}=0.1$
The target standard deviation of the particle distances from the current optimum. Once the standard deviation is below this level, e05sac will exit with ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$NW_SOLUTION_NOT_GUARANTEED and ${\mathbf{inform}}=2$. This criterion will be penalized by the use of ‘Repulsion’ options, as these cause the swarm to re-expand, increasing the standard deviation of the particle distances from the best point.
Constraint:
$r\ge 0.0$.
Target Objective
$a$
Default $\text{}=\mathrm{OFF}$
Target Objective Value
$r$
Default $\text{}=0.0$
Activate or deactivate the use of a target value as a finalization criterion. If active, then once the supplied target value for the objective function is found (beyond the first iteration if ${\mathbf{Target\; Warning}}$ is active) e05sac will exit with ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_NOERROR and ${\mathbf{inform}}=1$. Other than checking for feasibility only (${\mathbf{Optimize}}=\mathrm{CONSTRAINTS}$), this is the only finalization criterion that guarantees that the algorithm has been successful. If the target value was achieved at the initialization phase or first iteration and ${\mathbf{Target\; Warning}}$ is active, e05sac will exit with ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$NW_FAST_SOLUTION. This option may take any real value $r$, or the character ON/OFF as well as DEFAULT. If this option is queried using e05zlc, the current value of $r$ will be returned in rvalue, and cvalue will indicate whether this option is ON or OFF. The behaviour of the option is as follows:
$r$
Once a point is found with an objective value within the ${\mathbf{Target\; Objective\; Tolerance}}$ of $r$, e05sac will exit successfully with ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_NOERROR and ${\mathbf{inform}}=1$.
OFF
The current value of $r$ will remain stored, however it will not be used as a finalization criterion.
ON
The current value of $r$ stored will be used as a finalization criterion.
DEFAULT
The stored value of $r$ will be reset to its default value ($0.0$), and this finalization criterion will be deactivated.
Target Objective Safeguard
$r$
Default $\text{}=100.0\epsilon $
If you have given a target objective value to reach in $\mathit{objval}$ (the value of the optional parameter ${\mathbf{Target\; Objective\; Value}}$), $\mathit{objsfg}$ sets your desired safeguarded termination tolerance, for when $\mathit{objval}$ is close to zero.
Constraint:
$\mathit{objsfg}\ge 2\epsilon $.
Target Objective Tolerance
$r$
Default $\text{}=0.0$
The optional tolerance to a user-specified target value.
Constraint:
$r\ge 0.0$.
Target Warning
$a$
Default $\text{}=\mathrm{OFF}$
Activates or deactivates the error exit associated with the target value being achieved before entry into the main loop of the algorithm, ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$NW_FAST_SOLUTION.
OFF
No error will be returned, and the function will exit normally.
ON
An error will be returned if the target objective is reached prematurely, and the function will exit with ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$NW_FAST_SOLUTION.
Verify Gradients
$a$
Default $\text{}=\mathrm{ON}$
Adjusts the level of gradient checking performed when gradients are required. Gradient checks are only performed on the first call to the chosen local minimizer if it requires gradients. There is no guarantee that the gradient check will be correct, as the finite differences used in the gradient check are themselves subject to inaccuracies.
OFF
No gradient checking will be performed.
ON
A cheap gradient check will be performed on both the gradients corresponding to the objective through objfun.
OBJECTIVE FULL
A more expensive gradient check will be performed on the gradients corresponding to the objective objfun.
Weight Decrease
$a$
Default $\text{}=\mathrm{INTEREST}$
Determines how particle weights decrease.
OFF
Weights do not decrease.
INTEREST
Weights decrease through compound interest as ${w}_{\mathit{IT}+1}={w}_{\mathit{IT}}(1-{W}_{\mathit{val}})$, where ${W}_{\mathit{val}}$ is the ${\mathbf{Weight\; Value}}$ and $\mathit{IT}$ is the current number of iterations.
LINEAR
Weights decrease linearly following ${w}_{\mathit{IT}+1}={w}_{\mathit{IT}}-\mathit{IT}\times ({W}_{\mathit{max}}-{W}_{\mathit{min}})/{\mathit{IT}}_{\mathit{max}}$, where $\mathit{IT}$ is the iteration number and ${\mathit{IT}}_{\mathit{max}}$ is the maximum number of iterations as set by ${\mathbf{Maximum\; Iterations\; Completed}}$.
Weight Initial
$r$
Default $\text{}={W}_{\mathit{max}}$
The initial value of any particle's inertial weight, ${W}_{\mathit{ini}}$, or the minimum possible initial value if initial weights are randomized. When set, this will override ${\mathbf{Weight\; Initialize}}=\mathrm{RANDOMIZED}$ or $\mathrm{MAXIMUM}$, and as such these must be set afterwards if so desired.
Determines how the initial weights are distributed.
INITIAL
All weights are initialized at the initial weight, ${W}_{\mathit{ini}}$, if set. If ${\mathbf{Weight\; Initial}}$ has not been set, this will be the maximum weight, ${W}_{\mathit{max}}$.
MAXIMUM
All weights are initialized at the maximum weight, ${W}_{\mathit{max}}$.
RANDOMIZED
Weights are uniformly distributed in $({W}_{\mathit{min}},{W}_{\mathit{max}})$ or $({W}_{\mathit{ini}},{W}_{\mathit{max}})$ if ${\mathbf{Weight\; Initial}}$ has been set.
Weight Maximum
$r$
Default $\text{}=1.0$
The maximum particle weight, ${W}_{\mathit{max}}$.
Constraint:
$1.0\ge r\ge {W}_{\mathit{min}}$ (If ${W}_{\mathit{ini}}$ has been set then $1.0\ge r\ge {W}_{\mathit{ini}}$.)
Weight Minimum
$r$
Default $\text{}=0.1$
The minimum achievable weight of any particle, ${W}_{\mathit{min}}$. Once achieved, no further weight reduction is possible.
Constraint:
$0.0\le r\le {W}_{\mathit{max}}$ (If ${W}_{\mathit{ini}}$ has been set then $0.0\le r\le {W}_{\mathit{ini}}$.)
Weight Reset
$a$
Default $\text{}=\mathrm{MAXIMUM}$
Determines how particle weights are re-initialized.
INITIAL
Weights are re-initialized at the initial weight if set. If ${\mathbf{Weight\; Initial}}$ has not been set, this will be the maximum weight.
MAXIMUM
Weights are re-initialized at the maximum weight.
RANDOMIZED
Weights are uniformly distributed in $({W}_{\mathit{min}},{W}_{\mathit{max}})$ or $({W}_{\mathit{ini}},{W}_{\mathit{max}})$ if ${\mathbf{Weight\; Initial}}$ has been set.
Weight Value
$r$
Default $\text{}=0.01$
The constant ${W}_{\mathit{val}}$ used with ${\mathbf{Weight\; Decrease}}=\mathrm{INTEREST}$.