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

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

114 3 Basic Properties and Theory

A special type of complete recourse offers additional computational advantages

to stochastic programming solutions. This case is the generalization of the news

vendor problem introduced in Section 3.1. It is called simple recourse.Forasim-

ple recourse problem, W =[I,−I] , y is divided correspondingly as (y

−

) ,and

q =(q

−

) . Note that, in this case, the optimal values of y

(

),y

−

(

) are de-

termined purely by the sign of h

(

) −T

i·

(

)x provided that q

+ q

−

≥ 0 with

probability one. This ﬁniteness result is in the following theorem.

Theorem 7. Suppose the two-stage stochastic program in (1.1) is feasible and has

simple recourse and that ξ has ﬁnite second moments. Then Q(x) is ﬁnite if and

only if q

+ q

−

≥ 0 with probability one.

Proof:Ifq

(

)+q

−

(

) < 0for

∈

where P(

) > 0 , then, for any

feasible x in (1.1), for all

∈

where h

(

) −T

i·

(

)x > 0, let y

(

) −T

i·

(

)x + u , y

−

(

)=u . By letting u → ∞ , Q(x,

) →−∞ . A similar

argument applies if h

(

) −T

i·

(

)x ≤0,so Q(x) is not ﬁnite.

If q

+ q

−

≥ 0 with probability one, then Q(x,

∑

i=1

(

)(h

(

) −

i·

(

)x)

+ q

−

(

)(−h

(

)+T

i·

(

)x)

) , which is ﬁnite for all

. Using Proposi-

tion 2, we obtain the result.

We, therefore, assume that q

+ q

−

≥ 0 with probability one and can write

Q(x) as

∑

i=1

(x) ,where Q

(x)=E

(x,

(

))] ,and

(x,

(

)) = q

(

)(h

(

) −T

i·

(

)x)

+ q

−

(

)(−h

(

)+T

i·

(

)x)

When q and T are ﬁxed, this characterization of Q allows its expression as a

separable function in the remaining random components h

. Often, in this case,

i·

x is substituted with

and

is substituted for Q so that Q(x)=

(

) .We

then obtain

(

∑

i=1

(

) where

(

)=E

[

(

)] and

(

−

)

+ q

−

(−h

)

. We, however, continue to use Q(x) to maintain

consistency with our previous results.

We can deﬁne the objective function even further. In this case, let h

have an

associated distribution function F

, mean value

,andlet q

= q

+ q

−

. We can

then write Q

(x) as

(x)=q

−(q

−q

i·

x))T

i·

x −q



≤T

i·

). (1.9)

Of particular importance in optimization is the subdifferential of this function,

which has the following simple form:

∂

(x)={

i·

)

|−q

+ q

−

i·

x) ≤

≤−q

+ q

i·

x)} , (1.10)

where F

−

(h)=lim

t↑h

(t) and F

(h)=lim

t↓h

(t)=F

(h) . These results can

be used to obtain speciﬁc optimality conditions. These general conditions are the

subject of the next part of this section.

3.1 Two-Stage Stochastic Linear Programs with Fixed Recourse 115

e. Optimality conditions and duality

In this subsection, we consider optimality conditions for stochastic programs. Our

goal in describing these conditions is to show the special conditions that can apply

to stochastic programs and to show how stochastic programs may differ from other

mathematical programs. In particular, we give the additional assumptions that guar-

antee necessary and sufﬁcient conditions for two-stage stochastic linear programs.

The following sections contain generalizations.

The deterministic equivalent problem in (1.2) provides the framework for opti-

mality conditions, but several questions arise.

1. When is a solution to (1.2) attainable?

2. What form do the optimality conditions take and how can they be simpliﬁed?

3. What types of dual problems can be formulated to accompany (1.2) and do they

obtain bounds on optimal values?

4. How stable is an optimal solution to (1.2) to changes in the parameters and

distributions?

This subsection brieﬂy describes answers to these questions. Further details are con-

tained in Kall [1976], Wets [1974, 1990], and Dempster [1980]. Our aim is to give

only the basic results that may be useful in formulating, solving, and analyzing

practical stochastic programs.

