Birge J.R., Louveaux F. Introduction to Stochastic Programming

Подождите немного. Документ загружается.

154 3 Basic Properties and Theory

periods as w

t, j

= x

t−j

for j = 0,...,L

max

,where L

max

= max

and x

t−j

follows

the notation in Section 1.3, and re-label the current available capacity at time t as

t,L

max

. With these deﬁnitions, we deﬁne A

= I

n(L

max

+2)×n(L

max

+2)

,an n(L

max

2)×n(L

max

+2) identity matrix and let h

=[(x

−1

)

,(x

−2

)

,...,(x

−L

max

)

1×2n

]

where 0

1×2n

indicates a 1 ×2n matrix of zeroes, as the initial conditions for the

problem where x

−j

is interpreted as capacity installed j periods before the ini-

tial period (which then replaces the information in the remaining existing capacity

vector g

used in Section 1.3). We can then deﬁne, for t = 1,...,H −1,



−I

max

×nL

max

n×n

max

×nL

max

n×n

−I

n×n



; (4.7)



−

∑

i=1

∑

n( j−1)+i

n×2n

m×nL

max

n×2n



; (4.8)

and, for t = 2,...,H ,



max

×n

max

×nL

max

×n

−I

n×n

∑

i=1

(n−1)L

n×n



; (4.9)



∑

i=1

∑

j= 1

n( j−1)+i

n×n

∑

j= 1

∑

i=1

n(i−1)+ j

n×n



; (4.10)

= 0

n(L

max

+1)×1

,and d

(

)=[d

,...,d

1×n

]

,where d

is deﬁned as in Sec-

tion 1.3.

Notice that (3) in the deﬁnition implies that detailed level variables, correspond-

ing to the capacity usage in each period in the capacity expansion model, have no

direct effect on future constraints. This is the fundamental advantage of block sepa-

rability.

With block separable recourse, we may rewrite Q

t−1

(

)) as the sum of

two quantities, Q

t−1

(

))+ Q

t−1

(

)) , where we need not include the

t−1

terms in x

t−1

(

)) = minr

(

)+Q

t+1

)

s. t. W

(

)=b

(

) −R

t−1

(

t−1

(

) ≥ 0 ,

(4.11)

and

t−1

(

)) = minq

(

)

s. t. T

(

)=d

(

) −S

t−1

(

t−1

(

) ≥ 0 .

(4.12)

The great advantage of block separability is that we need not consider nesting among

the detailed level decisions. In this way, the w variables can all be pulled together

into a ﬁrst stage of aggregate level decisions. The second stage is then composed of

3.4 Multistage Stochastic Programs with Recourse 155

the detailed level decisions. Note that if the b

and R

are known, as they are in the

model in Section 1.3, then the block separable problem is equivalent to a similarly

sized two-stage stochastic linear program.

Separability is indeed a very useful property for stochastic programs. Computa-

tional methods should try to exploit it whenever it is inherent in the problem because

it may reduce work by orders of magnitude. We will also see in Chapter 10 that

separability can be added to a problem (with some error that can be bounded). This

approach opens many possible applications with large numbers of random variables.

Another modeling approach that may have some computational advantage ap-

pears in Grinold [1976]. This approach extends from analyses of stochastic pro-

grams as examples of a Markov decision process. He assumes that

belongs to

some ﬁnite set 1,...,k

, that the probabilities are determined by p

= P{

t+1

j |

= i} for all t ,andthat T

= T

(

t+1

) . In this framework, he can obtain

an approximation that again obtains a form of separability of future decisions from

previous outcomes. We discuss more approximation approaches for multiple stages

in Chapter 10.

Exercises

1. State a set of optimality conditions analogous to those in Theorem 9 for x

t∗

(

)

to be an optimal solution in (4.3).

2. Assume that the model in (4.1) has relatively complete recourse. In this case,

ﬁnd an expression for

∂

t+1

) .

3. Give the full set of optimality conditions that are satisﬁed for an optimal solution

t∗

(

) for t = 1,...,H for the ﬁnancial planning example in Section 1.2 and

verify their satisfaction for the solution corresponding to the data in (1.2.1).

4. Emergency vehicle location: Suppose a multistage version of the model in Sec-

tion 2.6, where a city wishes to determine the allocations of V emergency vehi-

