Stochastic_Programming-ed_Ruszczynski-Shapiro.pdf

(4856 KB) Pobierz
583798193 UNPDF
Preface
The area of stochastic programming was created in the middle of the last
century, following fundamental achievements in linear and nonlinear
programming. While it has been quickly realized that the presence of
uncertainty in optimization models creates a need for new problem formul-
ations, many years have passed until the basic stochastic programming models
have been formulated and analyzed. Today, stochastic programming theory
offers a variety of models to address the presence of random data in
optimization problems: chance-constrained models, two- and multi-stage
models, models involving risk measures. New problem formulations appear
almost every year and this variety is one of the strengths of the field.
Stochastic programming can be quite involved, starting with sophisticated
modeling and is based on advanced mathematical tools such as nonsmooth
calculus, abstract optimization, probability theory and statistical techniques.
One of the objectives of this Handbook is to bring these techniques together
and to show how they can be used to analyze and solve stochastic program-
ming models.
Because of the inherent diculty of stochastic optimization problems, it
took a long time until e cient solution methods have been developed. In the
last two decades a dramatic change in our abilities to solve stochastic
programming problems took place. It is partially due to the progress in large
scale linear and nonlinear programming, in nonsmooth optimization and
integer programming, but mainly it follows the development of techniques
exploiting specific properties of stochastic programming problems. Computa-
tional advances are also due to modern parallel processing technology.
Nowadays we can solve stochastic optimization problems involving tens of
millions of variables and constraints.
Our intention was to bring together leading experts in the most
important sub-fields of stochastic programming to present a rigorous
overview of basic models, methods, and applications of stochastic pro-
gramming. We hope that this Handbook will prove useful to researchers,
students, engineers and economists, who encounter in their work optimiza-
tion problems involving uncertainty. We also hope that our work will
encourage many to undertake research in this exciting and practically impor-
tant field.
v
vi
Preface
We want to thank all the Authors involved in this project for their
contributions. We also want to thank Darinka Dentcheva, Shabbir Ahmed,
Tito Homem-de-Mello and Anton Kleywegt, who have helped us to review
and improve several chapters of this Handbook.
Andrzej Ruszczyn´ ski and Alexander Shapiro
December 2002.
Contents
Preface
v
CHAPTER 1
Stochastic Programming Models
A. Ruszczyn´ ski and A. Shapiro
1
1. Introduction
1
2. Two-stage models
11
3. Multistage models
22
4. Robust and min–max approaches to stochastic optimization
48
5. Appendix
55
6. Bibliographic notes
62
References
63
CHAPTER 2
Optimality and Duality in Stochastic Programming
A. Ruszczyn´ ski and A. Shapiro
65
1. Expectation functions
65
2. Two-stage stochastic programming problems
72
3. Multistage models
93
4. Optimality conditions, basic case
97
5. Optimality conditions for multistage models
99
6. Duality, basic case
103
7. Duality for multistage stochastic programs
115
8. Min–max stochastic optimization
122
9. Appendix
126
10. Bibliographic notes
137
References
138
CHAPTER 3
Decomposition Methods
A. Ruszczyn ´ ski
141
1. Introduction
141
2. The cutting plane method
144
3. Regularized decomposition
161
4. Trust region methods
175
vii
viii
Contents
5. Nested cutting plane methods for multistage problems
180
6. Introduction to dual methods
187
7. The dual cutting plane method
192
8. The augmented Lagrangian method
195
9. Progressive hedging
200
10. Bibliographic notes
207
References
209
CHAPTER 4
Stochastic Integer Programming
F.V. Louveaux and R. Schultz
213
1. Introduction
213
2. Structural properties
215
3. Algorithms
235
References
264
CHAPTER 5
Probabilistic Programming
A. Pre ´ kopa
267
1. Model constructions
267
2. Convexity theory
272
3. Numerical solution of probabilistic constrained stochastic
programming problems
287
4. Dynamic type stochastic programming problems with
probabilistic constraints
309
5. Bounding, approximation and simulation of probabilities
311
6. Duality and stability
334
7. Selected applications
338
References
345
CHAPTER 6
Monte Carlo Sampling Methods
A. Shapiro
353
1. Introduction
353
2. Statistical properties of SAA estimators
357
3. Exponential rates of convergence
371
4. Validation analysis
382
5. Variance reduction techniques
393
6. Multistage stochastic programming
399
7. Stochastic generalized equations
410
8. Appendix
416
9. Bibliographic notes
421
References
423
Contents
ix
CHAPTER 7
Stochastic Optimization and Statistical Inference
G.Ch. Pflug
427
1. Uncertain and ambiguous optimization problems
427
2. The empirical problem
430
3. Properties of statistical estimates
433
4. Risk functionals and Lipschitz properties
445
5. Arithmetic means of of i.i.d. random variables
449
6. Entropic sizes of stochastic programs
458
7. Epiconvergence
461
8. Epipointwise convergence for stochastic programs
467
9. Asymptotic stochastic programs
470
10. Bibliographic remarks
479
References
480
CHAPTER 8
Stability of Stochastic Programming Problems
W. Ro¨ misch
483
1. Introduction
483
2. General stability results
488
3. Stability of two-stage and chance constrained programs
510
4. Approximations of stochastic programs
538
5. Bibliographical notes
547
Acknowledgements
548
References
549
CHAPTER 9
Stochastic Programming in Transportation and Logistics
W.B. Powell and H. Topaloglu
555
1. Introduction
555
2. Applications and issues
557
3. Modeling framework
564
4. A case study: freight car distribution
576
5. The two-stage resource allocation problem
579
6. Multistage resource allocation problems
609
7. Some experimental results
623
8. A list of extensions
627
9. Implementing stochastic programming models in the
real world
629
10. Bibliographic notes
631
References
633

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin