The identification of complex multicomponent material formulations that possess specific optimal properties is a challenging task in materials discovery. The high dimensional composition space needs to be adequately sampled and the properties measured with the goal of efficiently identifying effective formulations. This task must also take into account mass fraction and possibly other constraints placed on the material components. Either combinatorial or noncombinatorial sampling of the composition space may be employed in practice. This paper introduces random sampling-high dimensional model representation (RS-HDMR) as an algorithmic tool to facilitate these nonlinear multivariate problems. RS-HDMR serves as a means to accurately interpolate over sampled materials, and simulations of the technique show that it can be very efficient. A variety of simulations is carried out modeling multicomponent-->property relationships, and the results show that the number of sampled materials to attain a given level of accuracy for a predicted property does not significantly depend on the number of components in the formulation. Although RS-HDMR best operates in the laboratory by guided iterative rounds of random sampling of the composition space along with property observation, the technique was tested successfully on two existing databases of a seven component phosphor material and a four component deNO(x) catalyst for reduction of NO with C(3)H(6).