Computational methods for optimization via simulation using Gaussian Markov Random Fields

There has been recent interest, and significant success, in adapting and extending ideas from statistical learning via Gaussian process (GP) regression to optimization via simulation (OvS) problems. At the heart of all such methods is a GP representing knowledge about the objective function whose conditional distribution is updated as more of the feasible region is explored. Calculating the conditional distribution requires inverting a large, dense covariance matrix, and this is the primary bottleneck for applying GP learning to large-scale OvS problems. If the GP is a Gaussian Markov Random Field (GMRF), then the precision matrix (inverse of the covariance matrix) can be constructed to be sparse. In this paper we show how to exploit this sparse-matrix structure to extend the reach of OvS based on GMRF learning for discrete-decision-variable problems.