From the previous section, supposing that ξ has ﬁnite second moments, we

know that Q is Lipschitzian. We can then apply a direct subgradient result. A ques-

tion is, however, whether the solution of (1.2) can indeed be obtained, i.e., whether

the optimal objective value is ﬁnite and attained by some value of x .

To see that this question is indeed relevant, consider the following example. Find

inf{E

(ξ)] | y

(ξ),y

−

(ξ) ≥ 0,x + y

(ξ) −y

−

(ξ)=ξ, a.s.}, (1.11)

where ξ is, for example, negative exponentially distributed on [0,∞) . For any ﬁnite

value of x ,(1.11) has a positive value, but the inﬁmum over x is zero.

The following theorem gives some sufﬁcient conditions to guarantee that a so-

lution to (1.2) exists. In the following, we use rc to denote the recession cone,

{v | u +

v ∈ S ,forall

≥ 0andu ∈ S} when applied to a set, S , and the reces-

sion value, sup

x∈dom f

( f (x + v) − f (x)) when applied to a proper convex function,

f .

Theorem 8. Suppose that the random elements ξ have ﬁnite second moments and

one of the following:

(a) the feasible region K is bounded; or

(b) the recourse function Q is eventually linear in all recession directions of K ,

i.e., Q(x +

v)=Q(x+

v)+(

−

)rcQ(v) for some

≥0 (dependent on

x),all

≥

, and some constant recession value, rcQ(v) , for all v such that

x +

v ∈ K for all x ∈ K and

≥ 0 .

116 3 Basic Properties and Theory

Then, if problem (1.2) has a ﬁnite optimal value, it is attained for some x ∈ ℜ

Proof: The proof given (a) follows immediately by noting that the objective is

convex and ﬁnite on K , which is compact by assumption. The only possibility

for not attaining an optimum is, therefore, when the optimal value is only attained

asymptotically. By (b), along any recession direction v ,wemusthave rcQ(v) ≥0

for a ﬁnite value of Q(x +

v) . Hence, the optimal value must be attained.

As shown in Wets [1974], if T is ﬁxed and

is compact, the condition in (b)

is obtained. In the exercises, we will show that (b) may not hold if either of these

conditions is relaxed.

We now assume that an optimal solution can be attained as we would expect

in most practical situations. For optimization, we would like to describe the char-

acteristics of such points. The general deterministic equivalent form gives us the

following result in terms of Karush-Kuhn-Tucker conditions.

Theorem 9. Suppose (1.2) has a ﬁnite optimal value. A solution x

∗

∈K

, is optimal

in (1.2) if and only if there exists some

∗

∈ℜ

∗

∈ℜ

∗T

∗

= 0 , such that,

−c + A

∗

∈

∂

Q(x

∗

). (1.12)

Proof: From the optimization of a convex function over a convex region (see, for

example, Bazaraa and Shetty [1979, Theorem 3.4.3]), we have that c

x+ Q(x) has

a subgradient

at x

∗

such that

(x −x

∗

) ≥ 0forallx ∈ K

if and only if x

∗

minimizes c

x + Q(x) over K

. We can write the set, {

(x −x

∗

) ≥0forall

x ∈ K

},as {

= A

,forsome

≥ 0,

∗

= 0} . Hence, the general

optimality condition states that a nonempty intersection of {

= A

,for

some

≥ 0,

∗

= 0} and

∂

∗

+ Q(x

∗

)) = c +

∂

Q(x

∗

) is necessary and

sufﬁcient for the optimality of x

∗

This result can be combined with our previous results on simple recourse func-

tions to obtain speciﬁc conditions for that problem as follows.

Corollary 10. Suppose (1.1) has simple recourse and a ﬁnite optimal value. Then

∗

∈ K

is optimal in (1.2) corresponding to this problem if and only if there exists

some

∗

∈ ℜ

∗

∈ ℜ

∗T

∗

= 0 ,

∗

such that −(q

−q

−

i·

∗

)) ≤

∗

≤−(q

−q

i·

∗

)) and

−c + A

∗

−(

∗

)

T = 0 . (1.13)

