Preface 5
George B. Dantzig and Optimization UnderUncertainty 9
References 13
Contents 15
List of Figures 17
Contributors 19
1 Linear Programming Under Uncertainty 22
George B. Dantzig 22
Example 1. Minimum Expected Cost Diet 22
Example 2. Shipping to an Outlet to Meet an Uncertain Demand 23
Example 3. A Three-Stage Case 24
Example 4. A Class of Two-Stage Problems 24
Example 5. The Two-Stage Problem with General Linear Structure 28
Example 6. The Multistage Problem with General Linear Structure 30
Solution for Example 2. Shipping to an Outlet to Meetan Uncertain Demand 31
Solution for Example 5. The General Two-Stage Case 32
References 32
2 A Probabilistic Lower Bound for Two-Stage Stochastic Programs 33
George B. Dantzig and Gerd Infanger 33
2.1 Introduction 33
2.2 The Problem 34
2.3 Benders Decomposition 36
2.4 Probabilistic Lower Bound 39
2.4.1 Cut Generation Using Sampling 39
2.4.2 Stochastic Benders Algorithm 40
2.4.3 First-Stage Decision x=l, Upper Confidence Interval for z* 40
2.4.4 Lower Confidence Interval for z* 41
2.4.5 The Distribution of the Error Term 43
2.4.6 Worst-Case Lower Bound for z* 44
2.4.7 Conservative Lower Bound for z* 45
2.5 Test 48
References 54
3 Simulation-Based Optimality Tests for Stochastic Programs 56
G眉zin Bayraksan, David P. Morton, and Amit Partani 56
3.1 Introduction 56
3.2 Background and Motivation 58
3.3 Multiple Replications Procedure 60
3.4 Single and Two Replication Procedures 64
3.5 Bias Reduction 66
3.6 Variance Reduction 69
3.7 Conclusions 71
References 72
4 Stochastic Decomposition and Extensions 75
Suvrajeet Sen, Zhihong Zhou, and Kai Huang 75
4.1 Introduction 75
4.2 Stochastic Decomposition 76
4.3 Extensions of Regularized SD 79
4.3.1 A Sufficient Condition for a Unique Limit 79
4.3.2 SD With Resampling 80
4.3.3 Preliminary Computational Results 82
4.4 Conclusion 83
References 84
5 Barycentric Bounds in Stochastic Programming: Theory and Application 85
Karl Frauendorfer, Daniel Kuhn, and Michael Sch眉rle 85
5.1 Introduction 85
5.2 Problem Formulation 87
5.3 Regularity Conditions 90
5.4 Barycentric Probability Measures 92
5.5 Bounds for Stochastic Programs 96
5.6 Application in Financial Risk Management 100
5.6.1 Formulation as Multistage Stochastic Program 101
5.6.2 Risk Factor Models 102
5.6.3 Check of Regularity Conditions 104
5.6.4 Numerical Solution 107
5.7 Conclusions 110
References 112
6 Stochastic Programming Approximations Using Limited Moment Information, with Application to Asset Allocation 115
N. Chanaka P. Edirisinghe 115
6.1 Introduction 115
6.1.1 Bound-Based Approximations 117
6.1.2 Bounds Using Generalized Moment Problems 119
6.2 Bounding the Expected Recourse Function 121
6.2.1 First-Order Moment Bounds 122
6.2.2 Tightening First-Moment Bounds 126
6.3 Second-Order Moment Bounds 130
6.3.1 Simplicial Mean--Covariance Approximation 132
6.3.2 Tightening Second-Order Bounds 135
6.3.3 Higher Order Moment Upper Bounds in Convex Case 136
6.4 Simplicial Sequential Solution (SSS) 138
6.4.1 Partitioning and Convergence 139
6.4.2 Partitioning Strategies and Cell Redefining 141
6.4.2.1 Edge Selection 141
6.4.2.2 Cell Redefining 143
6.5 Asset Allocation Application 144
6.5.1 Scenario Clustering and Sensitivity Analysis 148
6.5.2 Efficient Frontiers and Transaction Costs 148
6.6 Concluding Remarks 153
References 153
7 Stability and Scenario Trees for Multistage Stochastic Programs 157
Holger Heitsch and Werner R枚misch 157
7.1 Introduction 157
7.2 Stability of Multistage Models 159
7.3 Generating Scenario Trees 172
7.4 Numerical Experience 177
7.4.1 Adapting a Statistical Model 177
7.4.2 Construction of Input Scenario Trees 178
References 181
8 Risk Aversion in Two-Stage Stochastic Integer Programming 183
R眉diger Schultz 183
8.1 Introduction 183
8.2 Structural Results 186
8.2.1 Prerequisites: Value Functions and Expectation Models 186
8.2.2 Risk Measures 188
8.2.3 Structure of Objective Functions 189
8.2.4 Joint Continuity and Stability 192
8.3 Algorithms 195
8.3.1 Block Structures 195
8.3.2 Decomposition Methods 198
References 204
9 Portfolio Optimization with Risk Control by Stochastic Dominance Constraints 206
Darinka Dentcheva and Andrzej Ruszczynski 206
9.1 Introduction 206
9.2 Portfolio Problem 208
9.3 Stochastic Dominance Relations 210
9.3.1 Direct Forms 210
9.3.2 Inverse Forms 212
9.3.3 Relations to Value at Risk and Conditional Value at Risk 213
9.4 Portfolio Problem with Stochastic Dominance Constraints 216
9.4.1 Direct Formulation 216
9.4.2 Inverse Formulation 217
9.4.3 Floating Benchmark 218
9.5 Optimality Conditions and Duality Relations 219
9.5.1 Direct Form. Implied Utility Function. 219
9.5.2 Inverse Form. Implied Rank-Dependent Utility Function 221
9.6 Dominance Constraints and Coherent Measures of Risk 223
9.6.1 Coherent Measures of Risk 223
9.6.2 The Implied Measure of Risk 224
9.7 Numerical Illustration 225
References 227
10 Single-Period Mean--Variance Analysis in a Changing World 229
Harry M. Markowitz and Erik L. van Dijk 229
10.1 Introduction 229
10.2 The Model 233
10.3 Computation of Expected Discounted Utility for a Given Action Matrix 235
10.4 Computation of a (Nearly) Optimum Strategy 237
10.5 The (Near) Optimum Action Matrices 240
10.6 The M--V Heuristic 241
10.7 Comparison of Expected Utilities 245
10.8 Where Next? 246
10.9 Conclusion 248
References 252
11 Mean--Absolute Deviation Model 254
Hiroshi Konno 254
11.1 Introduction 254
11.2 Mean--Absolute Deviation Model 255
11.3 Equilibrium Relations: MAD Version CAPM 259
11.4 Computational Aspects 262
11.5 Concluding Remarks 267
References 269
12 Multistage Financial Planning Models: Integrating Stochastic Programs and Policy Simulators 271
John M. Mulvey and Woo Chang Kim 271
12.1 Introduction 271
12.2 Multiperiod Models for Asset-Only Allocation 273
12.2.1 Fixed-Mix Policy Rules 273
12.2.2 Examples of Fixed-Mix Policy Rules 276
12.2.3 Practical Issues Regarding Fixed-Mix Rules 279
12.3 Application of the Dual Strategy to ALM 281
12.4 Conclusions and Future Research 285
References 287
13 Growth--Security Models and Stochastic Dominance 290
Leonard C. MacLean, Yonggan Zhao, and William T. Ziemba 290
13.1 Introduction 290
13.2 Capital Accumulation Models 293
13.2.1 Asset Prices 293
13.2.2 Investment and Wealth 295
13.3 Growth and Security 297
13.3.1 Stochastic Dominance Measures 297
13.3.2 Wealth Control 301
13.4 Efficient Strategies 302
13.5 The Fundamental Problem 304
13.5.1 Continuous-Time Problem 304
13.5.2 Discrete-Time Problem 305
13.6 Conclusion 306
References 307
14 Production Planning Under Supply and Demand Uncertainty: A Stochastic Programming Approach 310
Julia L. Higle and Karl G. Kempf 310
14.1 Introduction 310
14.2 A Preliminary Planning Model 312
14.2.1 Supply Progression 313
14.2.2 Demand Progression 315
14.2.3 Unmet Demand and Scrapped Inventory 316
14.2.4 Objective Function 316
14.2.5 A Deterministic Planning Model 317
14.3 Data Modeling 317
14.3.1 Production-Related Data 318
14.3.2 Demand-Related Data 320
14.3.3 Decisions Based on Partial Information 323
14.4 Conclusions 327
References 327
15 Global Climate Decisions Under Uncertainty 329
Alan S. Manne 329
15.1 Introduction 329
15.2 A Small-Scale Example 329
15.3 Aggregating Regions to a ``One-World'' Model 333
15.4 MERGE: A Multiregion, Multitechnology Model 334
References 339
16 Control of Diffusions via Linear Programming 340
Jiarui Han and Benjamin Van Roy 340
16.1 Preliminaries 340
16.1.1 Controlled Diffusion Processes 341
16.1.2 Value Functions and the HJB Equation 342
16.1.3 A Linear Programming Characterization 345
16.2 Approximate Dynamic Programming 345
16.2.1 Approximation via Basis Functions 346
16.2.2 Sampling States 347
16.2.3 Dealing with the Action Space 348
16.2.3.1 Convex Programming 348
16.2.3.2 Adaptive Constraint Selection 349
16.3 Case Studies in Portfolio Optimization 350
16.3.1 Market Model 351
16.3.2 Portfolio Choice 351
16.3.3 Utility Function 352
16.3.4 Relation to the Controlled Diffusion Framework 353
16.3.5 Special Structure 353
16.3.6 Factorization of Basis Functions 355
16.3.7 Measure and Sampling 356
16.3.8 Case Studies 357
16.3.8.1 Case Study 1: Constant Investment Opportunities 357
16.3.8.2 Case Study 2: 10-Factor Term Structure Model 359
16.4 Closing Remarks 363
References 363
Index 365