Nested Partitions Method for Global Optimization

Leyuan Shi () and Sigurdur Ólafsson ()
Additional contact information
Leyuan Shi: Department of Industrial Engineering, University of Wisconsin --- Madison, 1513 University Avenue, Madison, Wisconsin 53706
Sigurdur Ólafsson: IMSE Department, Iowa State University, 2019 Black Engineering, Ames, Iowa 50011

Operations Research, 2000, vol. 48, issue 3, 390-407

Abstract: 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.

Keywords: Programming: randomized global optimization; Mathematics; combinatorics: optimization; Probability; Markov processes: convergence (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (40)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.48.3.390.12436 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:48:y:2000:i:3:p:390-407

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().