Page 123 -

problem for a partial differential equation, the hold for all values of p, except on a set of mea-
interaction of the basis functions will be local in sure zero). Some models separate constraints
the sense that with several levels:

meas(supp b ∩supp b ) = 0 ⇒ a(b ,b ) = 0. P [g (x; p) ≤ 0 for all i in I ] ≥ a k
k
i
j
i
i
j
for k = 1, ..., K.
Thisleadstoconsiderablesparsityofthestiffness
matrix, which is key to the efficiency of finite The case of one chance constraint with the
element schemes. only random variable being the right-hand side
is particularly simple. Suppose F is the cumu-
stochastic computation Let the set of sym- lative distribution function of b for the chance
bols of the computation be K, and the probability constraint P [g(x) ≤ b] ≥ a.If b is a continuous
that a particular symbol σ exists be P (σ ). Then random variable and F is continuous and strictly
e
i
i
a computation C is executed stochastically if for increasing, the chance constraint is equivalent to
−1
−1
at least one σ ∈ K, P (σ ) ≤ 1; or if at least one g(x) ≤ F (1 − a) (where F is the inverse
i
e
i
c ∈ C is a stochastic function. function of F). In particular, if g(x) = Ax, the
i
Comment: This definition explicitly posits program remains linear.
that determinism is a property of a computation (3) Recourse model. This assumes decisions
are made over time where the effect of an early
and stochasticity that of its execution. An exam-
decision can be compensated by later decisions.
ple of the latter is when at least one σ has a half-
i
life which is not orders of magnitude greater than The objective is to optimize the expected value.
The two-stage model has the form
that of t , the time needed to execute the com-
C
putation, so that one cannot rely upon σ to per- Maxf (x ; p ) + f (x ; p ) :
i
sist throughout the lifetime of the computation 1 1 1 2 2 2
(including the step of actually detecting it). See x ∈ X ,x ∈ X ,g(x ; p ) + g(x ; p ) ≤ 0.
1 1 2 2 1 1 2 2
deterministic and nondeterministic computation.
(Sums could be replaced by other operators.)
Once x is implemented, p becomes known and
1
1
stochastic matrix A nonnegative matrix
x is chosen. The certainty equivalent is
2
whose row sums are each 1. (A column stochas-
tic matrix is one whose column sums are 1.) This Max E[f (x ; p ) + F (x |p )]: x ∈ X ,
1
1
1
1
2
1
1
1
arises in dynamic programs whose state transi- where
tion is described by a stochastic matrix contain-
F (x |p ) = Sup{E[f (x ; p )]:
2
2
1
2
1
2
ing the probabilities of each transition.
x ∈ X (p ), g(x ; p ) ≤−g(x ; p )}
2
1
2
2
1
2
2
stochastic program A program written in
for all p (except on set of measure zero).
2
the form of a mathematical program extended
(E[ ] denotes the expected value.) The “Sup” is
to a parameter space whose values are random
used to define F , the second stage value for a
2
variables (generally with a known distribution
particular value of x , because the choice of x 1
1
function). This is converted to a standard form
might be infeasible. The nature of the recourse
by forming a certainty equivalent. Here are some
model is pessimistic: x must be chosen such that
certainty equivalents:
the original constraints hold no matter what the
(1) Average value. Replace all random vari-
values of the random variables. With a finite
ables with their means.
number of possibilities, this means a system of
(2) Chance constraint. Given a stochastic
constraints for each possible realization of p =
program with a random variable, p, in its con-
(p ,p ). This sextends recursively to a k-stage
1
2
straint: g(x; p) ≤ 0, a certainty equivalent is
model.
to replace this with the constraint, P[g(x; p) ≤
The linear two-stage recourse model has the
0] ≥ a, where P[ ] is a (known) probability
form:
function on the range of g, and a is some accep-
tance level (a = 1 means the constraint must max E[c]x + E[F(x; p)]:
© 2003 by CRC Press LLC
© 2003 by CRC Press LLC