Stochastic Programming (eBook)

Preface 6
George B. Dantzig and Optimization UnderUncertainty 10
References 14
Contents 16
List of Figures 18
Contributors 20
1 Linear Programming Under Uncertainty 23
Example 1. Minimum Expected Cost Diet 23
Example 2. Shipping to an Outlet to Meet an Uncertain Demand 24
Example 3. A Three-Stage Case 25
Example 4. A Class of Two-Stage Problems 25
Example 5. The Two-Stage Problem with General Linear Structure 29
Example 6. The Multistage Problem with General Linear Structure 31
Solution for Example 2. Shipping to an Outlet to Meetan Uncertain Demand 32
Solution for Example 5. The General Two-Stage Case 33
References 33
2 A Probabilistic Lower Bound for Two-Stage Stochastic Programs 34
2.1 Introduction 34
2.2 The Problem 35
2.3 Benders Decomposition 37
2.4 Probabilistic Lower Bound 40
2.4.1 Cut Generation Using Sampling 40
2.4.2 Stochastic Benders Algorithm 41
2.4.3 First-Stage Decision x=l, Upper Confidence Interval for z* 41
2.4.4 Lower Confidence Interval for z* 42
2.4.5 The Distribution of the Error Term 44
2.4.6 Worst-Case Lower Bound for z* 45
2.4.7 Conservative Lower Bound for z* 46
2.5 Test 49
References 55
3 Simulation-Based Optimality Tests for Stochastic Programs 57
3.1 Introduction 57
3.2 Background and Motivation 59
3.3 Multiple Replications Procedure 61
3.4 Single and Two Replication Procedures 65
3.5 Bias Reduction 67
3.6 Variance Reduction 70
3.7 Conclusions 72
References 73
4 Stochastic Decomposition and Extensions 76
4.1 Introduction 76
4.2 Stochastic Decomposition 77
4.3 Extensions of Regularized SD 80
4.3.1 A Sufficient Condition for a Unique Limit 80
4.3.2 SD With Resampling 81
4.3.3 Preliminary Computational Results 83
4.4 Conclusion 84
References 85
5 Barycentric Bounds in Stochastic Programming: Theory and Application 86
5.1 Introduction 86
5.2 Problem Formulation 88
5.3 Regularity Conditions 91
5.4 Barycentric Probability Measures 93
5.5 Bounds for Stochastic Programs 97
5.6 Application in Financial Risk Management 101
5.6.1 Formulation as Multistage Stochastic Program 102
5.6.2 Risk Factor Models 103
5.6.3 Check of Regularity Conditions 105
5.6.4 Numerical Solution 108
5.7 Conclusions 111
References 113
6 Stochastic Programming Approximations Using Limited Moment Information, with Application to Asset Allocation 116
6.1 Introduction 116
6.1.1 Bound-Based Approximations 118
6.1.2 Bounds Using Generalized Moment Problems 120
6.2 Bounding the Expected Recourse Function 122
6.2.1 First-Order Moment Bounds 123
6.2.2 Tightening First-Moment Bounds 127
6.3 Second-Order Moment Bounds 131
6.3.1 Simplicial Mean--Covariance Approximation 133
6.3.2 Tightening Second-Order Bounds 136
6.3.3 Higher Order Moment Upper Bounds in Convex Case 137
6.4 Simplicial Sequential Solution (SSS) 139
6.4.1 Partitioning and Convergence 140
6.4.2 Partitioning Strategies and Cell Redefining 142
6.4.2.1 Edge Selection 142
6.4.2.2 Cell Redefining 144
6.5 Asset Allocation Application 145
6.5.1 Scenario Clustering and Sensitivity Analysis 149
6.5.2 Efficient Frontiers and Transaction Costs 149
6.6 Concluding Remarks 154
References 154
7 Stability and Scenario Trees for Multistage Stochastic Programs 158
7.1 Introduction 158
7.2 Stability of Multistage Models 160
7.3 Generating Scenario Trees 173
7.4 Numerical Experience 178
7.4.1 Adapting a Statistical Model 178
7.4.2 Construction of Input Scenario Trees 179
References 182
8 Risk Aversion in Two-Stage Stochastic Integer Programming 184
8.1 Introduction 184
8.2 Structural Results 187
8.2.1 Prerequisites: Value Functions and Expectation Models 187
8.2.2 Risk Measures 189
8.2.3 Structure of Objective Functions 190
8.2.4 Joint Continuity and Stability 193
8.3 Algorithms 196
8.3.1 Block Structures 196
8.3.2 Decomposition Methods 199
References 205
9 Portfolio Optimization with Risk Control by Stochastic Dominance Constraints 207
9.1 Introduction 207
9.2 Portfolio Problem 209
9.3 Stochastic Dominance Relations 211
9.3.1 Direct Forms 211
9.3.2 Inverse Forms 213
9.3.3 Relations to Value at Risk and Conditional Value at Risk 214
9.4 Portfolio Problem with Stochastic Dominance Constraints 217
9.4.1 Direct Formulation 217
9.4.2 Inverse Formulation 218
9.4.3 Floating Benchmark 219
9.5 Optimality Conditions and Duality Relations 220
9.5.1 Direct Form. Implied Utility Function. 220
9.5.2 Inverse Form. Implied Rank-Dependent Utility Function 222
9.6 Dominance Constraints and Coherent Measures of Risk 224
9.6.1 Coherent Measures of Risk 224
9.6.2 The Implied Measure of Risk 225
9.7 Numerical Illustration 226
References 228
10 Single-Period Mean--Variance Analysis in a Changing World 230
10.1 Introduction 230
10.2 The Model 234
10.3 Computation of Expected Discounted Utility for a Given Action Matrix 236
10.4 Computation of a (Nearly) Optimum Strategy 238
10.5 The (Near) Optimum Action Matrices 241
10.6 The M--V Heuristic 242
10.7 Comparison of Expected Utilities 246
10.8 Where Next? 247
10.9 Conclusion 249
References 253
11 Mean--Absolute Deviation Model 255
11.1 Introduction 255
11.2 Mean--Absolute Deviation Model 256
11.3 Equilibrium Relations: MAD Version CAPM 260
11.4 Computational Aspects 263
11.5 Concluding Remarks 268
References 270
12 Multistage Financial Planning Models: Integrating Stochastic Programs and Policy Simulators 272
12.1 Introduction 272
12.2 Multiperiod Models for Asset-Only Allocation 274
12.2.1 Fixed-Mix Policy Rules 274
12.2.2 Examples of Fixed-Mix Policy Rules 277
12.2.3 Practical Issues Regarding Fixed-Mix Rules 280
12.3 Application of the Dual Strategy to ALM 282
12.4 Conclusions and Future Research 286
References 288
13 Growth--Security Models and Stochastic Dominance 291
13.1 Introduction 291
13.2 Capital Accumulation Models 294
13.2.1 Asset Prices 294
13.2.2 Investment and Wealth 296
13.3 Growth and Security 298
13.3.1 Stochastic Dominance Measures 298
13.3.2 Wealth Control 302
13.4 Efficient Strategies 303
13.5 The Fundamental Problem 305
13.5.1 Continuous-Time Problem 305
13.5.2 Discrete-Time Problem 306
13.6 Conclusion 307
References 308
14 Production Planning Under Supply and Demand Uncertainty: A Stochastic Programming Approach 311
14.1 Introduction 311
14.2 A Preliminary Planning Model 313
14.2.1 Supply Progression 314
14.2.2 Demand Progression 316
14.2.3 Unmet Demand and Scrapped Inventory 317
14.2.4 Objective Function 317
14.2.5 A Deterministic Planning Model 318
14.3 Data Modeling 318
14.3.1 Production-Related Data 319
14.3.2 Demand-Related Data 321
14.3.3 Decisions Based on Partial Information 324
14.4 Conclusions 328
References 328
15 Global Climate Decisions Under Uncertainty 330
15.1 Introduction 330
15.2 A Small-Scale Example 330
15.3 Aggregating Regions to a ``One-World'' Model 334
15.4 MERGE: A Multiregion, Multitechnology Model 335
References 340
16 Control of Diffusions via Linear Programming 341
16.1 Preliminaries 341
16.1.1 Controlled Diffusion Processes 342
16.1.2 Value Functions and the HJB Equation 343
16.1.3 A Linear Programming Characterization 346
16.2 Approximate Dynamic Programming 346
16.2.1 Approximation via Basis Functions 347
16.2.2 Sampling States 348
16.2.3 Dealing with the Action Space 349
16.2.3.1 Convex Programming 349
16.2.3.2 Adaptive Constraint Selection 350
16.3 Case Studies in Portfolio Optimization 351
16.3.1 Market Model 352
16.3.2 Portfolio Choice 352
16.3.3 Utility Function 353
16.3.4 Relation to the Controlled Diffusion Framework 354
16.3.5 Special Structure 354
16.3.6 Factorization of Basis Functions 356
16.3.7 Measure and Sampling 357
16.3.8 Case Studies 358
16.3.8.1 Case Study 1: Constant Investment Opportunities 358
16.3.8.2 Case Study 2: 10-Factor Term Structure Model 360
16.4 Closing Remarks 364
References 364
Index 366