Infanger Stochastic Programming

The State of the Art In Honor of George B. Dantzig
1. Auflage 2010
ISBN: 978-1-4419-1642-6
Verlag: Springer US
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 150, 362 Seiten

Reihe: International Series in Operations Research & Management Science

From the Preface... The preparation of this book started in 2004, when George B. Dantzig and I, following a long-standing invitation by Fred Hillier to contribute a volume to his International Series in Operations Research and Management Science, decided finally to go ahead with editing a volume on stochastic programming. The field of stochastic programming (also referred to as optimization under uncertainty or planning under uncertainty) had advanced significantly in the last two decades, both theoretically and in practice. George Dantzig and I felt that it would be valuable to showcase some of these advances and to present what one might call the state-of- the-art of the field to a broader audience. We invited researchers whom we considered to be leading experts in various specialties of the field, including a few representatives of promising developments in the making, to write a chapter for the volume. Unfortunately, to the great loss of all of us, George Dantzig passed away on May 13, 2005. Encouraged by many colleagues, I decided to continue with the book and edit it as a volume dedicated to George Dantzig. Management Science published in 2005 a special volume featuring the 'Ten most Influential Papers of the first 50 Years of Management Science.' George Dantzig's original 1955 stochastic programming paper, 'Linear Programming under Uncertainty,' was featured among these ten. Hearing about this, George Dantzig suggested that his 1955 paper be the first chapter of this book. The vision expressed in that paper gives an important scientific and historical perspective to the book.Gerd Infanger

Autoren/Hrsg.

Infanger, Gerd

Inhaltsverzeichnis

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