Skip to Content

Dynamical Search

Applications of Dynamical Systems in Search and Optimization

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

Series Editor: Byron J.T. Morgan, Niels Keiding

Chapman and Hall/CRC – 1999 – 240 pages

Series: Chapman & Hall/CRC Interdisciplinary Statistics

Purchasing Options:

  • Add to CartHardback: $159.95
    978-0-8493-0336-4
    August 26th 1999

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.

Reviews

"…a fascinating book which links optimization algorithms with the properties of certain dynamical systems. This link allows one to better understand the optimization algorithms, and to ultimately construct more efficient versions of them…"

-Short Book Reviews of the ISI

"There is a great need for a text which provides this deeper level of consideration and rigour."

--Stephen Clark, University of Leeds, UK

"…an established research programme which aims to link the areas of dynamical systems and search theory. … The book is of value to those researchers and academics who have an interest in this area and wish to explore the research ideas that it contains in a more extensive coverage than is usually found in reports and journal papers."

-The Statistician, Vol. 50, Part 1, 2001

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

Name: Dynamical Search: Applications of Dynamical Systems in Search and Optimization (Hardback)Chapman and Hall/CRC 
Description: By Luc Pronzato, Henry P. Wynn, Anatoly A ZhigljavskySeries Editor: Byron J.T. Morgan, Niels Keiding. 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,...
Categories: Probability Theory & Applications, Mathematics & Statistics for Engineers, Statistical Theory & Methods