Binary Voronoi linear trees for the approximate solution of functional optimization problems

The need to find solutions in function form that optimize a given nonlinear cost functional arises routinely in many important areas of operations research and applied mathematics. In most practical cases, problems of this kind require a numerical solution based on some suitable class of approximating architectures. This paper introduces the use of binary Voronoi linear trees (BVLTs) for the approximate solution of a general class of functional optimization problems. The main features of the considered trees are (i) a splitting scheme based on a Voronoi bisection criterion and (ii) linear outputs in the leaves, which make the resulting models more flexible compared to classic trees with cuts parallel to the axes and constant outputs. At the same time, due to the binary recursive structure, BVLTs retain the well-known efficiency of decision tree architectures. Consistently with the typical tree construction framework, we provide a greedy algorithm for the approximate solution of the addressed functional optimization problem. Universal approximation capabilities of the proposed class of models are derived in the theoretical analysis, and the consistency of the solution is discussed as well. In order to improve accuracy and robustness, we also consider the use of BVLTs in ensemble fashion, through an aggregation scheme well suited to optimization purposes. Simulation tests involving various optimization problems are presented, showing how the proposed algorithm can cope well in complex multivariate contexts, especially in ensemble form.