Whereas routines in the NAG E04 Chapter seek to find a local optimum, the E05 Chapter contains routines which attempt to find the best of these local optima, the global minimum. Such problems are in general very difficult, especially if, as is often the case, the optimization is accompanied by nonlinear constraints on the solution.

Algorithms have been proposed to address such problems, many of which cater for functions which are not known to a high degree of accuracy or which are non-smooth. Such algorithms typically take very many function evaluations and hence are liable to take a long time to run.

When the functions are smooth a very practical means of addressing the global optimization problem is to use a local optimization routine but start it from many different points. If the best of the resulting solutions is returned, then we might be willing to accept this as a global solution. Of course there is no guarantee that a global minimum has been found, but increased confidence might be gained by using more starting points or by running the program again with different starting points.

Frequently this technique will prove to be faster and as reliable as other methods. We offer a multi-start routine, e05ucc. This routine uses a sequential QP algorithm for finding the local minimum of a general nonlinear function subject to linear, nonlinear and simple bound constraints. The user has the option to return not just the best solution, but any specified number of solutions, ordered to reflect the value of the objective at the minimum. Such a facility might be useful if the user has other criteria, not specified in the mathematical solution, that the user would like in an acceptable solution. An example might be a solution that is 'good', but stable in the sense that small changes in the variables does not cause a large change in the objective. So, for example, small errors in manufacturing a part might not diminish performance of the assembled product.

Our NAG Library and NAG Toolbox for MATLAB® contains the general multi-start algorithm described above and a multi-start algorithm, e05us, based upon a nonlinearly constrained, nonlinear sum of squares problem. This too has the option to return the best n solutions, where n may be greater than 1. Typically non-linearly constrained sum of squares problems occur when fitting models to observed data.