Editing Stochastic programming (section)

====Monte Carlo sampling and Sample Average Approximation (SAA) Method====

A common approach to reduce the scenario set to a manageable size is by using Monte Carlo simulation. Suppose the total number of scenarios is very large or even infinite. Suppose further that we can generate a sample <math>\xi^1,\xi^2,\dots,\xi^N</math> of <math>N</math> realizations of the random vector <math>\xi</math>. Usually the sample is assumed to be [[independent and identically distributed]] (i.i.d sample). Given a sample, the expectation function <math>q(x)=E[Q(x,\xi)]</math> is approximated by the sample average

<math>
\hat{q}_N(x) = \frac{1}{N} \sum_{j=1}^N Q(x,\xi^j)
</math>

and consequently the first-stage problem is given by

<math>
\begin{array}{rlrrr}
\hat{g}_N(x)=&\min\limits_{x\in \mathbb{R}^n}   & c^T x + \frac{1}{N} \sum_{j=1}^N Q(x,\xi^j)    &   \\
&\text{subject to} & Ax    &=&    b \\
&		    & x     &\geq& 0
\end{array}
</math>

This formulation is known as the ''Sample Average Approximation'' method. The SAA problem is a function of the considered sample and in that sense is random. For a given sample <math>\xi^1,\xi^2,\dots,\xi^N</math> the SAA problem is of the same form as a two-stage stochastic linear programming problem with the scenarios <math>\xi^j</math>., <math>j=1,\dots,N</math>, each taken with the same probability <math>p_j=\frac{1}{N}</math>.