An adaptive procedure for the global minimization of a class of polynomial functions

The paper deals with the problem of global minimization of a polynomial function expressed through the Frobenius norm of two dimensional or three-dimensional matrices. An adaptive procedure is proposed which applies a random search algorithm according to a heuristic approach. The basic step of the procedure consists in splitting the runs of different initial points in segments of fixed length and to interlace the processing order of the various segments, discarding those which appear less promising. A priority queue is suggested to implement this strategy. Various parameters contribute to the handling of the queue, whose length shrinks during the computation, allowing a considerable saving of the computational time with respect to classical procedures. To verify the validity of the approach, a large experimentation has been performed on both nonnegatively constrained and unconstrained problems.