随机逼近：Stability, Approximation, and Decomposition in Two- and Multistage Stochastic Programming by Christian Kuchler

【实例截图】

【核心代码】

Contents
1 Introduction 1
1.1 Stochastic Programming Models . . . . . . . . . . . . . . . . . 1
1.2 Approximations, Stability, and Decomposition . . . . . . . . . 4
1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Stability of Multistage Stochastic Programs 9
2.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Continuity of the Recourse Function . . . . . . . . . . . . . . 13
2.3 Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 Calm Decisions . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.5 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Recombining Trees for Multistage Stochastic Programs 33
3.1 Problem Formulation and Decomposition . . . . . . . . . . . . 35
3.1.1 Nested Benders Decomposition . . . . . . . . . . . . . 37
3.1.2 Cut Sharing . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.3 Recombining Scenario Trees . . . . . . . . . . . . . . . 39
3.2 An Enhanced Nested Benders Decomposition . . . . . . . . . 40
3.2.1 Cutting Plane Approximations . . . . . . . . . . . . . . 41
3.2.2 Dynamic Recombining of Scenarios . . . . . . . . . . . 45
3.2.3 Upper Bounds . . . . . . . . . . . . . . . . . . . . . . . 51
3.2.4 Extended Solution Algorithm . . . . . . . . . . . . . . 53
3.3 Construction of Recombining Trees . . . . . . . . . . . . . . . 55
3.3.1 A Tree Generation Algorithm . . . . . . . . . . . . . . 57
3.3.2 Consistency of the Tree Generation Algorithm . . . . . 60
3.4 Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.4.1 A Power Scheduling Problem . . . . . . . . . . . . . . 77
3.4.2 Numerical Results . . . . . . . . . . . . . . . . . . . . 79
3.5 Out-of-Sample Evaluation . . . . . . . . . . . . . . . . . . . . 83
3.5.1 Problem Formulation . . . . . . . . . . . . . . . . . . . 84
3.5.2 Towards Feasible Solutions . . . . . . . . . . . . . . . . 85
x Contents
3.5.3 Numerical Examples . . . . . . . . . . . . . . . . . . . 89
4 Scenario Reduction with Respect to Discrepancy Distances 97
4.1 Discrepancy Distances . . . . . . . . . . . . . . . . . . . . . . 98
4.2 On Stability of Two-Stage and Chance-Constrained Programs 100
4.3 Scenario Reduction . . . . . . . . . . . . . . . . . . . . . . . . 105
4.4 Bounds and Specific Solutions . . . . . . . . . . . . . . . . . . 106
4.4.1 Ordered Solution and Upper Bound . . . . . . . . . . . 106
4.4.2 Lower Bound . . . . . . . . . . . . . . . . . . . . . . . 110
4.5 The Inner Problem . . . . . . . . . . . . . . . . . . . . . . . . 113
4.5.1 Critical Index Sets . . . . . . . . . . . . . . . . . . . . 114
4.5.2 Reduced Critical Index Sets . . . . . . . . . . . . . . . 115
4.5.3 Determining the Coefficients . . . . . . . . . . . . . . . 116
4.5.4 Optimal Redistribution Algorithm . . . . . . . . . . . . 121
4.6 The Outer Problem . . . . . . . . . . . . . . . . . . . . . . . . 124
4.6.1 Revising Heuristics . . . . . . . . . . . . . . . . . . . . 124
4.6.2 A Glimpse on Low Discrepancy Sequences . . . . . . . 127
4.6.3 A Branch and Bound Approach . . . . . . . . . . . . . 127
4.7 Numerical Experience . . . . . . . . . . . . . . . . . . . . . . . 131
4.8 Further Results . . . . . . . . . . . . . . . . . . . . . . . . . . 138
4.8.1 A Note on Extended Discrepancies . . . . . . . . . . . 138
4.8.2 Mass Transportation and Clustering . . . . . . . . . . 140
4.8.3 An Estimation between Discrepancies . . . . . . . . . . 144
Appendix 153
Bibliography 159
List of Figures
3.1 Recombining and non-recombining scenario trees . . . . . . . . 40
3.2 Electricity demand and wind turbine power curve . . . . . . . 78
3.3 Out-of-sample values for the power scheduling model . . . . . 91
3.4 Out-of-sample values for the swing option model . . . . . . . . 95
4.1 Recourse function of Example 4.2.1 . . . . . . . . . . . . . . . 104
4.2 Supporting and non-supporting polyhedra . . . . . . . . . . . 117
4.3 Rectangular discrepancy for different reduction techniques . . 125
4.4 Cumulative distribution functions of Example 4.6.1 . . . . . . 126
4.5 Cell discrepancy and running time for the Forward Selection. . 134
4.6 Low discrepancy points with adjusted probabilities . . . . . . 135
4.7 Perturbation of the optimal value of Example 4.7.1 . . . . . . 136
4.8 Recourse function of Example 4.7.2 . . . . . . . . . . . . . . . 137
4.9 Perturbation of the optimal value of Example 4.7.2 . . . . . . 138
4.10 Probabilities adjusted with respect to α B rect and ζ 2 . . . . . . 142
4.11 α B rect and ζ 2 for different weighting factors . . . . . . . . . . . 143
4.12 Optimal mass transportation with respect to α B rect and ζ 2 . . 144
4.13 A polyhedron and the corresponding set M ∦ . . . . . . . . . . 147
4.14 Enlargements of a polyhedron . . . . . . . . . . . . . . . . . . 149
4.15 Polyhedral singularity of multivariate normal distributions . . 151
List of Tables
3.1 Parameters of the power scheduling model . . . . . . . . . . . 79
3.2 Running times of Benders Decomposition . . . . . . . . . . . . 80
3.3 Running times with and without using upper bounds . . . . . 81
3.4 Running times for different aggregation parameters . . . . . . 83
3.5 Out-of-sample values for different aggregation parameters . . . 92
3.6 Out-of-sample values for different aggregation parameters . . . 96
4.1 Number of supporting polyhedra and critical index sets . . . . 132
4.2 Running times of Algorithm 4.1 . . . . . . . . . . . . . . . . . 133
4.3 Running times of various support selection algorithms . . . . . 134
Index of Notation
1 B (·) the indicator function of the set B
?·,·? the standard scalar product in R m
|I| the cardinality of the finite set I
?a,¯ a? a closed polyhedron in R s induced by a,¯ a ∈
¯
R k , see p.116
α B the discrepancy distance w.r.t.the system B, see p.98
B a system of Borel subsets of R s , see p.98
B cell the system of closed cells in R s , see p.98
B cl the system of closed subsets of R s , see p.98
B conv the system of closed, convex subsets of R s , see p.98
B ph,k the system of polyhedra in R s having at most k vertices, see p.98
B ph,W the system of polyhedra in R s each of whose facets parallels a
facet of [0,1] s or posW, see p.98
B rect the system of closed, s-dimensional rectangles in R s
C feas a set of feasibility cuts, see p.43
C opt a set of optimality cuts, see p.42
δ ξ the Dirac measure in ξ
∂B the topological boundary of the Borel set B
d the Pompeiu-Hausdorff distance, see p.12
D F a probability metric with ζ-structure, see p.100
Δ B the optimal value of the scenario reduction problem, see p.107
dist(a,B) the distance between the point a ∈ R n and the set B ⊂ R n , see
p.12
E[ξ] the expectation of the random variable ξ
F a class of Borel measurable mappings, see p.100
F p a class of locally Lipschitz continuous mappings, see p.101
¯
F p a class of uniformly bounded, piecewise locally Lipschitz contin-
uous mappings, see p.101
¯
F p,B ? a class of uniformly bounded, locally Lipschitz continuous map-
pings, see p.101
I B the system of critical index sets, see p.114
I ∗
B
the system of reduced critical index sets, see p.115
Index of Notation xvi
intS the topological interior of the set S
Λ R j the set of representative nodes at time R j , see p.40
M m
[1,T]
a set of Borel measurable mappings, see p.11
posW the positive cone of a (d × m)-matrix W, i.e., posW = {Wy :
y ∈ R m
}
Q t (·,·) the recourse function at time t, see p.13
P,Q Borel probability measures
P t the probability distribution of the random variable ξ t under the
measure P, see p.11
P [t] the probability distribution of the random variable ξ [t] under the
measure P, see p.11
P the set of supporting polyhedra, see p.117
P p (Ξ) the set of all Borel probability measures on Ξ ⊂ R s with finite
absolute moments of order p ≥ 1, see p.101
R the set of real numbers
R the set of non-negative real numbers, i.e., R = [0,∞)
¯
R the set of extended real numbers,
¯
R = R ∪ {−∞, ∞}
ξ an R s -valued random variable or stochastic process
ξ [t] the random vector (ξ 1 ,...,ξ t )
ξ [s,t] the random vector (ξ s ,...,ξ t ) for s,t ∈ N with s ≤ t
S(ξ) the set of decisions that are feasible w.r.t. the process ξ, see p.12
S n the standard simplex in R n , see p.105
v(ξ),v(P) the optimal value of a stochastic program, see p.12
Ξ t the support of the measure P t
Ξ [t] the support of the measure P [t]
ζ p the p-th order Fortet-Mourier metric, see p.101
ζ p,B ph,k an extended polyhedral discrepancy, see p.101
ζ p,B ph,W an extended polyhedral discrepancy, see p.101