# An Adaptive Procedure for the Global Minimization of a Class of Polynomial Functions
## 5 Experimentation
### Summary of the Results  
First, we analyze the effect of the chosen tolerance on Class 2 methods. The experiments confirm the expectation that stronger tolerance requests, which pay in terms of larger execution time, in general lead to more accurate results. The comparison of the performances of Class 1 and Class 2 methods shows that the accuracy of MS2 and AD2 does not appear to suffer too much with respect to the accuracy of Class 1 methods, in spite of the fact that they enjoy a much smaller execution time. In order to summarize the results of the experimentation, we plot in Figure 3 the average of all the values of _lerr_, taken as a measure of the methods accuracy on all the problems, versus the averaged _time_. The larger the ordinate value, the more accurate the method. \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline _Problem (\(\rho\))_ & \(N\) & **Indices** & NM & DE & SA & MS1 & MS2 & AD1 & AD2 \\ \hline \multirow{3}{*}{_TF3_(16)} & \multirow{3}{*}{384} & \(time\) & 1015 & 1102 & 1138 & 1920 & 1917 & 393 & 5770 \\  & & _lerr_ & 3.5 & 3.4 & 3.0 & 7.6 & 7.6 & 8.0 & 12.0 \\ \hline \multirow{3}{*}{_TF3_(17)} & \multirow{3}{*}{408} & \(time\) & 457 & 370 & 1161 & 1097 & 1104 & 37 & 53 \\  & & _lerr_ & 8.5 & 8.7 & 6.5 & + & + & 8.2 & + \\ \hline \multirow{3}{*}{_TF3_(18)} & \multirow{3}{*}{432} & \(time\) & 1070 & 816 & 432 & 146 & 167 & 35 & 35 \\  & & _lerr_ & 7.6 & 8.1 & 9.6 & + & + & + & + \\ \hline \multirow{3}{*}{_FF3_(24)} & \multirow{3}{*}{648} & \(time\) & 3485 & 3501 & 3724 & 3640 & 4086 & 255 & 257 \\  & & _lerr_ & 3.8 & 3.3 & 4.0 & + & + & 13.1 & 13.1 \\ \hline \multirow{3}{*}{_FF3_(25)} & \multirow{3}{*}{675} & \(time\) & 643 & 2263 & 3145 & 2503 & 2783 & 217 & 219 \\  & & _lerr_ & \(-\) & 7.8 & 6.9 & + & + & + & + \\ \hline \multirow{3}{*}{_FF3_(26)} & \multirow{3}{*}{702} & \(time\) & 2633 & 2320 & 2639 & 1689 & 2880 & 146 & 197 \\  & & _lerr_ & 7.8 & 8.1 & 8.2 & + & + & 8.7 & + \\ \hline \multirow{3}{*}{_FF3_(27)} & \multirow{3}{*}{729} & \(time\) & 1356 & 1138 & 2502 & 1016 & 1523 & 210 & 210 \\  & & _lerr_ & 9.6 & 9.6 & 8.3 & + & + & + & + \\ \hline \end{tabular}
\end{table} 
Table 4: Execution times and accuracies for the tensor factorization associated to matrix product complexity. Figure 3: Average _lerr_ (taken as a measure of accuracy) versus _time_. From the figure we see that, on average, the adaptive procedure AD2 not only is faster, but also gives comparable accuracy with MS2. This is due to the fact that the computational effort of AD2 is focused where it is more useful and is not wasted. To study how _time_ depends on \(N\), we need data corresponding to large values of \(N\). A problem for which it is possible to obtain these data is the symmetric NMF applied to clustering. In fact, in this case it is easy to construct problems of the same type with increasing dimensions. Figure 4 gives an idea of the time performance of the methods when they are applied to the cluster problem \(C_{2}\). Class 2 methods have been run with increasing dimensions until \(n=2000\), corresponding to size \(N=20\),000. The execution times of AD2 (dashed line) and MS2 (solid line) are plotted together with the times of NM (solid line), chosen as the representative of Class 1 for \(N\leq 2000\) (larger dimensions for Class 1 methods could not be considered). For the lower dimensions, the use of the adaptive method does not give advantages, because of the initialization overhead (due to the \(6\lambda\) iterations performed for stabilization before starting the adaptive strategy). This is shown by the overlap of the plots of AD2 and MS2 in the initial tract. The lines which appear in the log-log plot suggest that the asymptotical behavior of the computational cost for increasing \(N\) is of the form \(\alpha\)\(N^{\beta}\). Very similar values of \(\beta\) suggest that the costs of MS2 and NM have roughly the same order, while the cost of AD2 has a lower order.