# An Adaptive Procedure for the Global Minimization of a Class of Polynomial Functions
## 5 Experimentation
### The Symmetric NMF  
In some applications, matrix \(M\in\mathbb{R}_{+}^{n\times n}\) is symmetric, then the objective function to be minimized becomes \(f(W)=\|M-W\,W^{T}\|_{F}^{2}\), under the constrain \(W\geq O\). This problem is known as symmetric NMF (SymNMF). As suggested in [12], the solution \(W\in\mathbb{R}_{+}^{n\times k}\) can be found through a nonsymmetric penalty problem of the form  
\[\min_{W,\,H\geq O}f_{\alpha}(W,H),\text{ with }f_{\alpha}(W,H)=\|M-WH^{T}\|_{F}^ {2}+\alpha\|W-H\|_{F}^{2},\]  
\(\alpha\) being a positive parameter which acts on the violation of the symmetry. Hence, applying ANLS, we solve alternatively the two subproblems  
\[H_{v}=\underset{H\geq 0}{\text{argmin}}\ \left\|\left[\begin{array}{c}M\\ \sqrt{\alpha_{v}}\ W_{v-1}^{T}\end{array}\right]-\left[\begin{array}{c}W_{v -1}\\ \sqrt{\alpha_{v}}\ I_{k}\end{array}\right]\ H^{T}\right\|_{F}^{2},\]  
\[W_{v}=\underset{W\geq 0}{\text{argmin}}\ \left\|\left[\begin{array}{c}M\\ \sqrt{\alpha_{v}}\ H_{v}^{T}\end{array}\right]-\left[\begin{array}{c}H_{v }\\ \sqrt{\alpha_{v}}\ I_{k}\end{array}\right]\ W^{T}\right\|_{F}^{2}.\]  
In [12], the sequence of penalizing parameters is constructed by setting  
\[\alpha_{v}=\beta_{v}\ \text{max}\ M,\quad\text{with}\quad\beta_{0}=1\]  
and \(\beta_{v}\) is modified according to a geometric progression of the form \(\beta_{v}=\zeta^{v}\) with the fixed ratio \(\zeta=1.01\). We suggest instead to let \(\beta_{v}\) be modified adaptively, as shown in [13].  
Symmetric NMF problems arise naturally in clustering. Given \(n\) points \(\mathbf{p}_{i}\) in an Euclidean space and the number \(k\) of the required clusters, the clustering structure is captured by a symmetric matrix \(M\), called _similarity_ matrix, whose elements \(m_{i,j}\) represent the similarity between \(\mathbf{p}_{i}\) and \(\mathbf{p}_{j}\). These similarity values are computed through the Gaussian kernel  
\[e_{i,j}=\exp\Big{(}-\ \frac{\|\mathbf{p}_{i}-\mathbf{p}_{j}\|_{2}^{2}}{\sigma^{2}} \Big{)}\,,\quad\text{for}\quad i\
eq j,\quad\text{and}\quad e_{i,i}=0, \tag{7}\]  
where \(\sigma\) is a suitable scaling parameter, followed by the normalized cut  
\[m_{i,j}=d_{i}^{-1/2}e_{i,j}d_{j}^{-1/2}\ \text{where}\quad d_{i}=\sum_{r=1}^{n}e_{ i,r},\quad\text{for}\quad i=1,\ldots,n.\]  
The experimentation deals with two sets \(C_{1}\) and \(C_{2}\) of \(n\) points randomly generated in \(\mathbb{R}^{2}\) (see Figure 2 for \(n=50\)).  
Set \(C_{1}\) is generated with \(n=10,\ 50,\ 100\) and set \(C_{2}\) is generated with \(n=50,\ 100,\ 200\). The number of the required clusters is fixed to \(k=5\) for all the cases. The dimension of the solution space is \(N=2 nk\). The results are shown in Table 2. On these problems, Class 2 methods outperform Class 1 methods in both the computational time and the accuracy. Moreover, by comparing the measures _lerr_ in column AD1 with those in column MS1 and the measures _lerr_ in column AD2 with those in column MS2, we see that, for each value of the tolerance \(\epsilon\), the adaptive method and the corresponding non adaptive one share the same accuracy.