CARTopt: a random search method for nonsmooth unconstrained optimization

A random search algorithm for unconstrained local nonsmooth optimization is described. The algorithm forms a partition on <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathbb{R}^{n}$</EquationSource> </InlineEquation> using classification and regression trees (CART) from statistical pattern recognition. The CART partition defines desirable subsets where the objective function f is relatively low, based on previous sampling, from which further samples are drawn directly. Alternating between partition and sampling phases provides an effective method for nonsmooth optimization. The sequence of iterates {z <Subscript> k </Subscript>} is shown to converge to an essential local minimizer of f with probability one under mild conditions. Numerical results are presented to show that the method is effective and competitive in practice. Copyright Springer Science+Business Media New York 2013