Proof: This is a direct application of (1.10)andTheorem9.

Inclusion (1.12) suggests that a subgradient method or other nondifferentiable

optimization procedure may be used to solve (1.2). While this is true, we note that

ﬁnite realizations of the random vector lead to equivalent linear programs (although

of large scale), while absolutely continuous distributions lead to a differentiable

recourse function Q .

3.1 Two-Stage Stochastic Linear Programs with Fixed Recourse 117

Obviously if Q is differentiable, we can replace

∂

Q(x

∗

) with ∇Q(x

∗

) to ob-

tain:

c + ∇Q(x

∗

)=A

∗

(1.14)

in place of (1.12). Possible algorithms based on convex minimization subject to

linear constraints are then admissible.

The main practical possibilities for solutions of (1.2) then appear as examples

of either large-scale linear programming or smooth nonlinear optimization. The

chief difﬁculty is, however, in characterizing

∂

Q because even evaluating this

function is difﬁcult. This evaluation is, however, decomposable into subgradients

of the recourse function for each realization of ξ , which form the subdifferential

set

∂

Q(x,

(

)) , where we interpret the subgradient elements as being deﬁned with

respect to the decision variables x .

Theorem 11. If x ∈K,then

∂

Q(x)=E

∂

Q(x,

(

)) + N(K

,x) , (1.15)

where N(K

,x)={v | v

y ≤ 0,∀ y such that x+ y ∈ K

}, the normal cone to K

at x .

Proof: From the theory of subdifferentials of random convex functions with ﬁnite

expectations (see, for example, Wets [1990, Proposition 2.11]),

∂

Q(x)=E

∂

Q(x,

(

)) + rc[

∂

Q(x)] , (1.16)

where again rc denotes the recession cone , {v | u +

v ∈

∂

Q(x), for all

≥ 0

and u ∈

∂

Q(x)}. This set is equivalently {v | y

(u +

v)+Q(x) ≤ Q(x + y) for

all

≥0andy}. Hence, v ∈rc[

∂

Q(x)] if and only if y

v ≤ 0forally such that

Q(x + y) < ∞ . Because K

= {x | Q(x) < ∞}, the result follows.

This theorem indeed provides the basis for the results on the differentiability of

Q . In the exercises, we illustrate more of the characteristics of optimal solutions.

Also note that if the problem has relatively complete recourse, then, for any y such

that x + y ∈K

,wemustalsohave x + y ∈ K

. Hence, N(K

,x) ⊂ N(K

,x)={v |

v = A

x = 0 ,

≥ 0}. This yields the following corollary to Theorems

9 and 11.

Corollary 12. If (1.2) has relatively complete recourse, a solution x

∗

is optimal in

(1.2) if and only if there exists some

∗

∈ ℜ

∗

∈ ℜ

∗T

∗

= 0 , such that

−c + A

∗

∈E

∂

Q(x,

(

)) . (1.17)

Corollary 12 provides the basis for a dual formulation as well. The ﬁrst step is to

identify

∂

Q(x,

(

)) (Exercise 10) as follows:

∂

Q(x,

(

)) = {−E[πT]|π

W ≤ q

118 3 Basic Properties and Theory

(h−Tx) ≥ (π



)

(h−Tx),∀(π



)

W ≤ q

a.s.}. (1.18)

Given this form of the subgradient, an equivalent dual program to (1.2) under the

relatively complete recourse assumption can be obtained (Exercise 11) by solving

the following maximization problem:

maxv = b

+ E

[h(

)

(

)]

s. t. A

+ E

[T(

)

(

)] ≤ c ,

(

) ≤q(

) ,a.s.

(1.19)

f. Stability and nonanticipativity

Another practical concern is whether the optimal solution set is also stable, i.e.,

whether it changes continuously in some sense when parameters of the problem

change continuously. Although this may be of concern when considering changing

problem conditions, we do not develop this theory in detail. The main results are

that stability is achieved (i.e., some optimal solution of an original problem is close

to some optimal solution of a perturbed problem) if problem (1.2) has complete

recourse and the set of recourse problem dual solutions, {

W ≤ q(

)

},is

