A CARTopt method for bound constrained global optimization

Abstract

A stochastic method for bound constrained global optimization is described. The method can be applied to objective functions which are nonsmooth or even discontinuous. The algorithm forms a partition on the search region using classification and regression trees (CART), which defines desirable subsets where the objective function is relatively low. Further samples are drawn directly from these low subsets before a new partition is formed. Alternating between sampling and partition phases provides an effective method for nonsmooth global optimization. The sequence of iterates generated by the algorithm is shown to converge to a global minimizer of the objective function with probability one under mild conditions. Non-probabilistic results are also give when random sampling is replaced with samples taken from the Halton sequence. Numerical results are presented for both smooth and nonsmooth problems and show that the method is effective and competitive in practice. doi:10.1017/S1446181113000412