Voronoi recursive binary trees for the optimization of nonlinear functionals

We propose an algorithm for the approximate solution of general nonlinear functional optimization problems through recursive binary Voronoi tree models. Unlike typical binary tree structures commonly employed for classification and regression problems, where splits are performed parallel to the coordinate axes, here the splits are based on Voronoi cells defined by a pair of centroids. Models of this kind are particularly suited to functional optimization, where the optimal solution function can easily be discontinuous even for very smooth cost functionals. In fact, the flexible nature of Voronoi recursive trees allows the model to adapt very well to possible discontinuities. In order to improve efficiency, accuracy and robustness, the proposed algorithm exploits randomization and the ensemble paradigm. To this purpose, an ad hoc aggregation scheme is proposed. Simulation tests involving various test problems, including the optimal control of a crane-like system, are presented, showing how the proposed algorithm can cope well with discontinuous optimal solutions and outperform trees based on the standard split scheme.