Simple statistical tests selection based parallel computating method ensures the guaranteed global extremum identification

Abstract

The article proposes a parallel computing oriented method for solving the global minimum finding problems, in which continuous objective functions satisfy the Hölder condition, and the control parameters domain limited by continuous functions is characterized by a positive Lebesgue measure. A typical example of such a task is the discrepancy minimizing problem between the left and right parts of some large system of equilibrium equations (this is a usual situation when describing real process using Markov chain). The method is based on simple statistical tests, thanks to which, at each iteration, growing sets of potential global minima and sets of decrements necessary for estimating the values of the Hölder constants are formed. The article theoretically substantiates and empirically proves the guaranteed convergence of the authors’ method to the real global minimum, which occurs at an exponential rate. For the continuous iterations number, analytical upper estimates of the spacing between the potential global minima and real global minima are formalized, as well as an estimate of the probability of overcoming this spacing is formalized. The decrements sequence approximation, estimation of a priori unknown Hölder constants, estimation of the average number of iterations of the method and probabilistic characteristics of the final solution are analytically justified. In addition to the theoretical proof, the adequacy of the authors’ method has been confirmed empirically. It turned out that both the quality characteristics of the initial results calculated by the authors’ method and the time to obtain them are practically independent of the size of the search area. This expected result is a significant advantage of the authors’ method over analogues.

Keywords

• Parallel computating
• Applied mathematics
• Optimization problem
• Global extremum
• Statistical tests method
• Equilibrium