The chaotic behaviour of search algorithms (Q1314871)

Certain search algorithms produce a sequence of decreasing regions converging to a point \(x\). After renormalizing to a standard region at each iteration, the renormalized location of \(x\) may obey a dynamic process. In this case, simple ergodic theory might be used to compute asymptotic rates. The family of ``second-order'' line search algorithms for local minimization which includes the Golden Section (GS) method has this property. The paper exhibits several alternatives to GS which have better almost sure asymptotic rates of convergence for symmetric functions despite the fact that GS is asymptotically minimax. The discussion in the last section includes weakening of the symmetry condition and announces a backtracking bifurcation algorithm with optimum asymptotic rate.