mwang (04/26/83)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
NUMERICAL ANALYSIS SEMINAR
- Tuesday, May 3, 1983.
Dr. G.T. Timmer of Erasmus Universiteit will speak on
``Stochastic Methods for Unconstrained and Constrained
Global Optimization''.
TIME: 3.30 PM
ROOM: MC 5158
ABSTRACT
Stochastic techniques enter the design as well as the
analysis of several efficient methods to find the glo-
bal minimum of a function f over a compact set S. A
method will be presented where in each iteration a
group of points randomly drawn from a (possibly chang-
ing) distribution over S are added to a sample and a
procedure similar to clustering is applied to a (possi-
bly changing) fraction of this sample. This is done in
such a way that the clusters found correspond to re-
gions of attraction of f. Inside each newly found re-
gion of attraction a local search is initiated. The
method is (asymptotically) provably correct and prov-
ably fast: the expected running time in iteration k
does not depend on k , but is bound by a constant.
Under various probabilistic assumptions about f and
its local minima, the probability distribution of the
actual number of local minima and the relative measure
of their regions of attraction can be derived in a
Bayesian manner. This can be used to formulate proper
stopping criteria for the method described.
All these ideas can be applied to both unconstrained
and constrained global optimization. In the case of
constrained global optimization, the restricted problem
is transformed to an unrestricted one using a so-called
doubly-exact penalty function. This penalty function
has the property that there is a 1-1 correspondence
between the local minima of the constrained and the un-
constrained problem.
April 26, 1983