Dynamical search : applications of dynamical systems in search and optimization : interdisciplinary statistics

Author(s)

• Pronzato, Luc
• Wynn, Henry P.
• Zhigli︠a︡vskiĭ, A. A. (Anatoliĭ Aleksandrovich)

Bibliographic Information

Dynamical search : applications of dynamical systems in search and optimization : interdisciplinary statistics

Luc Pronzato, Henry P. Wynn, Anatoly A. Zhigljavsky

Chapman & Hall/CRC Press, c2000

Note

Includes bibliographical references and index

Description and Table of Contents

Description

Certain algorithms that are known to converge can be renormalized or "blown up" at each iteration so that their local behavior can be seen. This creates dynamical systems that we can study with modern tools, such as ergodic theory, chaos, special attractors, and Lyapounov exponents. Furthermore, we can translate the rates of convergence into less studied exponents known as Renyi entropies. This all feeds back to suggest new algorithms with faster rates of convergence. For example, in line-search, we can improve upon the Golden Section algorithm with new classes of algorithms that have their own special-and sometimes chaotic-dynamical systems. The ellipsoidal algorithms of linear and convex programming have fast, "deep cut" versions whose dynamical systems contain cyclic attractors. And ordinary steepest descent has, buried within, a beautiful fractal that controls the gateway to a special two-point attractor. Faster "relaxed" versions exhibit classical period doubling. Dynamical Search presents a stimulating introduction to a brand new field - the union of dynamical systems and optimization. It will prove fascinating and open doors to new areas of investigation for researchers in both fields, plus those in statistics and computer science.

Table of Contents

INTRODUCTION CONSISTENCY Consistency in Discrete Search Line-Search Algorithms Consistency in Linear and Convex Programming RENORMALISATION Towards a Dynamical System Representation Renormalisation in Line-Search Algorithms Renormalisation of Ellipsoid Algorithms Renormalisation in the Steepest Descent Algorithm Square Algorithm RATES OF CONVERGENCE Ergodic Rates of Convergence Characteristics of Average Performances Characteristics of Worst-Case Performances Counting Characteristic One-Dimensional Piecewise Linear Mappings LINE-SEARCH ALGORITHMS First-Order Line Search Continued Fraction Expansion and the Gauss Map Golden-Section Algorithm Ergodically Optimal Second-Order Line Search Algorithm Symmetric Algorithms Midpoint and Window Algorithms Algorithms Based on Section Invariant Numbers Comparisons of GS, GS4, GS40 and Window Algorithms ELLIPSOID ALGORITHMS Volume-Optimal Outer and Inner Ellipsoids Ergodic Behaviour of the Outer-Ellisoid Algorithm STEEPEST DESCENT ALGORITHM Attraction to a Two-Dimensional Plane Stability of Attractors Rate of Convergence Steepest Descent with Relaxation Appendix Entropies Ergodic Theory Section-Invariant Numbers References Author Index Subject Index

by "Nielsen BookData"

Details

• NCID: BA43505873
• ISBN:
  • 0849303362
• LCCN: 99032954
• Country Code: us
• Title Language Code: eng
• Text Language Code: eng
• Place of Publication: Boca Raton, Fla.
• Pages/Volumes: 221 p.
• Size: 24 cm
• Classification:
  • LCC : T57.97
  • DC21 : 003
• Subject Headings:
  • LCSH : Search theory
  • LCSH : Differentiable dynamical systems