cles to each of n stations at times t = 1,...,H . Each vehicle can serve a single

call in any period, where calls are random and can occur at any of m locations

according with d

(

) corresponding to the random number of calls in location

j in period t . The cost of responding to a call at location j with a vehicle from

station i is q

and any calls in location j that cannot be served by the city’s

vehicles are served by an outside vendor at a cost ¯q

(regardless of the number

of calls). The initial number of vehicles at each station i is given by h

.Ini-

tially and at the end of each period, vehicles may be move from any station i to

any other station j at a cost r

(a) Give a multistage stochastic linear programming formulation for this model

(assuming V is sufﬁciently large that the discrete decision variables may

be adequately approximated with a continuous solution).

156 3 Basic Properties and Theory

(b) Show that this model satisﬁes the block-separable recourse conditions by

giving the corresponding decision vectors (w

(

),y

(

)) and constraint

parameters, A

, B

, R

(

) , S

(

) , b

(

) ,and d

(

) .

3.5 Stochastic Nonlinear Programs with Recourse

In this section, we generalize the results from the previous sections to problems with

nonlinear functions, starting with two-stage problems. The results extend directly

so the treatment here will be brief. The basic types of results we would like to

obtain concern the structure of the feasible region, the optimal value function, and

optimality conditions. As a note of caution, some of the results in this section refer

to concepts from measure theory.

We begin with a deﬁnition of the two-stage stochastic nonlinear program with

recourse.This problem has the form:

infz = f

(x)+Q(x)

s. t. g

(x) ≤ 0, i = 1,..., ¯m

(x)=0 , i = ¯m

+ 1,...,m

(5.1)

where Q(x)=E

[Q(x,

)] and

Q(x,

)=inf f

