More Website Templates @ - September08, 2014!

Optimisation and Error in Simul?ation

22nd January 2016

This week, the STOR-i CDT put on a Master Class for the MRes students. This is set up so that an expert in a particular subject visits Lancaster University to give us an intense week of lectures and labs in their field. This week, the guest expert was Professor Barry Nelson from the Department of Industrial Engineering & Management Sciences at Northwestern University in Illinois, U.S.A, and his chosen subject was Stochastic Simulation Design and Analytics. For most of us, the word simulation conjures images of big flight simulators used for either pilot training or recreation, or the rollercoaster simulations from fairs (at least, that's what my mind thought). However, that wasn't really what Barry Nelson was here to talk about. He was considering simulation as a tool for modelling problems within industry. This is particularly useful when the matmematics OR uses does not give a nice tractable answer.

Over the week, Barry Nelson gave us lectures on various aspects of simulation, both as a theoretical subject and how to use simulation within research. The aspects included experimental design, a brief look at pseudo-random number generation, how input error has a effect on output error and simulation optimisation. I would like to talk about a couple of these things in this post.

One subject I found interesting was the idea of error in a simulation experiment. Prof. Nelson was very insistent that any results that were obtained by simulation must be accompanied by some measure of uncertainty. This is because the simulations used are stochastic processes, so any particular output value is dependent on the particular number generation used in any run of the simulation. The output error can be quantified using normal statistical techniques. However, this is assuming that the data from which the simulation is built is an exact representation of the real world. In actual fact, as in all statistics, the data can only give an estimate for the inputs that the simulation requires. A fair (and important) question is then, how does input uncertainty effect output uncertainty?

One way of estimating the input uncertainty is the Random Effects Model. This involves taking $b$ bootstrap samples from the data and for each sample $i$ fitting a distribution $\hat{F}_i$. After that, use $\hat{F}_i$ as the input for $n$ replications from the simulation to get the outputs $Y_{ij}$ from the $j$th replication from the $i$th sample. By using the variance of the means from each sample to the overall mean, $\sigma_T^2$, and the variance of the sample outputs from the sample mean, $\sigma_S^2$, one can estimate the input variance $$\sigma_I^2 = \frac{\sigma_T^2-\sigma_S^2}{n}.$$ In some circumstances, the input error can be as significant as the simulation error. However, how can one interpret this when $\sigma_I^2$ is negative? There are other methods, and this is one of the research areas of Lucy Morgan, who is a STOR-i student working with Barry Nelson.

Another topic Prof. Nelson spoke about was Simulation Optimisation. This is a useful tool for when the objective function, $\theta(\mathbf{x})$, or constraint of an optimisation problem need to be estimated for each scenario. The estimator depends on the run length, number of replications and the pseudo-random numbers used in the simulation. Unless each scenario can be tested as many times as necessary to get $\theta(\mathbf{x})$ to a certain confidence level, the same problem that occurs for multi-armed bandit problem occurs. I discussed exploration versus exploitation in the "Why Not Let Bandits in to Help in Clinical Trials?" blog.

This is a "hot" (Nelson's words) topic in research with many different lines of approach being tried. One he described was called the Gradient Search. The idea is to use the gradient of $\theta(\mathbf{x})$ to move from the current scenario $\mathbf{x}$ to a better one. As we only have an estimate for $\theta(\mathbf{x})$, this isn't that simple. One method, known as Infinitesimal Perturbation Analysis (IPA), really struck me. It only holds in cases where $\theta(\mathbf{x})=E[Y]$, where $Y$ is the output of the simulation and under the condition that $$\frac{\partial E[Y(\mathbf{x})]}{\partial x_i}=E\left[\frac{\partial Y(\mathbf{x})}{\partial x_i}\right]$$ This is often difficult to prove for a particular simulation, but gives excellent results when it holds. Other results are normally more practical and have easier conditions to meet, but this has a wonderful mathematical cleanliness.

There were a number of other very interesting topics we were introduced to this week, and it was a brilliant opportunity to have Prof. Nelson to introduce us to them.