×

Dynamic systems in search and optimisation. (English) Zbl 0876.90084

Applications of dynamical systems to the study of optimisation and search algorithms are considered. The main idea is renormalisation. The simplest example is the bisection method to find the zeros of a linear function \(f\) in \([0,1]\). At each iteration \(n\) of the algorithm one half of \([0,1]\), not having a zero, is deleted, and the other half is renormalised to \([0,1]\). So a zero at \(n\)-th iteration is considered as a point \(x\in [O,1]\), and we get the dynamical system \(x_{n+1}= TX_n= 2x_n\pmod 1\). This approach opens up the possibility of usiug the machinery of ergodic theory and chaos.
The contraction in size at \(n\)-th iteration of an interval, containing the target, reflects expansion of intervals in the dynamical system. Ergodic convergence rate and ergodic log-rate are defined. The rate of divergence of orbits of dynamical system is measured by the Lyapunov exponents. The relation between ergodic log-rate and the Lyapunov exponents is considered. Attractors are applied as well. Attainable convergence rates of algorithms are discussed. The method is applied to the various algorithms such as line search, Golden Section and others. The authors hope that search algorithms and optimisation may provide a new area of application of dynamical systems.

MSC:

90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite