Nested partitions method for global optimization
成果类型：
Article
署名作者：
Shi, LY; Olafsson, S
署名单位：
University of Wisconsin System; University of Wisconsin Madison; Iowa State University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.48.3.390.12436
发表日期：
2000
页码：
390-407
关键词：
摘要：
We propose a new randomized method for solving global optimization problems. This method, the Nested Partitions (NP) method, systematically partitions the feasible region and concentrates the search in regions that are the most promising, The most promising region is selected in each iteration based on information obtained from random sampling of the entire feasible region and local search. The method hence combines global and local search. We first develop the method for discrete problems and then show that the method can be extended to continuous global optimization. The method is shown to converge with probability one to a global optimum in finite time. In addition, we provide bounds on the expected number of iterations required for convergence, and we suggest two stopping criteria. Numerical examples are also presented to demonstrate the effectiveness of the method.