Stochastic program

From Glossary

Jump to: navigation, search

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:

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:

\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

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:

\max E[c]x + E[F(x; p)]: Ax=b, x \ge 0,


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:

\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.

Personal tools