Nested Partitions Method for Global Optimization

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

Full description

Saved in:
Bibliographic Details
Published in:Operations research 2000-05, Vol.48 (3), p.390-407
Main Authors: Shi, Leyuan, Olafsson, Sigurdur
Format: Article
Language:English
Subjects:
Algorithms
Globalization
Heuristics
Iterative solutions
M region
Markov analysis
Markov chains
Mathematical functions
Mathematical minima
Mathematics, combinatorics: optimization
Methods
Operations research
Optimization
Probability
Probability, Markov processes: convergence
Programming: randomized global optimization
Random sampling
Sampling distributions
Theory
Transition probabilities
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.48.3.390.12436