nonempty with probability one. For further details, we refer to Robinson and Wets

[1987] and R¨omisch and Schultz [1991b].

Another approach to optimality conditions is to consider problem (1.2), in which

) again becomes an explicit part of the problem and the nonanticipativity con-

straints also become explicit. The advantage in this representation is that we may

obtain information on the value of future information. It also leads naturally to al-

gorithms based on relaxing nonanticipativity.

We discuss the main results in this characterization brieﬂy. The following devel-

opment assumes some knowledge of measure theory and can be skipped by those

unfamiliar with these concepts.

In general, for this approach, we wish to have a different x,y pair for every real-

ization of the random outcomes. We then wish to restrict the x decisions to be the

same for almost all outcomes. This says that the decision, (x(

),y(

)) , is a func-

tion (with suitable properties) on

. We restrict this to some space, X , of measur-

able functions on

, for example, the p -integrable functions, L

(

,B,

;ℜ

) ,

for some 1 ≤ p ≤∞ . (For background on these concepts, see, for example, Royden

[1968].) The general version of (1.2) (with certain restrictions) then becomes:

inf

(x(

),y(

))∈X



)+q(

)

))

)

3.1 Two-Stage Stochastic Linear Programs with Fixed Recourse 119

s. t. Ax(

)=b, a.s.,

(x(

)) −x(

)=0, a.s.,

)x(

)+Wy(

)=h(

), a.s.,

),y(

) ≥ 0, a.s.

(1.20)

Problem (1.20) is equivalent to (1.2) if, for example, X is the space of essentially

bounded functions on

and K is bounded for (1.2). The two formulations are not

necessarily the same, however, as in the problem given in Exercise 12.

The condition that the x decision is taken before realizing the random outcomes

is reﬂected in the second set of constraints in (1.20). These constraints are again the

nonanticipativity constraints, which imply that almost all x(

) values are the same.

The only difference in optimality conditions of (1.20) from those of (1.12)isthat

we include explicit multipliers for the nonanticipativity constraints. For continuous

distributions, these multipliers may, however, have a difﬁcult representation unless

(1.20) has relatively complete recourse. The difﬁculty is that we cannot guarantee

boundedness of the multipliers and may not be able to obtain an integrable function

to represent them. This difﬁculty is caused when future constraints restrict the set of

feasible solutions at the ﬁrst stage.

For ﬁnite distributions, (1.20) is, however, an implementable problem structure

that is used in several algorithms discussed here. In this case, with K possible real-

izations of ξ with probabilities p

, k = 1,...,K , the problem becomes:

inf

),k=1,...,K

∑

k=1

+(q

)

s. t. Ax

= b, k = 1,...,K ,

∑

j= k

+(p

−1)x

= 0, k = 1,...,K ,

+Wy

= h

, k = 1,...,K ,

≥ 0, k = 1,...,K .

(1.21)

Notice that (1.21) almost completely decomposes into K separate problems for

the K realizations. The only links are in the second set of constraints that impose

nonanticipativity. An aim of computation is to take advantage of this structure.

Consider the optimality conditions for (1.19). We wish to illustrate the difﬁculties

that may occur when continuous distributions are allowed. A solution (x

k∗

) ,

k = 1,...,K , is optimal for (1.21) if and only if there exist (

k∗

) such that

−

k∗T

·j

−

∑

l=k

l∗

−(−1 + p

)

k∗

−

∗T

·j

) ≥0 ,

k = 1,...,K , j = 1,...,n

, (1.22)

120 3 Basic Properties and Theory

−

k∗T

·j

−

∑

l=k

l∗

−(−1 + p

)

k∗

−

∗T

·j

k∗

= 0 ,

k = 1,...,K , j = 1,...,n

, (1.23)

−

∗T

·j

) ≥0 , k = 1,...,K , j = 1,...,n

, (1.24)

−

∗T

·j

k∗

= 0 , k = 1,...,K , j = 1,...,n

, (1.25)

where we have effectively multiplied the constraints in (1.19)by p

to obtain the

form in (1.22)–(1.25). We may also add the condition,

∑

k=1,...,K

k∗

