Buch, Englisch, 240 Seiten, Format (B × H): 163 mm x 242 mm, Gewicht: 499 g
Buch, Englisch, 240 Seiten, Format (B × H): 163 mm x 242 mm, Gewicht: 499 g
Reihe: Chapman & Hall/CRC Interdisciplinary Statistics
ISBN: 978-0-8493-0336-4
Verlag: Chapman and Hall/CRC
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.
Fachgebiete
Weitere Infos & Material
INTRODUCTIONCONSISTENCYConsistency in Discrete SearchLine-Search AlgorithmsConsistency in Linear and Convex ProgrammingRENORMALISATIONTowards a Dynamical System RepresentationRenormalisation in Line-Search AlgorithmsRenormalisation of Ellipsoid AlgorithmsRenormalisation in the Steepest Descent AlgorithmSquare AlgorithmRATES OF CONVERGENCEErgodic Rates of ConvergenceCharacteristics of Average PerformancesCharacteristics of Worst-Case PerformancesCounting CharacteristicOne-Dimensional Piecewise Linear MappingsLINE-SEARCH ALGORITHMSFirst-Order Line SearchContinued Fraction Expansion and the Gauss MapGolden-Section AlgorithmErgodically Optimal Second-Order Line Search AlgorithmSymmetric AlgorithmsMidpoint and Window AlgorithmsAlgorithms Based on Section Invariant NumbersComparisons of GS, GS4, GS40 and Window AlgorithmsELLIPSOID ALGORITHMSVolume-Optimal Outer and Inner EllipsoidsErgodic Behaviour of the Outer-Ellisoid AlgorithmSTEEPEST DESCENT ALGORITHMAttraction to a Two-Dimensional PlaneStability of AttractorsRate of ConvergenceSteepest Descent with RelaxationAppendixEntropiesErgodic TheorySection-Invariant NumbersReferencesAuthor IndexSubject Index
