Topics in Lipschitz global optimisation
Degree GrantorUniversity of Canterbury
Degree NameDoctor of Philosophy
The global optimisation problem has received much attention in the past twenty-five years. The problem is to find an algorithm which will locate the overall, or global, optimum of a function. It can be viewed as a computer-age approach to the problem approached analytically by Newton over three hundred years ago. While Newton's algorithm deals with convex optimisation problem, the development of global optimisation approaches cover more general cases. It is a problem of considerable practical importance chemists, physicists, engineers and statisticians need answers to such minimisation or maximisation problems. The problem is insoluble without imposing some regularity conditions on the function to be optimised. The simplest such regularity condition is that of Lipschitz continuity - an acknowledgement that the function cannot vary by more than a fixed amount as the independent variables move in a fixed region. The most acknowledged pioneer work on Lipschitzian global optimisation for objective functions of one variable was independently produced by Piyavskii and Shubert in 1967 and in 1972 respectively. The former Soviets have placed great emphasis on this approach to the problem, relating many of their methods back to the work of Piyavskii. A number of higher dimensional generalisations of the Piyavskii-Shubert algorithm have since been developed, including those due to Mladineo (1986), Pinter (1986) and Wood (1992). Apart from deterministic approaches to the global optimisation problem for Lipschitz continuous functions mentioned above, active research is being conducted to find stochastic methods to solve this problem. The pure adaptive search analysed by Zabinsky and Smith offered considerable hope for researchers pursuing practical stochastic methods to solve the problem. Pure adaptive search gives a linear complexity convergence result in dimension. For deterministic algorithms the computational complexity of convergence is exponential. A general introduction to the field of global optimisation and to the more specific topics studied in this thesis is presented in the first chapter. Chapters two and three are devoted to the development and properties of Lipschitz based algorithms. A survey of selected deterministic and stochastic Lipschitz global optimisation algorithms is first presented. The tightest lower bounding function of an objective function after a set of evaluations and a necessary condition for finite convergence of Lipschitz based approaches is obtained. The multidimensional bisection algorithm of Wood is discussed in detail in Chapter four. The context and acceleration strategies for the multidimensional bisection algorithm are presented. The performance of numerical acceleration methods is described for certain test functions. The context of multidimensional bisection is studied by showing such algorithms fall in a broadened branch and bound framework. A higher dimensional localisation convergence result is obtained. A stochastic method, pure localisation search, is presented and studied in Chapter five. This is an attempt to find an efficiently implementable algorithm, based on a stochastic variant of the Piyavskii-Shubert algorithm, which can realise the desirable linear complexity in dimension of pure adaptive search. Comparison of pure localisation search with pure adaptive search, pure random search and the Piyavskii-Shubert algorithm is given. Estimation of the Lipschitz constant of a function is investigated in Chapter six. It is itself a global optimisation problem. Existing methods for such estimation are surveyed. A new stochastic approach is developed. The distribution of the largest absolute slope in a fixed size sample of absolute slopes is shown to approximate a well known distribution. The location parameter of this distribution is used as an estimate of the Lipschitz constant. The applicability of this method is studied for univariate and multivariate functions. Numerical results are presented.