Stochastic global optimisation algorithms

This thesis addresses aspects of stochastic algorithms for the solution of global optimisation problems. The bulk of the research investigates algorithm models of the adaptive search variety. Performances of stochastic and deterministic algorithms are also compared.

Chapter 2 defines pure adaptive search, the prototypical improving region search scheme from the literature. Analyses from the literature of the search duration of pure adaptive search in two specialised situations are recounted and interpreted. In each case pure adaptive search is shown to require an expected search time which varies only linearly with the dimension of the feasible region.

In Chapter 3 a generalisation of pure adaptive search is introduced under the name of hesitant adaptive search. This original algorithm retains the sample point generation mechanism of pure adaptive search, but allows for hesitation, in which an algorithm iteration passes without an improving sample being located. In this way hesitant adaptive search is intended to model more closely practically implementable algorithms. The analysis of the convergence of hesitant adaptive search is more thorough than the analyses already appearing in the literature, as it describes how hesitant adaptive search behaves when given more general objective functions than in previous studies. By specialising to the case of pure adaptive search we obtain a unification of the results appearing in those papers.

Chapter 4 is the most applied of the chapters in this thesis. Here hesitant adaptive search is specialised to describe the convergence behaviour of localisation search schemes. A localisation search scheme produces a bracket of the current improving region at each iteration. The results of Chapter 3 are applied to find necessary and sufficient conditions on the 'tightness' of the brackets to ensure that the dependence of the expected search duration on the dimension of the feasible region is linear, quadratic, cubic, and so forth.

Chapter 5 describes another original generalisation of pure adaptive search, known as fenestral adaptive search. This algorithm generates sample points from a region determined not merely by the previous sample, but by the previous w samples, where w is some prespecified positive integer. The expected search duration of fenestral adaptive search is greater than that of pure adaptive search, but still varies only linearly with the dimension of the feasible region. The sequence of objective function values obtained constitutes an interesting stochastic process, and Chapter 5 is devoted to understanding this process.

Chapter 6 presents a theoretical comparison of the search durations of deterministic and stochastic global optimisation algorithms, together with some discussion of the implications. It is shown that to any stochastic algorithm, there corresponds a deterministic algorithm which requires no more iterations on average, but we discuss why stochastic algorithms may still be more efficient than their deterministic counterparts in practice.