Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-27T08:54:17.996Z Has data issue: false hasContentIssue false
  • English
  • Français

Stochastic Analysis of Convergence via Dynamic Representation for a Class of Line-search Algorithms

Published online by Cambridge University Press:  01 June 1997

L. PRONZATO ,
H. P. WYNN  and
A. A. ZHIGLJAVSKY
L. PRONZATO
Affiliation:
Laboratoire I3S, CNRS-URA 1376, 250 rue A. Einstein, bât. 4, Sophia Antipolis, 06560 Valbonne, France
H. P. WYNN
Affiliation:
Department of Statistics, University of Warwick, Coventry CV4 7AL, UK
A. A. ZHIGLJAVSKY
Affiliation:
Department of Mathematics, St. Petersburg University, Bibliotechnaya sq.2, St. Petersburg, 198904 Russia
Get access Rights & Permissions [Opens in a new window]

Abstract

Certain convergent search algorithms can be turned into chaotic dynamic systems by renormalisation back to a standard region at each iteration. This allows the machinery of ergodic theory to be used for a new probabilistic analysis of their behaviour. Rates of convergence can be redefined in terms of various entropies and ergodic characteristics (Kolmogorov and Rényi entropies and Lyapunov exponent). A special class of line-search algorithms, which contains the Golden-Section algorithm, is studied in detail. Their associated dynamic systems exhibit a Markov partition property, from which invariant measures and ergodic characteristics can be computed. A case is made that the Rényi entropy is the most appropriate convergence criterion in this environment.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 6 , Issue 2 , June 1997 , pp. 205 - 229
Copyright
1997 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)