 # Stochastic program

It is written in the form of a mathematical program extended to a parameter space whose values are random variables (generally with known distribution function). This is converted to a standard form by forming a certainty equivalent.

• Here are some certainty equivalents:
• Average value. Replace all random variables with their means.
• Chance constraint. Given a stochastic program with a random variable, p, in its constraint: $LaTeX: \textstyle g(x; p) \le 0,$ a certainty equivalent is to replace this with the constraint, $LaTeX: \textstyle P \left [g(x; p) \le 0 \right ] \ge a,$ where $LaTeX: P[]$ is a (known) probability function on the range of $LaTeX: g$, and $LaTeX: a$ is some acceptance level ( $LaTeX: a=1$ means the constraint must hold for all values of $LaTeX: p$, except on a set of measure zero). Some models separate constraints with several levels: $LaTeX: P \left [g_i(x; p) \le 0 \mbox{ for all } i \in I_k] \ge a_k \mbox{ for } k=1, \dots ,K.$

The case of one chance constraint with the only random variable being the right-hand side is particularly simple. Suppose $LaTeX: F$ is the cumulative distribution function of $LaTeX: b$ for the chance constraint $LaTeX: \textstyle P[g(x) \le b] \ge a.$ If $LaTeX: b$ is a continuous random variable and $LaTeX: F$ is continuous and strictly increasing, the chance constraint is equivalent to $LaTeX: \textstyle g(x) \le F^{-1}(1-a)$ (where $LaTeX: F^{-1}$ is the inverse function of $LaTeX: F$). In particular, if $LaTeX: \textstyle g(x) = Ax,$ the program remains linear.
• Recourse model. This assumes decisions are made over time where the effect of an early decision can be compensated by later decisions. The objective is to optimize the expected value. The 2-stage model has the form: $LaTeX: \max f_1(x_1; p_1) + f_2(x_2; p_2): x_1 \in X_1, x_2 \in X_2, g(x_1; p_1) + g(x_2; p_2) \le 0.$

(Sums could be replaced by other operators.) Once $LaTeX: x_1$ is implemented, $LaTeX: p_1$ becomes known and $LaTeX: x_2$ is chosen. The certainty equivalent is: $LaTeX: \max E[f_1(x1; p1) + F_2(x_1 | p_1)]: x_1 \in X_1,$ where $LaTeX: F_2(x_1 | p_1) = \sup \{E[f_2(x_2; p_2)]: x_2 \in X_2(p_2), g(x_2; p_2) \le -g(x_1; p_1)\}$

for all p2 (except on set of measure zero). (E[] denotes the expected value.) The 'Sup' is used to define $LaTeX: F_2,$ the second stage value for a particular value of $LaTeX: x_1,$ because the choice of $LaTeX: x_1$ might be infeasible. The nature of the recourse model is pessimistic: $LaTeX: x$ must be chosen such that the original constraints hold no matter what the values of the random variables. With a finite number of possibilities, this means a system of constraints for each possible realization of $LaTeX: \textstyle p=(p_1, p_2).$ This extends recursively to a k-stage model. The linear 2-stage recourse model has the form: $LaTeX: \max E[c]x + E[F(x; p)]: Ax=b, x \ge 0,$

where $LaTeX: F(x; p) = \max d(p)y: W(p)y = w(p) - T(p)x, y \ge 0.$

Here the second stage variable is denoted $LaTeX: y;$ it is determined after $LaTeX: x$ has been set and the random variable $LaTeX: p$ has been realized. The LP data depend on $LaTeX: p$ as functions, $LaTeX: d(p), W(p), w(p)$ and $LaTeX: T(p).$ The fixed recourse model has $LaTeX: W(p)=W.$ The complete recourse model assumes it fixed and $LaTeX: \textstyle \{Wy: y \ge 0\}$ is all of $LaTeX: \mathbb{R}^m$ (where $LaTeX: m$ = number of rows of $LaTeX: W$). This means that no matter what value of $LaTeX: x$ is chosen for the first stage, there is feasible recourse $LaTeX: (y).$ This is simple recourse if $LaTeX: \textstyle W=[I -I],$ so we can think of y as having two parts: $LaTeX: y^+$ and $LaTeX: y^-.$ The second stage LP simplifies to the following: $LaTeX: \max d^-(p) y^+ + d^-(p) y^- : y^+, y^- \ge 0, y^+ - y^- = w(p) - T(p)x.$

Also see robust optimization. The certainty equivalent depends upon the underlying decision process. If it is adaptive, the recourse model applies (but RO might be more practical). The chance constraint model represents a notion of an allowed frequency of violations, as in environmental control models.