# An Adaptive Procedure for the Global Minimization of a Class of Polynomial Functions
## 4 An Adaptive Procedure  
Because of the large computational cost of the strategy described in the previous section, the straightforward implementation can be profitably applied only to small problems. For this reason we propose here a heuristic approach, which we denote by the name AD, suitable for large problems whose basic step consists in the splitting of the runs in segments of a fixed length \(\lambda\). Each segment, identified by the index \(r\), \(r=1,\ldots,q\), stores the partial solution produced at the end of the \(\lambda\) iterations, which will be used as the starting point for the next run with the same index \(r\). The processing order of the various segments is modified by interlacing the computation of segments with different indices \(r\). This strategy requires segments corresponding to different \(r\)'s to be available at any moment of the computation. The segments, which appear to be the more promising ones depending on the behavior of the computed function values, are carried on and the other segments are discarded. The strategy is accomplished using a priority queue \(\mathcal{Q}\) whose items have the form  
\[Y=\{r,h,\boldsymbol{x},\boldsymbol{g},\delta,\chi\},\quad r=1,\ldots,q,\]  
where  
* \(r\in\{1,\ldots,q\}\) is the index of the segment; it identifies the seed chosen for the random generation of the initial point following a uniform distribution between \(0\) and \(1\). * \(h=h^{(r)}\) is the number of iterations computed until now by \(\mathcal{L}\) in all the segments with the same index \(r\), i.e., starting with \(\boldsymbol{x}_{0}^{(r)}\). * \(\boldsymbol{x}=\boldsymbol{x}_{h}^{(r)}\) is the partial solution computed by \(\mathcal{L}\) at the end of the current \(r\)th segment. * \(\boldsymbol{g}=\left[\,f(\boldsymbol{x}_{h-2}^{(r)}),f(\boldsymbol{x}_{h-1}^ {(r)}),f(\boldsymbol{x}_{h}^{(r)})\,\right]\) is the array containing the function values of the last three points computed by \(\mathcal{L}\) in the current \(r\)th segment. * \(\delta=f(\boldsymbol{x}_{h-1}^{(r)})-f(\boldsymbol{x}_{h}^{(r)})\) is an estimate of the decreasing rate of the function. * \(\chi=\chi^{(r)}\) is the priority of the item, which rules the processing order of the various segments according to the minimum policy. The belonging of an element to an item \(Y\) is denoted by using the subscript \((Y)\), for example \(r_{(Y)}\) denotes the index of item \(Y\). During the computation three global quantities, \(g_{\min}\), \(\boldsymbol{x}_{\min}\), and \(r_{\min}\), play an important role:  
* \(g_{\min}\) is the minimum of all the function values computed so far relative to all the items already processed
* \(\boldsymbol{x}_{\min}\) is the computed point corresponding to \(g_{\min}\) and \(r_{\min}\) is the index of the item where \(g_{\min}\) has been found. The priority is defined by \(\chi=\gamma+\xi\), where \(\gamma=\log_{10}(f(\boldsymbol{x})/g_{\min})\) measures the accuracy of the last computed iterate in the current segment and \(\xi=h/\lambda\) measures the age of the computation of the \(r\)th seed. Between two items which have the same age, this expression favors the one with the better accuracy and, between two items which have comparable accuracies, it favors the younger one, that is  
Figure 1: (a) History plots of MS; (b) History plots of AD. the quicker one. The inclusion of the age into the priority is important to avoid that only the best item is processed and all the other items are ignored. In fact, with the increase of the age, also items which had been left behind take their turn. At the beginning the initial points \(x_{0}^{(r)}\), \(r=1,\ldots,q\), are randomly generated and \(g_{\min}=\min_{r=1,\ldots,q}f(x_{0}^{(r)})\) is set. The initial priorities are defined by \(\chi^{(r)}=\log_{10}(f(x_{0}^{(r)})/g_{\min})\) and the queue is formed by the \(q\) items  
\[\{r,h,x_{0}^{(r)},g,\delta,\chi^{(r)}\},\quad\text{for}\quad r=1,\ldots,q, \tag{5}\]  
where \(h=\delta=0\) and \(g\) is a void array.