Obtaining minimum-correlation Latin Hypercube Sampling plans using an IP-based heuristic

The objective of Latin Hypercube Sampling is to determine an effective procedure for sampling from a (possibly correlated) multivariate population to estimate the distribution function (or at least a significant number of moments) of a complicated function of its variables. The typical application involves a computer-based model in which it is largely impossible to find a way (closed form or numerical) to do the necessary transformation of variables and where it is expensive to run in terms of computing resources and time. Classical approaches to hypercube sampling have used sophisticated stratified sampling techniques; but such sampling may provide incorrect measures of the output parameters’ variances or covariances due to correlation between the sampling pairs. In this work, the authors offer a strategy which provides a sampling specification minimizing the sum of the absolute values of the pairwise differences between the true and sampled correlation pairs. They show that optimal plans can be obtained for even small sample sizes. The authors consider the characteristics of permutation matrices which minimize the sum of correlations between column pairs and then present an effective heuristic for solution. This heuristic generally finds plans which match the correlation structure exactly. When it does not, the authors provide a hybrid lagrangian/heuristic method, which empirically has found the optimal solution for all cases tested.