## Optimisation and Error in Simul?ation

### 22^{nd} 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.