# An Adaptive Procedure for the Global Minimization of a Class of Polynomial Functions
## 2 The Problem  
A widely studied problem in literature is the one of nonlinear global minimization  
\[\min_{\mathbf{x}\in D}f(\mathbf{x}), \tag{1}\]  
where \(D\subseteq\mathbb{R}^{N}\) is a region determined by a set of constraints and \(f:D\rightarrow\mathbb{R}_{+}\) is a polynomial function of degree \(d\geq 2\) which models the problem's objective. Classical examples are \(D=\mathbb{R}_{+}^{N}\) of nonnegativity constraints, and \(D=\mathbb{R}^{N}\) when no constraint is given. Problem (1) is NP-hard [5]. In this paper we consider specifically objective functions expressed through the Frobenius norm of an array \(\mathcal{A}\) whose elements are low degree polynomials in the entries of \(\mathbf{x}\):  
\[f(\mathbf{x})=\|\mathcal{A}(\mathbf{x})\|_{F}^{2}. \tag{2}\]  
We examine in particular the cases where \(\mathcal{A}(\mathbf{x})\) is a two-dimensional or a three-dimensional matrix. For example, in the two dimensional case, a problem considered in the experimentation looks for two low-rank matrices \(W\in\mathbb{R}_{+}^{m\times k}\) and \(H\in\mathbb{R}_{+}^{n\times k}\) such that \(M\approx WH^{T}\) according to  
\[\min_{W,\,H\geq O}f(W,H),\text{ where }f(W,H)=\|M-W\,H^{T}\|_{F}^{2}, \tag{3}\]  
given a nonnegative matrix \(M\in\mathbb{R}_{+}^{m\times n}\) and an integer \(k<n\). Problem (3), known as Nonnegative Matrix Factorization (NMF), was first proposed in [6] for data analysis and from then on has received much attention. It is a particular case of Problem (1) with \(f(\mathbf{x})\) as in (2), \(N=(m+n)k\), \(D=\mathbb{R}_{+}^{N}\) and \(\mathbf{x}\) a vectorization of the pair \((W,H)\). In a columnwise vectorization, \(\mathcal{A}(\mathbf{x})\) is the matrix of elements  
\[a_{i,j}(\mathbf{x})=m_{i,j}-\sum_{r=1}^{k}w_{i,r}h_{j,r}=m_{i,j}-\sum_{r=1}^{k}x_ {(r-1)m+i}x_{mk+(r-1)n+j}.\]  
Since \(f\) is a polynomial, the gradient \(\
abla f\) and the Hessian \(\
abla^{2}f\) of \(f\) are available. From a theoretical point of view, a simple way to solve Problem (1) in the unconstrained case would be to look for the stationary points \(\mathbf{x}\) where \(\
abla f(\mathbf{x})=0\) and choose whichever \(\mathbf{x}\) minimizes \(f\), but this way does not appear to be practical when \(N\) is large, even if \(d\) is not too large, because finding a global minimum can be a very difficult task when \(f\) has many local minima. For this reason, numerical methods have been proposed which do not try to solve \(\
abla f(\mathbf{x})=0\). Anyway, many numerical methods take advantage of derivative information to improve the computation.  
When the dimension \(N\) is very large, also numerical methods which require at the same time \(O(N)\) active points might be impracticable. This is the case, for example, of methods such as Nelder-Mead algorithm [7] which works on a polytope of \(N+1\) vertices, or Differential Evolution [8] which generates at each iteration a new population of more than \(N+1\) points, or Simulated Annealing [9] which for the continuous minimization uses a downhill simplex of \(N+1\) points. In this paper we propose a method which allows solving Problem (1) also when \(N\) is very large. To validate its performances against other methods, it is necessary to restrict our experimentation to dimensions where the other methods could still compute reliable solutions.