= 0 , (1.26)

without changing the feasibility of (1.22)–(1.25). This is true because, if

∑

k=1,...,K

k∗

for some

= 0 is part of a feasible solution to (1.22)–(1.25),

then so is



k∗

−

. A problem arises if more realizations are included in the

formulation (i.e., K increases) and



becomes unbounded.

To see how the multipliers may become unbounded, consider the following ex-

ample (see also Rockafellar and Wets [1976a]). We wish to ﬁnd min

{x |x ≥0, x −

y = ξ, a.s.,y ≥ 0},where ξ is uniformly distributed on k/K for k = 0,...,K −1

and K ≥ 2 . In this case, the optimal solution is x

∗

K−1

and y

k∗

K−1−k

for

k = 0,...,K . The multipliers satisfying (1.22)–(1.26)are

k∗

= 1,

k∗

= 0for

k = 0,...,K −2, and

K−1∗

= −(K −1) and

K−1∗

= −K + 2 . Note that as K

increases,

∗

approaches a distribution with a singular value at one. The difﬁculty

is that

K−1∗

is unbounded so that bounded convergence cannot apply. If relatively

complete recourse is assumed, however, then all elements of

∗

are bounded (see

Exercise 13). No singular values are necessary.

In this example, the continuous distribution would tend toward a singular multi-

plier for some value of

(i.e., a multiplier with mass one at a single point). If this

is the case, we must have that the solution to the dual of the recourse problem is un-

bounded, or the recourse problem is infeasible for x

∗

feasible in the ﬁrst stage. This

possibility is eliminated by imposing the relatively complete recourse assumption.

With relatively complete recourse, we can state the following optimality condi-

tions for a solution (x

∗

(

),y

∗

(

)) to (1.19). The theorem appears in other ways in

Hiriart-Urruty [1978], Rockafellar and Wets [1976a, 1976b], Birge and Qi [1993],

and elsewhere. We only note that regularity conditions (other than relatively com-

plete recourse) follow from the linearity of the constraints.

Theorem 13. Assuming that (1.20) with X = L

∞

(

,B,

;ℜ

) is feasible,

has a bounded optimal value, and satisﬁes relatively complete recourse, a solution

∗

(

),y

∗

(

)) is optimal in (1.20) if and only if there exist integrable functions on

