Stability, Approximation, and Decomposition in Two- and Multistage Stochastic Programming
Stochastic programming provides a framework for modelling, analyzing, and solving optimization problems with some parameters being not known up to a probability distribution. Such problems arise in a variety of applications, such as inventory control, fin
- PDF / 175,555 Bytes
- 15 Pages / 420 x 595 pts Page_size
- 74 Downloads / 213 Views
gt (ξˆ[t] , εt+1 )
mt+1 h( εt+1 ) ≤ E max 1, gt (ξ[t] , εt+1 ) , gt (ξˆ[t] , εt+1 )
· max{1, ξ[t] , ξˆ[t] }r ξ[t] − ξˆ[t]
mt+1 k( εt+1 )mt+1 h( εt+1 ) ≤ E max 1, ξ[t] , ξˆ[t]
· max{1, ξ[t] , ξˆ[t] }r ξ[t] − ξˆ[t]
= E [k( εt+1 )mt+1 h( εt+1 )] · max{1, ξ[t] , ξˆ[t] }r+mt+1 ξ[t] − ξˆ[t] . Due to the identity r+mt+1 = mt −1, this entails condition (i) of Assumption 2.2.6. The asserted form of K follows from m1 ≥ mt for t = 1, . . . , T . Furthermore, we apply (2.13) recursively to obtain the following estimate:
ξ T ≤ max{1, ξ[t] }
T
k( εi ).
i=t+1
Raising both sides to the power of 1 + (T − t) and taking conditional expectations E[ · |ξ[t] = ξ[t] ] verifies condition (ii) of Assumption 2.2.6. Proposition A.1. The strategy x∗ defined by (3.92) is an optimal solution to problem (3.89). Proof. We introduce the value ht U − t−1 s=1 xs that indicates how much of the swing option’s intial capacity U is still available at time t. The time t
154
Appendix
recourse function Qt (·, ·) of problem (3.91) can be written in terms of ht by setting QT +1 ≡ 0 and min xt ψ(ξt ) + E Qt+1 (ht − xt , ξt+1 ) ξt = ξt . (A.2) Qt (ht , ξt ) xt ∈[0,1],xt ≤ht
Let us denote the objective function of problem (A.2) by Φt (ht , ξt , xt ) xt ψ(ξt ) + E[Qt+1 (ht − xt , ξt+1 )|ξt = ξt ]. ∗ The strategy x∗ with h∗t t−1 s=1 xs is optimal for problem (3.91) if and only if the equality Qt (h∗t , ξt ) = Φt (h∗t , ξt , x∗t (ξt )) (A.3) is fulfilled for P−a.e. ξt ∈ Ξt for t = 1, . . . , T . By definition, we have x∗ defined by (3.92) fulfills x∗t = 0 and h∗t = U for t = 1, . . . , T − U . Together with the presentation (A.6) of Qt , this shows that identity (A.3) holds for t = 1, . . . , T − U . Let us now consider t ∈ {T − U + 1, . . . , T } and note that h∗t ≥ T + 1 − t and h∗t ∈ N. Thus, relation (A.6) turns to T Qt (h∗t , ξt ) = E[ψ(ξs )|ξt = ξt ] (A.4) s=t
On the other hand, we have x∗t (ξt ) = 1 if ψ(ξt ) = 0. This yields x∗t (ξt )ψ(ξt ) = ψ(ξt ) = E[ψ(ξt )|ξt = ξt ], and, in particular, Φt (h∗t , ξt , x∗t (ξt )) = E[ψ(ξt )|ξt = ξt ] + E[Qt+1 (h∗t − x∗t (ξt ), ξt+1 )|ξt = ξt ]. (A.5) Applying now h∗t − x∗t ≥ T + 1 − (t + 1) and h∗t − x∗t ∈ N together with (A.6) shows that the right side of (A.5) is equal to the right side of (A.4). Thus, (A.3) holds also for t = T − U + 1, . . . , T and, consequently, x∗ given by (3.92) is optimal for problem (3.91). Because x∗t > 0 only if ξt > K, the strategy x∗ is also optimal for problem (3.89). Proposition A.2. The cost-to-go function Qt (ht , ξt ) of problem (3.91), defined by (A.2), has the form Qt (ht , ξt ) = (ht − ht ) E[ψ(ξT −ht )|ξt = ξt ] 1{T −ht ≥t} +
T
(A.6)
E[ψ(ξs )|ξt = ξt ],
s=max{t,T +1−ht }
i.e., for t = 1, . . . , T the mapping ht → Qt (ht , ξt ) is convex and nonincreasing. Furthermore, it is affine in ht on every interval [z, z + 1] for z ∈ N+ .
Appendix
155
Proof. Since ψ a concave mapping, the conditional version of the Jensen inequality yields for t = 1, . . . , T, and s ≥ t ψ (E[ξs |ξt = ξt ]) ≥ E[ψ(ξs )|ξt = ξt ]. Since the dri
Data Loading...
