Development of global search algorithms for global search problems and their analysis
Min Sun, Xiaoli Yang · 2006
Any problem seeking for all points contained in a given set and satisfying a given property is called a global search problem. Global search problems arise in many areas of practical applications. Global optimization problems and constraint satisfaction problems are two important global search problems. Eight global search problems are listed in this thesis. Solving global search problems is a challenging mathematical problem. Presented in this thesis is the prototype of a very general algorithm referred to as Division - Deletion Algorithm (DDA) for solving the most general global search problem. Various necessary conditions, sufficient conditions, and necessary and sufficient conditions for the convergence of the algorithm are proposed and analyzed. As examples of its application, we demonstrate that the convergences of a standard Hansen's interval algorithm for unconstrained global optimization, a standard interval algorithm for constrained global optimization, and a standard interval algorithm for constraint satisfaction problem simply follow from our general theory. We propose three interval algorithms for solving two kinds of simple constraint satisfaction problems and for locating all discontinuities of a function. We also demonstrate their convergence. Our results would provide useful guidelines for developing new implementations of global search algorithms, and reliable theoretical justifications for their convergence as well as convergence of existing algorithms. In particular, we hope that this research will lead to a series of new results in the global optimization and in global search in general.