Scalable Approximate Optimization of Objective Functions Represented by Random Forests

The problem of global optimization of an objective function represented by a Random Forest (RF) is considered. A method to obtain an approximate solution at low computational complexity is proposed, resorting to the inherent structure of an RF, which is a non-parametric model that partitions the feature space in convex polytopes according to the training data. The approach selects the optimal solution inside the polytopes corresponding to the best data points. It is shown that the proposed approximate method is significantly more efficient, thus applicable at large scale, than extensive global search algorithms, such as gridding and Mixed Integer Linear Programming (MILP), which in turn provide exact solutions. The efficiency and sub-optimality of the approach are evaluated on RFs trained on a dataset generated by sampling a bivariate, discontinuous and non-convex benchmark function from the literature.