A peak-over-threshold search method for global optimization

In this paper, we propose a random search method, called peak-over-threshold search (POTS), for solving global optimization problems. An important feature of POTS is that it combines the existing partition-based random search framework (e.g., Shi and Ólafsson 2000a; Chen et al. 2011) with the peak-over-threshold statistical reference (Coles, 2001) in order to achieve high search efficiency. In each iteration, POTS partitions the solution space into several subregions, evaluates the quality of each subregion and moves to promising subregions for more partitioning and sampling. To effectively assess the quality of a subregion, an extreme value type of inference in statistics is used to develop a new promising index which reflects the optimal objective value of a subregion and biases the search to regions that are likely to contain the optimal or near-optimal solutions. Under assumptions on the depth of partitioning and the probability of correct movement, POTS is shown to converge with probability one to the optimal region. The higher efficiency of the proposed method is illustrated by numerical examples. The application of POTS to beam angle selection, an important optimization problem in radiation treatment, is also presented in this paper.