Lectures on Stochastic Programming-Model

【实例简介】
这是一本关于随机规划比较全面的书！比较难，不太容易啃，但是读了之后收获很大。这是高清版的！
To Julia, Benjamin, Daniel, Nalan, and Yael; to Tsonka Konstatin and Marek and to the memory of feliks, Maria, and dentcho 2009/8/20 pag Contents List of notations erace 1 Stochastic Programming Models Introduction 1.2 Invento 1.2.1 The news vendor problem 1.2.2 Constraints 12.3 Multistage models Multiproduct assembl 1.3.1 Two-Stage Model 1.3.2 Chance Constrained Mode Multistage model Portfolio selection 13 1.4.1 Static model 14.2 Multistage Portfolio selection 14.3 Decision rule 21 1.5 Supply Chain Network Design 22 Exercises 2 Two-Stage Problems 27 2.1 Linear Two-Stage Problems 2.1.1 Basic pi 27 2.1.2 The Expected Recourse Cost for Discrete Distributions 30 2.1.3 The Expected Recourse Cost for General Distributions.. 32 2.1.4 Optimality Conditions 垂 Polyhedral Two-Stage Problems 42 2.2.1 General Properties 42 2.2.2 Expected recourse Cost Optimality conditions 2.3 General Two-Stage Problems 8 2.3.1 Problem Formulation, Interchangeability 48 2.3.2 Convex Two-Stage Problems 2.4 Nonanticipativity 2009/8/20 page vill Contents 2.4.1 Scenario formulation 2.4.2 Dualization of Nonanticipativity Constraints 2.4.3 Nonanticipativity duality for general Distributions 2.4.4 Value of perfect inf E xercises 3 Multistage problems 3. 1 Problem Formulation 63 3.1.1 The general setting 3.1 The Linear case 65 3.1.3 Scenario trees 3.1.4 Algebraic Formulation of nonanticipativity constraints 7l Duality.... 76 3.2.1 Convex multistage problems · 76 3.2.2 Optimality Conditions 3.2.3 Dualization of Feasibility Constraints 3.2.4 Dualization of nonanticipativity Constraints Exercises 4 Optimization models with Probabilistic Constraints 87 4.1 Introduction 87 4.2 Convexity in Probabilistic Optimization 4.2 Generalized Concavity of Functions and measures 4.2.2 Convexity of probabilistically constrained sets 106 4.2.3 Connectedness of Probabilistically Constrained Sets... 113 Separable probabilistic Constraints .114 4.3 Continuity and Differentiability Properties of Distribution functions 4.3.2 p-Efficient Points .115 4.3.3 Optimality Conditions and Duality Theory 122 4 Optimization Problems with Nonseparable Probabilistic Constraints.. 132 4.4 Differentiability of Probability Functions and Optimality Conditions 133 44.2 Approximations of Nonseparable Probabilistic Constraints 13 4.5 Semi-infinite Probabilistic Problems 144 E 150 5 Statistical Inference 155 Statistical Properties of Sample Average Approximation Estimators.. 155 5.1.1 Consistency of SAA estimators 157 5.1.2 Asymptotics of the saa Optimal value 163 5.1.3 Second order as Stochastic Programs 5.2 Stoch 174 5.2.1 Consistency of solutions of the SAA Generalized Equatio 175 2009/8/20 p Contents 5.2.2 A totics of saa generalized equations estimators 177 5.3 Monte Carlo Sampling Methods 180 Exponential Rates of Convergence and Sample size Estimates in the Case of a finite Feasible se 181 5.3.2 Sample size estimates in the General Case 185 5.3.3 Finite Exponential Convergence 191 5.4 Quasi-Monte Carlo Methods 193 5. Variance-Reduction Techniques 198 Latin h mpling 198 5.5.2 Linear Control random variables method 200 ng and likelihood ratio methods 20 5.6 Validation analysis 5.6.1 Estimation of the optimality g 202 5.6.2 Statistical Testing of Optimality Conditions 207 5.7 Constrained Probler 5.7.1 Monte Carlo Sampling Approach 210 5.7.2 Validation of an Optimal solution 5.8 SAA Method Applied to Multistage Stochastic Programmin 20 5.8.1 Statistical Properties of Multistage SAA Estimators 22l 5.8.2 Complexity estimates of Multistage Programs 226 5.9 Stochastic Approximation Method 230 5.9 Classical Approach 5.9.2 Robust sA approach ..233 59.3 Mirror Descent sa method 23 5.9.4 Accuracy Certificates for Mirror Descent Sa Solutions.. 244 Exercis 6 Risk Averse Optimi 253 6.1 Introductio 6.2 Mean-Risk models .254 6.2.1 Main ideas of mean -Risk analysis 54 6.2.2 Semideviation 6.2.3 Weighted Mean Deviations from Quantiles .256 6.2.4 Average value-at-Risk 257 6.3 Coherent risk measures 261 6.3.1 Differentiability Properties of Risk Measures 265 6.3.2 Examples of risk Measures ..269 6.3.3 Law invariant risk measures and Stochastic orders 279 6.3.4 Relation to Ambiguous Chance Constraints 285 6.4 Optimization of risk measures .288 6.4.1 Dualization of Nonanticipativity Constraints 291 6.4.2 Examples... 295 6.5 Statistical Properties of Risk measures 6.5.I Average value-at-Ris 6.52 Absolute semideviation risk measure 301 Von mises statistical functionals 304 6.6 The problem of moments 306 中2009/8/20 page x Contents 6.7 Multistage Risk Averse Optimization 308 6.7.1 Scenario tree formulation 308 6.7.2 Conditional risk mappings 315 6.7.3 Risk Averse multistage Stochastic Programming 318 Exercises 328 7 Background material 333 7.1 Optimization and Convex Analysis ..334 Directional Differentiability 334 7.1.2 Elements of Convex Analysis 336 7.1.3 Optimization and duality 339 7.1.4 Optimality Conditions............. 346 7.1.5 Perturbation analysis 351 7.1.6 Epiconvergence 357 2 Probability 359 7.2.1 Probability spaces and random variables 7.2.2 Conditional Probability and Conditional Expectation... 363 72.3 Measurable multifunctions and random functions 365 7.2.4 Expectation Functions .368 7.2.5 Uniform Laws of Large Numbers ...,,374 7.2.6 Law of Large Numbers for Random Sets and Subdifferentials 379 7.2.7 Delta method 7.2.8 Exponential Bounds of the Large Deviations Theory 387 7.2.9 Uniform Exponential Bounds 7.3 Elements of Functional analysis 399 7.3 Conjugate duality and differentiability.......... 401 7.3.2 Lattice structure 403 405 8 Bibliographical remarks 407 Bi ibliography 415 Index 431 2009/8/20 page List of Notations equal by definition, 333 IR", n-dimensional space, 333 A, transpose of matrix(vector)A, 333 6I, domain of the conjugate of risk mea- C(X) space of continuous functions, 165 sure p, 262 CK, polar of cone C, 337 Cn, the space of nonempty compact sub- C(v,R"), space of continuously differ- sets of r 379 entiable mappings,176 set of probability density functions, I Fr influence function. 304 2 L, orthogonal of (linear) space L, 41 Sz, set of contact points, 399 0(1), generic constant, 188 b(k; a, N), cdf of binomial distribution, Op(), term, 382 214 S, the set of &-optimal solutions of the o, distance generating function, 236 true problem, 18 g(x), right-hand-side derivative, 297 Va(a), Lebesgue measure of set A C Rd Cl(A), topological closure of set A, 334 195 conv(C), convex hull of set C, 337 W,(U), space of Lipschitz continuous Corr(X, Y), correlation of X and Y 200 functions. 166. 353 CoV(X, Y, covariance of X and y, 180 [a]+=max{a,0},2 ga, weighted mean deviation, 256 IA(, indicator function of set A, 334 Sc(, support function of set C, 337 n(n.f. p). space. 399 A(x), set of dist(x, A), distance from point x to set A e multipliers vectors 334 348 dom f, domain of function f, 333 N(μ,∑), nonmal distribution,16 Nc, normal cone to set C, 337 dom 9, domain of multifunction 9, 365 IR, set of extended real numbers. 333 o(z), cdf of standard normal distribution, epif, epigraph of function f, 333 IIx, metric projection onto set X, 231 epiconvergence, 377 convergence in distribution, 163 SN, the set of optimal solutions of the 0(x,h) d order tangent set 348 SAA problem. 156 AVOR. Average value-at-Risk. 258 Sa, the set of 8-optimal solutions of the f, set of probability measures, 306 SAA problem. 181 ID(A, B), deviation of set A from set B n,N, optimal value of the Saa problem, 334 156 IDIZ], dispersion measure of random vari- N(x), sample average function, 155 able 7. 254 1A(, characteristic function of set A, 334 吧, expectation,361 int(C), interior of set C, 336 TH(A, B), Hausdorff distance between sets La」, integer part of a∈R,219 A and B. 334 Isc f, lower semicontinuous hull of func N, set of positive integers, 359 tion f, 333 2009/8/20 page List of notations Rc, radial cone to set C, 337 C, tangent cone to set C, 337 V-f(r), Hessian matrix of second order partial derivatives, 179 a. subdifferential. 338 a, Clarke generalized gradient, 336 as, epsilon subdifferential, 380 pos w, positive hull of matrix W, 29 Pr(A), probability of event A, 360 ri relative interior. 337 upper semideviation, 255 Le, lower semideviation, 255 @R. Value-at-Risk. 25 Var[X], variance of X, 14 9, optimal value of the true problem, 156 5=(51,……,5), history of the process, {a,b},186 r, conjugate of function/, 338 f(x, d), generalized directional deriva- g(x, h), directional derivative, 334 O,(, term, 382 p-efficient point, 116 lid, independently identically distributed, 156 2009/8/20 page xlll Preface The main topic of this book is optimization problems involving uncertain parameters for which stochastic models are available. Although many ways have been proposed to model uncertain quantities stochastic models have proved their flexibility and usefulness in diverse areas of science. This is mainly due to solid mathematical foundations and theoretical richness of the theory of probability stochastic processes, and to sound statistical techniques of using real data Optimization problems involving stochastic models occur in almost all areas of science and engineering, from telecommunication and medicine to finance This stimulates interest in rigorous ways of formulating, analyzing, and solving such problems. Due to the presence of random parameters in the model, the theory combines concepts of the optimization theory, the theory of probability and statistics, and functional analysis. Moreover, in recent years the theory and methods of stochastic programming have undergone major advances. all these factors motivated us to present in an accessible and rigorous form contemporary models and ideas of stochastic programming. We hope that the book will encourage other researchers to apply stochastic programming models and to undertake further studies of this fascinatin and rapidly developing area We do not try to provide a comprehensive presentation of all aspects of stochastic programming, but we rather concentrate on theoretical foundations and recent advances in selected areas. The book is organized into seven chapters The first chapter addresses mod eling issues. The basic concepts, such as recourse actions, chance(probabilistic)constraints and the nonanticipativity principle, are introduced in the context of specific models. The discussion is aimed at providing motivation for the theoretical developments in the book, rather than practical recommendations Chapters 2 and 3 present detailed development of the theory of two-stage and multi stage stochastic programming problems. We analyze properties of the models and develop optimality conditions and duality theory in a rather general setting. Our analysis covers general distributions of uncertain parameters and provides special results for discrete distri butions, which are relevant for numerical methods. Due to specific properties of two- and multistage stochastic programming problems, we were able to derive many of these results without resorting to methods of functional analvsis The 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 some applications, this assumption could be unjustified. However, dependence of probability dis- tribution on decisions typically destroys the convex structure of the optimization problems considered, and our analysis exploits convexity in a significant way 【实例截图】
【核心代码】