Dynamical system approach for studying convergence of
search algorithms
Even in simple cases,
algorithms that are simply convergent can be considered as dynamic systems,
after a suitable transformation is applied to each iteration. The main idea is
to renormalise the region containing the search object x, for instance the
point where a given function f(.) is optimum, so that the target remains in a
standard region X. Therefore x is no longer fixed but moves in X at each
iteration, and follows the evolution of a dynamic system. Methods of analysis
relying on ergodic theory and chaos thus apply. Various algorithms are
considered, e.g. line search, ellipsoid, steepest descent. The associated
dynamic systems show different features: in some cases the asymptotic behaviour
depends on x and/or on the function f(.), and periodic and strange attractors
are typical. A main purpose is to use the theory of dynamic systems to analyse
the asymptotic behaviour of the algorithms, and, when possible, to obtain
optimal rates of convergence.
References
Monograph:
Pronzato L., Wynn, H.P., Zhigljavsky, A. (2000) Dynamical search. Applications of dynamical systems in search and optimization. Chapman & Hall/CRC, Boca Raton
Selected articles:
- Wynn H.P., Zhigljavsky A.A. (1993) Chaotic behaviour of search algorithms. Acta Applicandae Mathematicae, 1993, 32, 123-156.
- Wynn H.P., Zhigljavsky A.A. (1995) Achieving the ergodically optimal convergence rate for a one-dimensional minimization problem. Journal of Complexity, 11,196-226.
- Pronzato L., Wynn H.P., Zhigljavsky A.A. (1995) Dynamic systems in search and optimization, CWI Quarterly, 8, 201-236.
- Pronzato L., Wynn H.P., Zhigljavsky A.A. (1997) Stochastic analysis of convergence via dynamic representation for a class of line-search algorithms. Combinatorics, Probability and Computing, 6, 205-229.
- Zhigljavsky A.A., Pronzato L., Wynn H.P. (1998) Section-invariant numbers and generalised Golden Section algorithms, Application of Fibonacci Numbers, v. 7 (G.E.Bergum, A.N.Philippou, F.Horadam, eds.), Kluwer Academic Publishers, Dordrecht e.a., 463-477.
- Pronzato L., Wynn H.P., Zhigljavsky A.A. (1998) A generalised Golden-Section algorithm for line-search, IMA Journal on Math. Control and Information, 15, 185-214.
- Pronzato L., Wynn H.P., Zhigljavsky A.A. (1999) Finite sample behaviour of an ergodically fast line-search algorithm, Computational Optimisation and Applications, 14, 75-86.
- Pronzato L., Wynn H.P.,
Zhigljavsky A.A. (2001) Some convergence properties of the steepest
descent algorithm revealed by renormalisation, in: Advances in
convex analysis and global optimization, (ser. Nonconvex Optim. Appl.,
54), Kluwer Academic Publishers,
- Pronzato L., Wynn H.P., Zhigljavsky A.A. (2001) Analysis of performance of symmetric second-order line search algorithms through continued fractions, IMA J. on Math Control and Information, 18, 281-296.
- Pronzato L., Wynn H.P., Zhigljavsky A.A. (2001) Renormalised steepest descent in Hilbert space converges to a two-point attractor, Acta Applicandae Mathematicae, 67, 1-18.
- Pronzato L., Wynn H.P.,
Zhigljavsky A.A. (2002) An introduction to dynamical search. Handbook of global optimization, Vol. 2, 115--150,
Nonconvex Optim. Appl., 62, Kluwer Acad. Publ.,
- Pronzato L., Wynn H.P.,
Zhigljavsky A.A. (2005) Kantorovich-type inequalities for operators via D-optimal
design theory. Linear Algebra Appl.
410 (2005), 160--169.
- Pronzato L., Wynn H.P., Zhigljavsky A.A. (2006) Asymptotic behaviour of a family of gradient algorithms in R^ d and Hilbert spaces. Math. Program. 107, no. 3, Ser. A, 409--438.