Browsing by Author "Alexander, D.L.J."

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Convergence of alternating Markov chains
    (2005) Jones, G.; Alexander, D.L.J.
    Suppose we have two Markov chains defined on the same state space. What happens if we alternate them? If they both converge to the same stationary distribution, will the chain obtained by alternating them also converge? Consideration of these questions is motivated by the possible use of two different updating schemes for MCMC estimation, when much faster convergence can be achieved by alternating both schemes than by using either singly.
  • Thumbnail Image
    Item
    Convergence rates of stochastic global optimisation algorithms with backtracking : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Statistics at Massey University
    (Massey University, 2004) Alexander, D.L.J.
    A useful measure of quality of a global optimisation algorithm such as simulated annealing is the length of time it must be run to reach a global optimum within a certain accuracy. Such a performance measure assists in choosing and tuning algorithms. This thesis proposes an approach to obtaining such a measure through successive approximation of a generic stochastic global optimisation algorithm with a sequence of stochastic processes culminating in backtracking adaptive search. The overall approach is to approximate the progress of an optimisation algorithm with that of a model process, backtracking adaptive search. The known convergence rate of the model then provides an estimator of the unknown convergence rate of the original algorithm. Parameters specifying this model are chosen based on observation of the optimisation algorithm. The optimisation algorithm may first be approximated with a time-inhomogeneous Markovian process defined on the problem range. The distribution of the number of iterations to convergence for this averaged range process is shown to be identical with that of the original process. This process is itself approximated by a time-homogeneous Markov process in the range, the asymptotic averaged range process. This approximation is defined for all Markovian optimisation algorithms and a weak condition under which its convergence time closely matches that of the original algorithm is developed. The asymptotic averaged range process is of the same form as backtracking adaptive search, the final stage of approximation. Backtracking adaptive search is an optimisation algorithm which generalises pure adaptive search and hesitant adaptive search. In this thesis the distribution of the number of iterations for which the algorithm runs in order to reach a sufficiently extreme objective function level is derived. Several examples of backtracking adaptive search on finite problems are also presented, including special cases that have received attention in the literature. Computational results of the entire approximation framework are reported for several examples. The method can be applied to any optimisation algorithm to obtain an estimate of the time required to obtain solutions of a certain quality. Directions for further work in order to improve the accuracy of such estimates are also indicated.