Application of Global Sensitivity Indices for
Measuring the Effectiveness of Quasi-Monte Carlo Methods
and Parameter Estimation

S. Kucherenko
Imperial College London, UK
s.kucherenko@imperial.ac.uk

Many problems in physics and numerical analysis are concerned with high dimensional integrals. While the classical grid methods are very efficient for low dimensional integrands, they become computationally impractical when the number of dimensions n increases as the number of required integrand evaluations grows exponentially. This effect is known as ”the curse of dimensionality”. In contrast, the convergence rate of Monte Carlo (MC) integration methods dos not depend on the number of dimensions n. However, the rate of convergence O(1/N-1/2), where N is the number of sampled points, attained by MC is rather low. A higher rate of convergence can be obtained by using deterministic uniformly distributed sequences also known as low-discrepancy sequences (LDS) instead of pseudo-random numbers. Methods based on the usage of such sequences are known as Quasi Monte Carlo (QMC) methods. Asymptotically, QMC can provide the rate of convergence O(1/N). For sufficiently large N, QMC should always outperform MC. However, in practice such sample sizes quite often are infeasible, especially when high dimensional problems are concerned. Some numerical experiments demonstrated that the advantages of QMC can disappear for high-dimensional problems. There were claims that the degradation in performance of QMC occurs at n > 12 [1]. At the same time there are known high-dimensional problems for which QMC significantly outperforms MC. 
Global sensitivity analysis (SA) offers a general practical way to predict the efficiency of QMC algorithms. Using the Sobol’ method of global sensitivity indices the classification of some important classes of integrable functions is developed [2]. Functions with respect to their dependence on the input variables can be divided into three categories: functions with not equally important variables ( type A ), functions with equally important variables and with dominant low order terms ( type B ) and functions with equally important variables and with dominant interaction terms ( type C ). For functions of type A and B, QMC is even in the high dimensional case superior to MC while for functions of type C, QMC looses its advantage over MC because of the importance of higher-order terms in the corresponding ANOVA decomposition. The results of numerical tests verify the prediction of the suggested classification.
The technique for prediction the efficiency of QMC methods was extended for the case of Wiener path integrals. In [2] it was applied for analysis the differences in performances of two well-known approximations of a test path integral. The standard and the Brownian discretization schemes used in MC option pricing were compared in [3]. Global SA reveals that the variance of the samples generated for the Brownian path slowly decreases with time step index for the standard discretisation for the case of Asian call options. The higher order interactions in the ANOVA decomposition of payoff functions are very important. Therefore, the effective dimensions for standard discretization is close to the real dimension. Although the standard discretisation with QMC sampling is superior to MC, the convergence rate of the QMC method is much lower than that of the Brownian bridge discretisation and it decreases as dimensionality grows. 
The Brownian bridge discretisation of the Brownian path results in significant improvement of the accuracy of QMC especially when the number of time steps n is large. For the Brownian bridge discretisation the sensitivity indices of the first few variables are much larger than those of the subsequent variables. Application of the Brownian bridge discretization greatly reduces the effective dimension and consequently increases the efficiency of QMC. Its efficiency practically does not depend on the problem dimensionality. 

A new approach for parameter estimation within the framework of optimal experimental design (OED) is developed. OED allows the identification of a set of experiments with conditions that deliver measurement data the most sensitive to the unknown parameters. One of the common ways to design experiments is to use scalar functions of the Fisher information matrix (FIM) evaluated at the nominal values of the parameters. This information matrix is based on the linear sensitivity coefficients of the response variables. The results of a FIM based OED depend on the nominal values used for the parameters. Moreover, preliminary experiments and model calibration tests need to be carried out in order to obtain a first guess for the parameter values and a slowly converging iterative scheme is required [4]. These linear methods are not sufficient for dealing with complex OED problems, especially those in which nonlinear interactions between parameters are present.
These limitations can be overcome by the application of global sensitivity indices and defining the Global Fisher Information Matrix (GFIM ) as
,				
where matrix  has a form
.			
Here  is the Sobol’ sensitivity index for parameter of the r-th response variable at -th moment of time. Once GFIM is defined the maximization of the determinant
.					
leads to an optimal vector of input variables. This approach was applied to some cases studies in [5]. The results demonstrated methods ability to significantly reduce the required experimental work and illustrated the effectiveness of the global SA techniques for the design of reliable dynamic experiments.

Acknowledgement:

Author expresses his gratitude to I. Sobol’ N. Shah, W. Mauntz and M. Rodriguez Fernandez for their valuable contributions and interest in this work. Author gratefully acknowledges the financial support by the EPSRC grant EP/D506743/1.

References

[1] Bratley P, Fox BL, Niederreiter H: Implementation and tests of low- discrepancy sequences. ACM Transactions on Modeling and Computer Simulation 2(3), 195-213 (1992)

[2] Kucherenko S, Mauntz W: Application of global sensitivity indexes for measuring the effectiveness of quasi-Monte Carlo method. Submitted to Monte Carlo Methods and Simulation (2007)

[3] Sobol’ IM, Kucherenko S: On global sensitivity analysis of quasi-Monte Carlo algorithms. Monte Carlo Methods and Simulation 11, 1, 1-9 (2005)

[3] Kucherenko S, Shah N: The importance of being global. Application of global sensitivity analysis in Monte Carlo option pricing. To be published in Wilmott (2007)

[4] Walter E, Pronzato L: Identification of Parametric Models from Experimental Data. Springer, 1997.

[5] Rodriguez-Fernandez M, Kucherenko S, Pantelides C, Shah N.: Optimal experimental design based on global sensitivity analysis. Submitted to 17th European Symposium on Computer Aided Process Engineering (ESCAPE17), 2007.