(x,y(

)

(x,y(

) ≤ 0 ,i = 1,..., ¯m

(x,y(

)=0 ,i = ¯m

+ 1,...,m

, (5.2)

where all functions f

and g

for all i are continuous, and f

(·,·,

) and

(·,·,

) are also continuous for any ﬁxed

and are measurable in

for any

ﬁxed ﬁrst argument and for any i . Given this assumption, Q(x,

) is measurable

(Exercise 1) and hence Q(x) is well-deﬁned.

We make the following deﬁnitions consistent with Section 3.1.

≡{x |g

(x) ≤ 0 , i = 1,..., ¯m

; g

(x)=0 , i = ¯m

+ 1,...,m

} ,

(

)={x |∃y(

) | g

(xy(

) ≤ 0 , i = 1,..., ¯m

;

(x,y(

)=0 , i = ¯m

+ 1,...,m

} ,

and

= {x | Q(x) < ∞} .

We have not forced ﬁxed recourse in Problem 5.1 because the second-period con-

straint functions may depend on

and on y(

) . For linear programs, we assumed

3.5 Stochastic Nonlinear Programs with Recourse 157

ﬁxed recourse so we could describe the feasible region in terms of intersections of

feasible regions for each random outcome. We could also follow this approach here

but the conditions for this result depend directly on the form of the objective and

constraint functions. We explore these possibilities in Exercise 1 but we continue

here with the more general case.

We make additional assumptions to allow results along the lines of the previ-

ous section. These conditions ensure regularity for the application of necessary and

sufﬁcient optimality conditions.

1. Convexity. The function f

is convex on ℜ

, g

is convex on ℜ

for i =

1,..., ¯m

, g

is afﬁne on ℜ

for i = ¯m

+ 1,...,m

, f

(·,·,

) is convex

and ﬁnite on ℜ

for all

∈

, g

(·,·,

) is convex on ℜ

for all

i = 1,..., ¯m

and for all

∈

, g

(·,

) is afﬁne on ℜ

for i = ¯m

1,...,m

and for all

∈

2. Slater condition.If Q(x) < ∞ , for almost all

∈

, there exists some y(

)

such that g

(x,y(

) < 0fori = 1,..., ¯m

and g

(x,y(

)=0fori =

¯m

+ 1,...,m

The main purpose of these assumptions is to ensure that the resulting deterministic

equivalent nonlinear program is also convex. The following theorem gives condi-

tions for convexity of the recourse function. It follows directly from the deﬁnitions.

Theorem 34. Under Assumptions 1 and 2, the recourse function Q(x,

) is a con-

vex function of x for all

∈

Proof:Lety

solve the optimization problem in (5.2)for x

and let y

solve

the corresponding problem for x

. Consider x =

+(1 −

. In this case,

(

+(1 −

) ≤

)+(1 −

) ≤

0 for each i = 1,..., ¯m

.Wealsohavethat g

(

+(1 −

λλ

)+(1 −

)=0 for each i = ¯m

+ 1,...,m

So, Q(

+(1 −

) ≤ f

(

+(1 −

)

≤

)+(1 −

) f

Q(x

)+(1 −

)Q(x

) ,givingthe

result.

We can also obtain continuity of the recourse function if we assume the recourse

feasible region is bounded.

Theorem 35. If the recourse feasible region is bounded for any x ∈ ℜ

, then the

function Q(x,

) is lower semicontinuous in x for all

∈

(i.e., Q(x,

) is a

closed convex function).

Proof: Proving lower semicontinuity is equivalent (see, e.g., Rockafellar [1969])

to showing that

liminf

x→¯x

Q(x,

) ≥ Q( ¯x,

)

for any ¯x ∈ℜ

, x → ¯x ,and

∈

. Suppose a sequence x

→ ¯x . We can assume

that Q(x

) < ∞ for all

because there is either a subsequence of {x

} that is

ﬁnite valued in Q or the result holds trivially.

158 3 Basic Properties and Theory

We therefore have g

(

) ≤0fori = 1,..., ¯m

and g

(

)

= 0fori = ¯m

+ 1,...,m

and for some y

(

) . Hence, by continuity of each

of these functions and the boundedness assumption, the {y

(

)} sequence must

have some limit point, e.g., ¯y(

) . Thus, g

( ¯x, ¯y(

) ≤ 0fori = 1,..., ¯m

and g

( ¯x, ¯y(

)=0fori = ¯m

+ 1,...,m

.So, ¯x is feasible and Q( ¯x,

) ≤

( ¯x, ¯y(

)=lim

(

)=lim

Q(x

) where

is a sub-

sequence such that y

(

) → ¯y(

) .

Because integration is a linear operation on the convex function Q , we obtain

the following corollaries.

Corollary 36. The expected recourse function Q(x) is a convex function in x .

Corollary 37. The feasibility set K

= {x | Q(x) < ∞} is closed and convex.

Corollary 38. Under the conditions in Theorem 35, Q is a lower semi-continuous

function on x .

This corollary then leads directly to the following attainability result.

Theorem 39. Suppose the conditions in Theorem 35, K

is bounded, f

contin-

uous, g

and g

continuous for each i , and K

∩K

= /0 .Then(5.1) has a ﬁnite

optimal solution and the inﬁmum is attained.

Proof: From Corollary 38, Q is continuous on its effective domain. The continuity

of g

also implies that K

is closed so the optimization is for a continuous, convex

function over the nonempty, compact region K

∩K

Other results may follow for speciﬁc cases from Fenchel’s duality theorem (see

Rockafellar [1969]). In some cases, it may be difﬁcult to decompose the feasibility

set K

into



(

) . It is possible if f

is always dominated by some integrable

function in

for any y(

) feasible in the recourse problem for all x . This might

be veriﬁable if, for example, the feasible recourse region is bounded for all x ∈

. Another possibility is for special functions such as the quadratic function in

Exercise 2.

We can now proceed to state optimality conditions for (5.1) as in Theorem 9.

As a reminder from Section 2.10, in the following, we use ri to indicate relative

interior.

Theorem 40. If there exists x such that x ∈ri(dom( f

(x)) and x ∈ri(dom(Q(x)))

and g

(x) < 0 for all i = 1,..., ¯m

and g

(x)=0 for all i = ¯m

+ 1,...,m

,then

∗

is optimal in 5.1 if and only if x

∗

∈ K

and there exists

∗

≥ 0 ,i= 1,..., ¯m

∗

,i= ¯m

+ 1,...,m

, such that

∗

)=0 ,i= 1,..., ¯m

, and

0 ∈

∂

∗

∂

Q(x

∗

∑

i=1

∗

∂

∗

) . (5.3)

3.5 Stochastic Nonlinear Programs with Recourse 159

Proof: This result is a direct extension of the general optimality conditions in non-

linear programming (see, e.g., Rockafellar [1969, Theorem 28.3]).

For most practical purposes, we need to obtain some decomposition of

∂

Q(x)

into subgradients of the Q(x,

) . The same argument as in Theorem 11 applies here

so that

∂

Q(x)=E

[

∂

Q(x,

)] + N(K

,x) (5.4)

for all x ∈ K . Moreover, if we have relatively complete recourse, we can remove

the normal cone term in (5.4).

We can also develop optimality conditions that apply to the problem with ex-

plicit constraints on nonanticipativity as in Section 3.1. In this case, Problem (5.1)

becomes

inf

(x(

),y(

))∈X



( f

(x(

)) + f

(x(

),y(

))

)

s. t. g

(x(

)) ≤ 0 , a.s., i = 1,..., ¯m

(x(

)) = 0 , a.s., i = ¯m

+ 1,...,m

(x(

)) −x(

)=0 , a.s.,

(x(

),y(

) ≤ 0 , a.s., i = 1,..., ¯m

(x(

),y(

)=0 , a.s., i = ¯m

+ 1,...,m

),y(

) ≥ 0 , a.s.

(5.5)

The optimality results appear in the following theorem which is proven similarly to

Theorem 13.

Theorem 41. Assume that (5.5) with X = L

∞

(

,B,

;ℜ

) is feasible, has

a bounded optimal value, satisﬁes relatively complete recourse, and that a feasi-

ble solution (x

∗

(

),y

∗

(

)) is at a point satisfying the linear independence con-

dition that any vector in

∂

∗

(

),y

∗

(

) cannot be written as a combina-

tion of some strict subset of representative vectors from

∂

∗

(

),y

∗

(

) for

i such that g

∗

(

),y

∗

(

)=0 ; then, (x

∗

(

),y

∗

(

)) is optimal in (5.5)

if and only if there exist integrable functions on

, (

∗

(

∗

(

∗

(

)) ,

(

x∗

(

y∗

(

)) ∈

∂

∗

(

),y

∗

(

) , and (

x∗

y∗

) ∈

∂

∗

(

),y

∗

(

)

for i = 1,...,m

such that, for almost all

∗

(

) ∈

∂

∗

(

)) +

x∗

(

)

∑

i=1

∗

(

)

∂

∗

(

)) +

∑

i=1

∗

(

)

x∗

(

) , (5.6)

∗

(

) ≥ 0 ,

∗

(

∗

(

)) = 0 , i = 1,..., ¯m

, (5.7)

0 =

y∗

(

∑

i=1

∗

(

)

y∗

(

) , (5.8)

160 3 Basic Properties and Theory

∗

(

) ≥ 0 ,

∗

(

∗

(

),y

∗

(

)=0 , i = 1,..., ¯m

, (5.9)

and

[

∗

(

)] = 0 . (5.10)

Again the

functions represent the value of information in each of the scenarios

under

. These results can also be generalized to allow for nonseparability between

the ﬁrst and second stage but for our computational descriptions, this is generally

not necessary.

For multiple stages, we can deﬁne models analogous to the linear version in

Section 5.1. A general representation can be obtained by including the constraint

information except for nonanticipativity into the objective so that the objective

takes on an inﬁnite value whenever a constraint is violated. To distinguish in-

formation from period to period, we associate a ﬁltration with the data process

as F := {

}

∞

t=1

,where

(

) is the

-ﬁeld of the history process

:= {

,...,

},andthe

satisfy {0,

}⊂

⊂ ···⊂

. Nonanticipativity

of the decision process at time t implies that decisions must only depend on the

data up to time t , i.e., x

must be

–measurable. An alternative characteriza-

tion of this nonanticipative property is that x

= E{x

} a.s., t = 0,... ,where

E{· |

} is conditional expectation with respect to the

-ﬁeld

.Usingthepro-

jection operator

: z →

z := E{z |

}, t = 0,... , this is equivalent to

(I −

= 0 , t = 0,... (5.11)

In this framework, the general multistage stochastic programming model is to ﬁnd

inf

x∈N

∑

t=0

(

),x

t+1

(

)) , (5.12)

where “ E ” is expectation with respect to

. Using our random variable boldface

notation, expression (5.12) then becomes

inf

x∈N

∑

t=0

t+1

) , (5.13)

with objective z(x) := E

∑

t=0

t+1

) .

We can develop optimality conditions for this model that also allow H →∞ .The

conditions are basically the same as in previous sections (in terms of some assump-

tion about relatively complete recourse and some regularity condition), but we need

some additional assumptions to control multipliers at H = ∞ . Detailed descrip-

tions of these conditions and other issues appear in the papers by Rockafellar and

Wets [1976a,1976b], Dempster [1988], Fl˚am [1985,1986], and Birge and Dempster

[1992].

These basic results for the general model in (5.13) can be extended to results

with constraints in the same way as necessary conditions in the previous sections

3.5 Stochastic Nonlinear Programs with Recourse 161

(Exercise 5). The only requirement is to describe the subdifferentials of f

in terms

of an objective and constraint functions (Exercise 6). The optimality conditions that

extend Theorem 41 to multiple stages can then be used to decompose the multistage

problem into individual period t problems. In this way, optimization may be applied

at each period provided suitable multipliers are available. This property is the basis

for the Lagrangian and progressive hedging algorithms described in Chapter 5.

Exercises

1. Show that the assumptions made when deﬁning (5.1)and(5.2) imply that

Q(x,

) is a measurable function of

for all x .(Hint:Find {

|Q(x,

) ≤

}

for any

using a countable covering of ℜ

2. Suppose f

is a convex, quadratic function on ℜ

for each

∈

and

the constraints g

and h

are afﬁne on ℜ

for all i = 1,..., ¯m

and j =

1,...,m

− ¯m

. What conditions on

(

) can guarantee that K



(

) ?

3. Construct an example in which the recourse function Q(x,

) is not lower semi-

continuous. (Hint: Try to make the only feasible recourse action tend to ∞ while

the ﬁrst-period action tends to some ﬁnite value.)

4. Show that conditions in (5.6)–(5.10) are sufﬁcient to obtain optimality in (5.5).

5. State and prove a set of optimality conditions analogous to Theorem 35 for the

multistage model in (5.13).

6. Suppose that constraints are explicitly represented by g

t+1

) ≤ 0in(4.11)

instead of being incorporated into f

. Interpret the optimality conditions from

Exercise 5 above in terms of the g

functions.

Chapter 4

The Value of Information and the Stochastic

Solution

Stochastic programs have the reputation of being computationally difﬁcult to solve.

Many people faced with real-world problems are naturally inclined to solve simpler

versions. Frequently used simpler versions are, for example, to solve the determinis-

tic program obtained by replacing all random variables by their expected values or to

solve several deterministic programs, each corresponding to one particular scenario,

and then to combine these different solutions by some heuristic rule.

A natural question is whether these approaches can sometimes be nearly optimal

or whether they are totally inaccurate. The theoretical answer to this is given by two

concepts: the expected value of perfect information and the value of the stochastic

solution. The object of this chapter is to study these two concepts. Section 4.1 in-

troduces the expected value of perfect information. Section 4.2 gives the value of

the stochastic solution. Some basic inequalities and the relationships between these

quantities are given in Sections 4.3 and 4.4, respectively. Section 4.5 provides some

examples of these quantities. Section 4.6 presents additional bounds.

4.1 The Expected Value of Perfect Information

The expected value of perfect information ( EVPI ) measures the maximum amount

a decision maker would be ready to pay in return for complete (and accurate) in-

formation about the future. In the farmer’s problem of Chapter 1, we saw that the

farmer would greatly beneﬁt from perfect information about future weather condi-

tions, so that he could allocate his land optimally to the various crops.

The concept of EVPI was ﬁrst developed in the context of decision analysis and

can be found in a classical reference such as Raiffa and Schlaifer [1961]. In the

stochastic programming setting, we may deﬁne it as follows. Suppose uncertainty

can be modeled through a number of scenarios. Let ξ be the random variable whose

realizations correspond to the various scenarios. Deﬁne

minz(x,

)=c

x + min{q

y |Wy = h −Tx,y ≥ 0}

J.R. Birge and F. Louveaux, Introduction to Stochastic Programming, Springer Series 163

in Operations Research and Financial Engineering, DOI 10.1007/978-1-4614-0237-4

 Springer Science+Business Media, LLC 2011