# An Adaptive Procedure for the Global Minimization of a Class of Polynomial Functions
## 3 A Multistart Algorithm  
Multistart algorithms are widely used heuristics for solving Problem (1) [2; 3]. Over the years, many variants and generalizations have been produced. We consider here its basic form which consists of the following steps:  
* start with a fixed number \(q\) of independent initial points \(\mathbf{x}_{0}^{(r)}\), \(r=1,\ldots,q\), randomly generated.
* For \(r=1,\ldots,q\), a local optimizer, say \(\mathcal{L}\), is applied to \(\mathbf{x}_{0}^{(r)}\) to find an approximation of a local minimum. We assume \(\mathcal{L}\) to be an iterative procedure which, in the constrained case, takes on the nonnegativity of \(\mathbf{x}\) and denote by \(\mathbf{x}_{v}^{(r)}\), \(v=1,2,\ldots\), the sequence of points computed until a suitable stopping condition is satisfied. The corresponding function values \(f(\mathbf{x}_{v}^{(r)})\) estimate the quality of the approximation. Both the chosen procedure \(\mathcal{L}\) and the stopping condition employed by \(\mathcal{L}\) are of crucial importance. Ideally, the stopping condition should verify whether the local minimum has been reached within a given tolerance \(\epsilon\), but of course more practical tests must be used.
* When all the \(q\) points \(\mathbf{x}_{0}^{(r)}\) have been processed, the point \(\mathbf{x}_{v}^{(r)}\) with the smallest function value \(f(\mathbf{x}_{v}^{(r)})\) is selected as an approximation of the global minimum. It is evident that the minimum found in this way is not guaranteed to suitably approximate the global minimum, even if a large number of starting points is considered.  
In the experimentation we have implemented a version of the basic Multistart algorithm, here denoted by MS, as reference. The chosen local optimizer \(\mathcal{L}\) is particularly suitable for the problems we are considering and exploits the differentiability of the function \(f(\mathbf{x})\). Its execution time turns out to be much smaller than what is generally expected from a library method, which relies on general purpose procedures as local optimizers and does not exploit the differentiability information. The stopping condition we have implemented monitors the flatness of the approximation by assuming \(\mathbf{x}_{v}^{(r)}\) as an acceptable approximation of a local minimum when  
\[(\max g-\min g)/\text{mean}\ g\leq\epsilon,\ \text{where}\ g=\big{[}\,f(\mathbf{x}_{v- 2}^{(r)}),f(\mathbf{x}_{v-1}^{(r)}),f(\mathbf{x}_{v}^{(r)})\,\big{]}. \tag{4}\]  
Of course, if an index \(v\) exists such that \(f(\mathbf{x}_{v}^{(r)})=0\), the algorithm stops and condition (4) is not tested. The tolerance \(\epsilon\) is set equal to some power of the machine \(eps\). As usual, a maximum number \(d_{\max}\) of allowed iterations is imposed to each run.  
As an example, we have applied MS to one of the problems described in Section 5.3, namely problem \(10\times 5\times 15\) (\(5\), \(3\)), generating \(q=5\) initial points. Figure 1a shows the log plot of the histories \(f(\mathbf{x}_{v}^{(r)})\), \(v=1,2,\ldots\), computed by MS for \(r=1,\ldots,q\) using the stopping condition (4) with \(\epsilon=10^{-12}\). All the sequences converge to the same local minimum, but one (plotted with black solid line) requires \(300\) iterations and appears to be faster than the others which require from \(400\) to \(500\) iterations. The number of iterations of the overall execution is \(2100\).  
Letting the local algorithm run until convergence for all the starting points is a time-consuming procedure, in particular when the iterates obtained from many different starting points lead to the same local minimum. A reasonable approach, that we presently propose, modifies this procedure adaptively. It is based on an efficient premature recognition of the more promising runs of the local algorithm and interrupts with high probability the runs which may lead to already found local minima or to local minima of larger value than those already found.