Lectures on Stochastic Programming: Modeling and Theory

1 SPbook 2009/4/21page iiiiiiiiiLectures on Stochastic programming : Modeling and TheoryAlexander ShapiroDarinka DentchevaAndrzej Ruszczy nskiTo be published bySIAM, Philadelphia, 2009. SPbook 2009/4/21page iiiiiiiiiiDarinka DentchevaDepartment of Mathematical SciencesStevens Institute of TechnologyHoboken, NJ 07030, USAA ndrzej Ruszczy nskiDepartment of Management Science and Information SystemsRutgers UniversityPiscataway, NJ 08854, USAA lexander ShapiroSchool of Industrial and Systems EngineeringGeorgia Institute of TechnologyAtlanta, GA 30332, USA SPbook 2009/4/21page iiiiiiiiiiiPrefaceThe main topic of this book are optimization problems involving uncertain parame-ters, for which Stochastic models are available.

2 Although many ways have been proposedto model uncertain quantities, Stochastic models have proved their flexibility and useful-ness in diverse areas of science. This is mainly due to solid mathematical foundationsand theoretical richness of the Theory of probability and Stochastic processes, and to soundstatistical techniques of using real problems involving Stochastic models occur in almost all areas of sci-ence and engineering, so diverse as telecommunication, medicine, or finance, to name justa few. This stimulates interest in rigorous ways of formulating, analyzing, and solving suchproblems. Due to the presence of random parameters in the model, the Theory combinesconcepts of the optimization Theory , the Theory of probability and statistics, and functionalanalysis.

3 Moreover, in recent years the Theory and methods of Stochastic programming haveundergone major advances. All these factors motivated us to present in an accessible andrigorous form contemporary models and ideas of Stochastic programming . We hope thatthe book will encourage other researchers to apply Stochastic programming models and toundertake further studies of this fascinating and rapidly developing do not try to provide a comprehensive presentation of all aspects of stochasticprogramming, but we rather concentrate on theoretical foundations and recent advances inselected areas. The book is organized in 7 chapters. The first chapter addresses modelingissues.

4 The basic concepts, such as recourse actions, chance (probabilistic) constraintsand the nonanticipativity principle, are introduced in the context of specific models. Thediscussion is aimed at providing motivation for the theoretical developments in the book,rather than practical 2 and 3 present detailed development of the Theory of two- and multistagestochastic programming problems. We analyze properties of the models, develop optimal-ity conditions and duality Theory in a rather general setting. Our analysis covers generaldistributions of uncertain parameters, and also provides special results for discrete distri-butions, which are relevant for numerical methods.

5 Due to specific properties of two- andmulti-stage Stochastic programming problems, we were able to derive many of these resultswithout resorting to methods of functional basic assumption in the Modeling and technical developments is that the proba-bility distribution of the random data is not influenced by our actions (decisions). In someapplications this assumption could be unjustified. However, dependence of probability dis-tribution on decisions typically destroys the convex structure of the optimization problemsconsidered, and our analysis exploits convexity in a significant SPbook 2009/4/21page iviiiiiiiiivPrefaceChapter 4 deals with chance (probabilistic) constraints, which appear naturally inmany applications.

6 The chapter presents the current state of the Theory , focusing on thestructure of the problems, optimality Theory , and duality. We present generalized convexityof functions and measures, differentiability, and approximations of probability attention is devoted to problems with separable chance constraints and problemswith discrete distributions. We also analyze problems with first order Stochastic dominanceconstraints, which can be viewed as problems with continuum of probabilistic of the presented results are relatively new and were not previously available in stan-dard 5 is devoted to statistical inference in Stochastic programming . The startingpoint of the analysis is that the probability distribution of the random data vector is ap-proximated by an empirical probability measure.

7 Consequently the true (expected value)optimization problem is replaced by its sample average approximation (SAA). Origins ofthis statistical inference are going back to the classical Theory of the maximum likelihoodmethod routinely used in statistics. Our motivation and applications are somewhat differ-ent, because we aim at solving Stochastic programming problems by Monte Carlo samplingtechniques. That is, the sample is generated in the computer and its size is only constrainedby the computational resources needed to solve the constructed SAA problem. One ofthe byproducts of this Theory is the complexity analysis of two and multistage stochasticprogramming.

8 Already in the case of two stage Stochastic programming the number ofscenarios (discretization points) grows exponentially with the increase of the number ofrandom parameters. Furthermore, for multistage problems, the computational complexityalso grows exponentially with the increase of the number of Chapter 6 we outline the modern Theory of risk averse approaches to stochasticprogramming. We focus on the analysis of the models, optimality Theory , and and two-stage risk-averse models are analyzed in much detail. We also outline a risk-averse approach to multistage problems, using conditional risk mappings and the principleof time consistency.

9 Chapter 7 contains formulations of technical results used in the other parts of thebook. For some of these, less known, results we give proofs, while others are referred tothe literature. The subject index can help the reader to find quickly a required definition orformulation of a needed technical important aspects of Stochastic programming have been left out. We do notdiscuss numerical methods for solving Stochastic programming problems, with exceptionof section where the Stochastic Approximation method, and its relation to complex-ity estimates, is considered. Of course, numerical methods is an important topic whichdeserves careful analysis. This, however, is a vast and separate area which should be con-sidered in a more general framework of modern optimization methods and to large extentwould lead outside the scope of this also decided not to include a thorough discussion of Stochastic integer program-ming.

10 The Theory and methods of solving Stochastic integer programming problems drawheavily from the Theory of general integer programming . Their comprehensive presentationwould entail discussion of many concepts and methods of this vast field, which would havelittle connection with the rest of the the beginning of each chapter we indicate the authors who were primarily respon-sible for writing the material, but the book is the creation of all three of us, and we share SPbook 2009/4/21page viiiiiiiiPrefacevequal responsibility for errors and inaccuracies that escaped our Shapiro, Darinka Dentcheva, and Andrzej Ruszczy nski SPbook 2009/4/21page viiiiiiiii SPbook 2009/4/21page viiiiiiiiiiContentsPrefaceiii1 Stochastic programming .