, (

∗

(

∗

(

∗

(

)) , such that

3.1 Two-Stage Stochastic Linear Programs with Fixed Recourse 121

−

∗

(

·j

−

∗

(

) −

∗T

(

·j

(

) ≥0 , a.s., j = 1,...,n

, (1.27)

−

∗

(

·j

−

∗

(

) −

∗T

(

·j

(

))x

∗

(

)=0 ,

a.s., j = 1,...,n

, (1.28)

(

) −

∗T

(

·j

≥ 0 , a.s., j = 1,...,n

, (1.29)

(

) −

∗T

(

·j

∗

(

)=0, a.s., j = 1,...,n

, (1.30)

and

[

∗

(

)] = 0 . (1.31)

Proof: We ﬁrst show the sufﬁciency of these conditions directly. If (1.27)–(1.31)

are satisﬁed, then for any (x(

),y(

)) (with expected value (x,y) ) such that

∗

(

)+x(

),y

∗

(

)+y(

)) is feasible in (1.20), then integrating over

,sum-

ming over j in (1.28), and using (1.29), we obtain that c

x−E

[

∗T

(

)T(

)]x ≥

0 . We also have that q(

)

) ≥

∗T

(

)Wy(

)=−

∗T

(

)T(

)x . Hence,

x + E

[q(

)

)] ≥ 0 , giving the optimality of (x

∗

(

),y

∗

(

)) .

For necessity, we use the equivalence of (1.20)and(1.2), and Corollary 12.

In this case, let

∗

from (1.12) replace

∗

(

) in (1.27). Let

∗

(

) be the

optimal dual value in the recourse problem in (1.4). Thus, E

[

∂

Q(x

∗

(

))] =

[−

∗T

(

)T(

)] .Now,ifwelet

∗

(

[−

∗T

(

)T] −

∗T

(

)T(

) , we obtain all the conditions in

(1.27)–(1.31).

The results in this section give conditions that can be useful in algorithms and in

checking the optimality of stochastic programming solutions. Dual problems similar

to (1.18) can also be formulated based on these conditions either to obtain bounds

on optimal solutions by ﬁnding corresponding feasible dual solutions or to give an

alternative solution procedure that can be used directly or in some combined primal-

dual approach (see, for example, Bazaraa and Shetty [1979]). The dual problem di-

rectly obtained from (1.27)–(1.31)istoﬁnd (

(

)) on the dual space

to X to maximize

(

)+h(

)

(

)] subject to (1.32)

(

)+T(

)

(

) ≤c , a.s., (1.33)

(

) ≤q(

) , a.s., (1.34)

and

[

(

)] = 0 . (1.35)

122 3 Basic Properties and Theory

This ﬁts the general duality framework used by Klein Haneveld [1985] where fur-

ther details on the properties of these dual problems may be found. Rockafellar and

Wets [1976a, 1976b] also discuss this alternative viewpoint with an analysis based

on perturbations of both primal and dual forms. Discussion of alternative dual spaces

appears in Eisner and Olsen [1975]. In general, Problem (1.20) attains its minimum

with a bounded region, and the supremum in (1.32)–(1.35) gives the same value.

Relatively complete recourse, or a similar requirement, is necessary to obtain that

the dual optimum is also attained. With unbounded regions or without relatively

complete recourse, as we have seen, we may have that an optimal solution is not

attained for either (1.21)or(1.32)–(1.35). In this case, it is possible that the corre-

sponding dual problem does not have the same optimal value and the two problems

exhibit a duality gap. The exercises explore this possibility further.

Exercises

1. Consider Example 1 with a second-stage program deﬁned as

min 2y

+ y

s. t. y

+ 2y

≥

−x

+ y

≥

−x

0 ≤ y

≤ 1 , 0 ≤y

≤ 1 .

We have seen that K

(

)={x | x

≥

−3 , x

+ x

≥

−2}.Let ξ

and

be two independent continuous random variables. Assume they both have

uniform density over [2,4] .

(a) What is K

(b) What is K

∗

be deﬁned as in (1.7). What are u

∗

and u

∗

in this example?

2. Let the second stage of a stochastic program be

min 2y

+ y

s. t. y

−y

≤ 2 −ξx

≤ x

0 ≤ y

Find K

(ξ) and K

for:

(a) ξ ∼U[0,1] .

(b) ξ ∼ Poisson(

) ,

> 0.

What properties do you expect for K

3.1 Two-Stage Stochastic Linear Programs with Fixed Recourse 123

3. Consider the following second-stage program:

Q(x,

)=min{y | y ≥

,y ≥x} .

For simplicity, assume x ≥0.

Let ξ have density

f (

≥ 1 .

Show that K

= K

. Compare this with the statement of Theorem 3.

4. Consider Example 2 where the second-stage program is deﬁned as

min 2y

+ y

s. t. y

+ y

≥ 1 −x

≥ ξ −x

−x

≥ 0 ,

where

⊂ ℜ

(a) Show that this program has complete recourse if ξ has ﬁnite expectation.

(b) Show that Q(x,

) is convex in x and convex in

thors of this book will go through, one obtains Q(x)=

+2x

−

−6x

+ 9) . Check that the relevant properties of Theorem 6 are satis-

ﬁed.

5. Let a second-stage program be deﬁned as

min

+ y

s. t. y

+ y

≥ 1 −x

−x

≥ 0 .

Assume 0 ≤ x

≤ 1 . Obtain Q(x,

) and observe that it is concave in

6. Prove the positive homogeneity property in (1.8).

7. Derive the simple recourse results in (1.9)and(1.10).

8. Show that the news vendor problem is a special case of a simple recourse prob-

lem.

9. Consider the following example:

min −x+ E

(t(

),h(

))

(

)+y

−

(

)]

s. t. t(

)x + y

(

) −y

−

(

)=h(

) , a.s.,

x,y

(

),y

−

(

) ≥ 0 , a.s.,