Clustering Methods
Overview
Clustering global optimization methods can be viewed as a modified form
of the standard multistart procedure, which performs a local search
from several points distributed over the entire search domain. A
drawback of Multistart is that when many starting points are used the
same local minimum may identified several times, thereby leading to an
inefficient global search. Clustering methods attempt to avoid this
inefficiency by carefully selecting points at which the local search is
initiated. The three main steps of clustering methods are: (1) sample
points in the search domain, (2) transform the sampled point to group
them around the local minima, and (3) apply a clustering technique to
identify groups that (hopefully) represent neighborhoods of local
minima. If this procedure successfully identifies groups that
represent neighborhoods of local minima, then redundant local searches
can be avoided by simply starting a local search for some point within
each cluster.
Application Domains
Clustering methods have been developed for optimizing unconstrained
functions over reals. These methods assume that the objective function
is relatively inexpensive since many points are randomly sampled to
identify the clusters. Clustering methods are most effective for low
dimensional problems, so these methods become less effective for
problems of more than a few hundred variables.
Aimo Törn's review
of clustering methods describes a variety of applications.
Software
An implementation of the Boender-Timmer-Rinnoy Kan clustering
algorithm by Tibor Csendes is located (here).
References
Aimo Törn's review
of clustering methods includes a bibliography of research on
clustering methods.
Törn, Aimo and Zilinskas, Antanas. Global
Optimization. Lecture Notes in Computer Science, No 350, 255
pp. Springer Verlag, Heidelberg,1989.
Provides a detailed description of clustering methods and their variants.
Miscellaneous Links
None.