# An Adaptive Procedure for the Global Minimization of a Class of Polynomial Functions
## 4 An Adaptive Procedure
The length of the queue, i.e., the number of items in \(\mathcal{Q}\), is found by calling the function Length. At the beginning the length is \(q\) and it is modified by the functions:  
* \(Y=\texttt{Dequeue}(\mathcal{Q})\) returns the item \(Y\) which has the smallest priority and deletes it from \(\mathcal{Q}\),
* \(\texttt{Enqueue}(\mathcal{Q},Y)\) inserts the item \(Y\) into \(\mathcal{Q}\). A further function \(\texttt{Maxdelta}(\mathcal{Q})\) returns the largest value among the quantities \(\delta\) of all the items in \(\mathcal{Q}\). During the computation the following quantities deriving from \(g=g_{(Y)}\), \(h=h_{(Y)}\) and \(\delta=\delta_{(Y)}\) are referred (their expressions have been tested by an ad hoc experimentation):  
* \(\vartheta=(\max g-\min g)/\text{mean}\,g\) measures the flatness of the last computed values of \(f\) according to (4),
* \(\varphi=\delta/\text{mean}\,g\) measures the decreasing rate of \(f\). If \(\varphi<0\) the last computed iteration increases over the preceding one. Only small increases, corresponding to limited oscillations, are tolerated,
* \(c=(1-2^{-\xi/\lambda})^{2}+0.5\,(f(x)-g_{\min})/f(x)\) measures the discarding level. The larger \(c\), the higher the probability of discarding the item. Among items which have comparable values \(f(x)\), the older one has greater probability to be discarded. Three other functions are needed:  
* \(\texttt{Random}\,(n)\) generates \(n\) numbers uniformly distributed over \([0,1]\). * The local minimization algorithm \(\mathcal{L}\) is applied for the predefined number \(\lambda\) of iterations (in the experiments we assume \(\lambda=10\)) and returns \(x\), \(g\), the minimum \(\widehat{g}\) of the function values of the current segment, its corresponding point \(\widehat{x}\), the number \(\upsilon\) of performed iterations and the decreasing rate \(\delta\). Since algorithm AD is based on the splitting into segments of the run corresponding to a single starting point, the local optimizer \(\mathcal{L}\) needs to be stationary, in order to get a computation which gives the same numerical values as if a single run had been performed without segmentation. * The following Boolean function Control verifies whether an item is promising (i.e., must be further processed) or not. For notes (a)-(e) see the text. ```
functionControl(\(Y\)); the selected item \(Y\) is enqueued again if True is returned, otherwise it is discarded. \(g=g_{(Y)}\); \(h=h_{(Y)}\); \(\delta=\delta_{(Y)}\); compute \(\vartheta\), \(\varphi\) and \(c\); if\(\varphi<-0.6\)thenreturnFalse; (a) if\(\vartheta<\epsilon\),thenreturnFalse; (b) ifLength\((\mathcal{Q})>2\) and \(\delta\geq\texttt{Maxdelta}(\mathcal{Q})\)thenreturnTrue; (c) if\(r_{(Y)}=r_{\min}\),thenreturnTrue; (d) ifRandom\((1)<c\)thenreturnFalse; (e) returnTrue;
```  
The decision on which course to choose depends mainly on the flatness, but other conditions are also taken into consideration as described in the following notes:1. large oscillations are not allowed,
2. the flatness level has been reached,
3. the selected item decreases more quickly than other items in the queue,
4. the selected item has the same index \(r\) of the item where \(g_{\min}\) has been found,
5. if none of the preceding conditions holds, the selected item is discarded with probability given by its discarding level. After the initialization of the queue, the adaptive process AD evolves as follows: an item \(Y\) is extracted from the queue according to its priority \(\chi_{(Y)}\). When enough iterations (\(6\lambda\) iterations in the experiments) have been performed for stabilizing the initial situation, the function Control is applied, and if \(Y\) is recognized promising, the function \(\mathcal{L}\) is applied to point \(\mathbf{x}_{(Y)}\). A new item is so built and inserted back into \(\mathcal{Q}\). If the computed \(f(\widehat{\mathbf{x}})\) is smaller than \(g_{\min}\), then \(g_{\min}\), \(x_{\min}\) and \(r_{\min}\) are updated.