Relaxing the Assumptions of the Multilevel Single Linkage Algorithm

In this paper we relax the assumptions of a well known algorithm for continuous global optimization, Multilevel Single Linkage (MLSL). It is shown that the good theoretical properties of MLSL are shared by a slightly different algorithm, Non-monotonic MLSL (NM MLSL), but under weaker assumptions. The main difference with MLSL is the fact that in NM MLSL some non-monotonic sequences of sampled points are also considered in order to decide whether to start or not a local search, while MLSL only considers monotonic decreasing sequences. The modification is inspired by non-monotonic methods for local searches. This revised version was published online in July 2006 with corrections to the Cover Date.