Contents
Preface iii
1 Stochastic Programming Models 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Inventory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2.1 The Newsvendor Problem . . . . . . . . . . . . . . . . . 1
1.2.2 Chance Constraints . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Multistage Models . . . . . . . . . . . . . . . . . . . . . 6
1.3 Multi-Product Assembly . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.1 Two Stage Model . . . . . . . . . . . . . . . . . . . . . 9
1.3.2 Chance Constrained Model . . . . . . . . . . . . . . . . 11
1.3.3 Multistage Model . . . . . . . . . . . . . . . . . . . . . 12
1.4 Portfolio Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4.1 Static Model . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4.2 Multistage Portfolio Selection . . . . . . . . . . . . . . . 17
1.4.3 Decision Rules . . . . . . . . . . . . . . . . . . . . . . . 21
1.5 Supply Chain Network Design . . . . . . . . . . . . . . . . . . . . . 22
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2 Two Stage Problems 27
2.1 Linear Two Stage Problems . . . . . . . . . . . . . . . . . . . . . . . 27
2.1.1 Basic Properties . . . . . . . . . . . . . . . . . . . . . . 27
2.1.2 The Expected Recourse Cost for Discrete Distributions . 30
2.1.3 The Expected Recourse Cost for General Distributions . . 33
2.1.4 Optimality Conditions . . . . . . . . . . . . . . . . . . . 38
2.2 Polyhedral Two-Stage Problems . . . . . . . . . . . . . . . . . . . . . 42
2.2.1 General Properties . . . . . . . . . . . . . . . . . . . . . 42
2.2.2 Expected Recourse Cost . . . . . . . . . . . . . . . . . . 44
2.2.3 Optimality Conditions . . . . . . . . . . . . . . . . . . . 47
2.3 General Two-Stage Problems . . . . . . . . . . . . . . . . . . . . . . 48
2.3.1 Problem Formulation, Interchangeability . . . . . . . . . 48
2.3.2 Convex Two-Stage Problems . . . . . . . . . . . . . . . 50
2.4 Nonanticipativity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.4.1 Scenario Formulation . . . . . . . . . . . . . . . . . . . 53
2.4.2 Dualization of Nonanticipativity Constraints . . . . . . . 55
2.4.3 Nonanticipativity Duality for General Distributions . . . 56
2.4.4 Value of Perfect Information . . . . . . . . . . . . . . . . 60
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3 Multistage Problems 63
3.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.1.1 The General Setting . . . . . . . . . . . . . . . . . . . . 63
3.1.2 The Linear Case . . . . . . . . . . . . . . . . . . . . . . 65
3.1.3 Scenario Trees . . . . . . . . . . . . . . . . . . . . . . . 69
3.1.4 Algebraic Formulation of Nonanticipativity Constraints . 72
3.2 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.2.1 Convex Multistage Problems . . . . . . . . . . . . . . . 76
3.2.2 Optimality Conditions . . . . . . . . . . . . . . . . . . . 77
3.2.3 Dualization of Feasibility Constraints . . . . . . . . . . . 81
3.2.4 Dualization of Nonanticipativity Constraints . . . . . . . 82
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4 Optimization Models with Probabilistic Constraints 87
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.2 Convexity in Probabilistic Optimization . . . . . . . . . . . . . . . . 94
4.2.1 Generalized Concavity of Functions and Measures . . . . 94
4.2.2 Convexity of Probabilistically Constrained Sets . . . . . 107
4.2.3 Connectedness of Probabilistically Constrained Sets . . . 114
4.3 Separable Probabilistic Constraints . . . . . . . . . . . . . . . . . . . 115
4.3.1 Continuity and Differentiability Properties of Distribu-
tion Functions . . . . . . . . . . . . . . . . . . . . . . . 115
4.3.2 p-Efficient Points . . . . . . . . . . . . . . . . . . . . . 117
4.3.3 Optimality Conditions and Duality Theory . . . . . . . . 123
4.4 Optimization Problems with Nonseparable Probabilistic Constraints . . 133
4.4.1 Differentiability of Probability Functions and Optimality
Conditions . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.4.2 Approximations of Nonseparable Probabilistic Constraints 137
4.5 Semi-infinite Probabilistic Problems . . . . . . . . . . . . . . . . . . 145
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
5 Statistical Inference 157
5.1 Statistical Properties of SAA Estimators . . . . . . . . . . . . . . . . 157
5.1.1 Consistency of SAA Estimators . . . . . . . . . . . . . . 159
5.1.2 Asymptotics of the SAA Optimal Value . . . . . . . . . . 165
5.1.3 Second Order Asymptotics . . . . . . . . . . . . . . . . 168
5.1.4 Minimax Stochastic Programs . . . . . . . . . . . . . . . 172
5.2 Stochastic Generalized Equations . . . . . . . . . . . . . . . . . . . . 176
5.2.1 Consistency of Solutions of the SAA Generalized Equa-
tions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
5.2.2 Asymptotics of SAA Generalized Equations Estimators . 180
5.3 Monte Carlo Sampling Methods . . . . . . . . . . . . . . . . . . . . . 182
5.3.1 Exponential Rates of Convergence and Sample Size Es-
timates in Case of Finite Feasible Set . . . . . . . . . . . 184
5.3.2 Sample Size Estimates in General Case . . . . . . . . . . 188
5.3.3 Finite Exponential Convergence . . . . . . . . . . . . . . 194
5.4 Quasi-Monte Carlo Methods . . . . . . . . . . . . . . . . . . . . . . 195
5.5 Variance Reduction Techniques . . . . . . . . . . . . . . . . . . . . . 201
5.5.1 Latin Hypercube Sampling . . . . . . . . . . . . . . . . 201
5.5.2 Linear Control Random Variables Method . . . . . . . . 203
5.5.3 Importance Sampling and Likelihood Ratio Methods . . . 203
5.6 Validation Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
5.6.1 Estimation of the Optimality Gap . . . . . . . . . . . . . 206
5.6.2 Statistical Testing of Optimality Conditions . . . . . . . . 210
5.7 Chance Constrained Problems . . . . . . . . . . . . . . . . . . . . . . 213
5.7.1 Monte Carlo Sampling Approach . . . . . . . . . . . . . 214
5.7.2 Validation of an Optimal Solution . . . . . . . . . . . . . 220
5.8 SAA Method Applied to Multistage Stochastic Programming . . . . . 224
5.8.1 Statistical Properties of Multistage SAA Estimators . . . 225
5.8.2 Complexity Estimates of Multistage Programs . . . . . . 230
5.9 Stochastic Approximation Method . . . . . . . . . . . . . . . . . . . 233
5.9.1 Classical Approach . . . . . . . . . . . . . . . . . . . . 234
5.9.2 Robust SA Approach . . . . . . . . . . . . . . . . . . . 237
5.9.3 Mirror Descent SA Method . . . . . . . . . . . . . . . . 240
5.9.4 Accuracy Certificates for Mirror Descent SA Solutions . . 248
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253