Editing Stochastic programming (section)

====Consistency of SAA estimators====

Suppose the feasible set <math>X</math> of the SAA problem is fixed, i.e., it is independent of the sample. Let <math>\vartheta^*</math> and <math>S^*</math> be the optimal value and the set of optimal solutions, respectively, of the true problem and let <math>\hat{\vartheta}_N</math> and <math>\hat{S}_N</math> be the optimal value and the set of optimal solutions, respectively, of the SAA problem.

# Let <math>g: X \rightarrow \mathbb{R}</math> and <math>\hat{g}_N: X \rightarrow \mathbb{R}</math> be a sequence of (deterministic) real valued functions. The following two properties are equivalent:
#* for any <math>\overline{x}\in X</math> and any sequence <math>\{x_N\}\subset X</math> converging to <math>\overline{x}</math> it follows that <math>\hat{g}_N(x_N)</math> converges to <math>g(\overline{x})</math>
#* the function <math>g(\cdot)</math> is continuous on <math>X</math> and <math>\hat{g}_N(\cdot)</math> converges to <math>g(\cdot)</math> uniformly on any compact subset of <math>X</math>
# If the objective of the SAA problem <math>\hat{g}_N(x)</math> converges to the true problem's objective <math>g(x)</math> with probability 1, as <math>N \rightarrow \infty</math>, uniformly on the feasible set <math>X</math>. Then <math>\hat{\vartheta}_N</math> converges to <math>\vartheta^*</math> with probability 1 as <math>N \rightarrow \infty</math>.
# Suppose that there exists a compact set <math>C \subset \mathbb{R}^n</math> such that
#* the set <math>S</math> of optimal solutions of the true problem is nonempty and is contained in <math>C</math>
#* the function <math>g(x)</math> is finite valued and continuous on <math>C</math>
#* the sequence of functions <math>\hat{g}_N(x)</math> converges to <math>g(x)</math> with probability 1, as <math>N \rightarrow \infty</math>, uniformly in <math>x\in C</math>
#* for <math>N</math> large enough the set <math>\hat{S}_N</math> is nonempty and <math>\hat{S}_N \subset C</math> with probability 1
:: then <math>\hat{\vartheta}_N \rightarrow \vartheta^*</math> and <math>\mathbb{D}(S^*,\hat{S}_N)\rightarrow 0 </math> with probability 1 as <math>N\rightarrow \infty </math>. Note that <math>\mathbb{D}(A,B) </math> denotes the ''deviation of set <math>A</math> from set <math>B</math>'', defined as

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;"><math>
\mathbb{D}(A,B) := \sup_{x\in A} \{ \inf_{x' \in B} \|x-x'\| \}
</math></div>

In some situations the feasible set <math>X</math> of the SAA problem is estimated, then the corresponding SAA problem takes the form

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;"><math>
\min_{x\in X_N} \hat{g}_N(x)
</math></div>

where <math>X_N</math> is a subset of <math>\mathbb{R}^n</math> depending on the sample and therefore is random. Nevertheless, consistency results for SAA estimators can still be derived under some additional assumptions:
# Suppose that there exists a compact set <math>C \subset \mathbb{R}^n</math> such that
#* the set <math>S</math> of optimal solutions of the true problem is nonempty and is contained in <math>C</math>
#* the function <math>g(x)</math> is finite valued and continuous on <math>C</math>
#* the sequence of functions <math>\hat{g}_N(x)</math> converges to <math>g(x)</math> with probability 1, as <math>N \rightarrow \infty</math>, uniformly in <math>x\in C</math>
#* for <math>N</math> large enough the set <math>\hat{S}_N</math> is nonempty and <math>\hat{S}_N \subset C</math> with probability 1
#* if <math> x_N \in X_N</math> and <math> x_N </math> converges with probability 1 to a point <math> x</math>, then <math> x \in X</math>
#* for some point <math> x \in S^*</math> there exists a sequence <math> x_N \in X_N</math> such that <math> x_N \rightarrow x</math> with probability 1.
:: then <math>\hat{\vartheta}_N \rightarrow \vartheta^*</math> and <math>\mathbb{D}(S^*,\hat{S}_N)\rightarrow 0 </math> with probability 1 as <math>N\rightarrow \infty </math>.