On the separability of multivariate functions
For optimization practitioners, this provides a method to detect separability in black-box functions, potentially reducing problem dimensionality, though the approach is incremental.
The paper proposes a Monte Carlo-based algorithm to estimate the separability of black-box multivariate functions, including the number and composition of disjoint variable subsets, with computational complexity ranging from linear to exponential in dimension.
Separability of multivariate functions alleviates the difficulty in finding a minimum or maximum value of a function such that an optimal solution can be searched by solving several disjoint problems with lower dimensionalities. In most of practical problems, however, a function to be optimized is black-box and we hardly grasp its separability. In this study, we first describe a general separability condition which a function defined over an arbitrary domain satisfies if and only if the function is separable with respect to given disjoint subsets of variables. By introducing an alternative separability condition, we propose a Monte Carlo-based algorithm to estimate the separability of a function defined over unit cube with respect to given disjoint subsets of variables. Moreover, we extend our algorithm to estimate the number of disjoint subsets and the disjoint subsets such that a function is separable with respect to them. Computational complexity of our extended algorithm is function-dependent and varies from linear to exponential in the dimension.