Lectures on Stochastic Programming-Model
这是一本关于随机规划比较全面的书！比较难，不太容易啃，但是读了之后收获很大。这是高清版的！To Julia, Benjamin, Daniel, Nalan, and Yael;to Tsonka Konstatin and Marekand to the memory of feliks, Maria, and dentcho2009/8/20pagContentsList of notationserace1 Stochastic Programming ModelsIntroduction1.2 Invento1.2.1The news vendor problem1.2.2Constraints12.3Multistage modelsMultiproduct assembl1.3.1Two-Stage Model1.3.2Chance Constrained ModeMultistage modelPortfolio selection131.4.1Static model14.2Multistage Portfolio selection14.3Decision rule211.5 Supply Chain Network Design22Exercises2 Two-Stage Problems272.1 Linear Two-Stage Problems2.1.1Basic pi272.1.2The Expected Recourse Cost for Discrete Distributions 302.1.3The Expected Recourse Cost for General Distributions.. 322.1.4Optimality Conditions垂Polyhedral Two-Stage Problems422.2.1General Properties422.2.2Expected recourse CostOptimality conditions2.3 General Two-Stage Problems82.3.1Problem Formulation, Interchangeability482.3.2Convex Two-Stage Problems2.4 Nonanticipativity2009/8/20page villContents2.4.1Scenario formulation2.4.2Dualization of Nonanticipativity Constraints2.4.3Nonanticipativity duality for general Distributions2.4.4Value of perfect infExercises3 Multistage problems3. 1 Problem Formulation633.1.1The general setting3.1The Linear case653.1.3Scenario trees3.1.4Algebraic Formulation of nonanticipativity constraints 7lDuality....763.2.1Convex multistage problems·763.2.2Optimality Conditions3.2.3Dualization of Feasibility Constraints3.2.4Dualization of nonanticipativity ConstraintsExercises4 Optimization models with Probabilistic Constraints874.1 Introduction874.2 Convexity in Probabilistic Optimization4.2Generalized Concavity of Functions and measures4.2.2Convexity of probabilistically constrained sets1064.2.3Connectedness of Probabilistically Constrained Sets... 113Separable probabilistic Constraints.1144.3Continuity and Differentiability Properties ofDistribution functions4.3.2p-Efficient Points.1154.3.3Optimality Conditions and Duality Theory1224 Optimization Problems with Nonseparable Probabilistic Constraints.. 1324.4Differentiability of Probability Functions and OptimalityConditions13344.2Approximations of Nonseparable ProbabilisticConstraints134.5 Semi-infinite Probabilistic Problems144E1505 Statistical Inference155Statistical Properties of Sample Average Approximation Estimators.. 1555.1.1Consistency of SAA estimators1575.1.2Asymptotics of the saa Optimal value1635.1.3Second order asStochastic Programs5.2 Stoch1745.2.1Consistency of solutions of the SAA GeneralizedEquatio1752009/8/20pContents5.2.2Atotics of saa generalized equations estimators 1775.3 Monte Carlo Sampling Methods180Exponential Rates of Convergence and Sample sizeEstimates in the Case of a finite Feasible se1815.3.2Sample size estimates in the General Case1855.3.3Finite Exponential Convergence1915.4 Quasi-Monte Carlo Methods1935.Variance-Reduction Techniques198Latin hmpling1985.5.2Linear Control random variables method200ng and likelihood ratio methods 205.6 Validation analysis5.6.1Estimation of the optimality g2025.6.2Statistical Testing of Optimality Conditions2075.7Constrained Probler5.7.1Monte Carlo Sampling Approach2105.7.2Validation of an Optimal solution5.8 SAA Method Applied to Multistage Stochastic Programmin205.8.1Statistical Properties of Multistage SAA Estimators22l5.8.2Complexity estimates of Multistage Programs2265.9 Stochastic Approximation Method2305.9Classical Approach5.9.2Robust sA approach..23359.3Mirror Descent sa method235.9.4Accuracy Certificates for Mirror Descent Sa Solutions.. 244Exercis6 Risk Averse Optimi2536.1 Introductio6.2 Mean-Risk models.2546.2.1Main ideas of mean -Risk analysis546.2.2Semideviation6.2.3Weighted Mean Deviations from Quantiles.2566.2.4Average value-at-Risk2576.3 Coherent risk measures2616.3.1Differentiability Properties of Risk Measures2656.3.2Examples of risk Measures..2696.3.3Law invariant risk measures and Stochastic orders2796.3.4Relation to Ambiguous Chance Constraints2856.4 Optimization of risk measures.2886.4.1Dualization of Nonanticipativity Constraints2916.4.2Examples...2956.5 Statistical Properties of Risk measures6.5.IAverage value-at-Ris6.52Absolute semideviation risk measure301Von mises statistical functionals3046.6The problem of moments306中2009/8/20page xContents6.7 Multistage Risk Averse Optimization3086.7.1Scenario tree formulation3086.7.2Conditional risk mappings3156.7.3Risk Averse multistage Stochastic Programming318Exercises3287 Background material3337.1 Optimization and Convex Analysis..334Directional Differentiability3347.1.2Elements of Convex Analysis3367.1.3Optimization and duality3397.1.4Optimality Conditions.............3467.1.5Perturbation analysis3517.1.6Epiconvergence3572 Probability3597.2.1Probability spaces and random variables7.2.2Conditional Probability and Conditional Expectation... 36372.3Measurable multifunctions and random functions3657.2.4Expectation Functions.3687.2.5Uniform Laws of Large Numbers...,,3747.2.6Law of Large Numbers for Random Sets andSubdifferentials3797.2.7Delta method7.2.8Exponential Bounds of the Large Deviations Theory3877.2.9Uniform Exponential Bounds7.3 Elements of Functional analysis3997.3Conjugate duality and differentiability.......... 4017.3.2Lattice structure4034058 Bibliographical remarks407Biibliography415Index4312009/8/20pageList of Notationsequal by definition, 333IR", n-dimensional space, 333A, transpose of matrix(vector)A, 3336I, domain of the conjugate of risk mea-C(X) space of continuous functions, 165sure p, 262CK, polar of cone C, 337Cn, the space of nonempty compact sub-C(v,R"), space of continuously differ-sets of r 379entiable mappings,176set of probability density functions,I Fr influence function. 3042L, orthogonal of (linear) space L, 41Sz, set of contact points, 3990(1), generic constant, 188b(k; a, N), cdf of binomial distribution,Op(), term, 382214S, the set of &-optimal solutions of theo, distance generating function, 236true problem, 18g(x), right-hand-side derivative, 297Va(a), Lebesgue measure of set A C RdCl(A), topological closure of set A, 334195conv(C), convex hull of set C, 337W,(U), space of Lipschitz continuousCorr(X, Y), correlation of X and Y 200functions. 166. 353CoV(X, Y, covariance of X and y, 180[a]+=max{a,0},2ga, weighted mean deviation, 256IA(, indicator function of set A, 334Sc(, support function of set C, 337n(n.f. p). space. 399A(x), set ofdist(x, A), distance from point x to set Ae multipliers vectors334348dom f, domain of function f, 333N(μ,∑), nonmal distribution,16Nc, normal cone to set C, 337dom 9, domain of multifunction 9, 365IR, set of extended real numbers. 333o(z), cdf of standard normal distribution,epif, epigraph of function f, 333IIx, metric projection onto set X, 231epiconvergence, 377convergence in distribution, 163SN, the set of optimal solutions of the0(x,h)d order tangent set 348SAA problem. 156AVOR. Average value-at-Risk. 258Sa, the set of 8-optimal solutions of thef, set of probability measures, 306SAA problem. 181ID(A, B), deviation of set A from set Bn,N, optimal value of the Saa problem,334156IDIZ], dispersion measure of random vari-N(x), sample average function, 155able 7. 2541A(, characteristic function of set A, 334吧, expectation,361int(C), interior of set C, 336TH(A, B), Hausdorff distance between setsLa」, integer part of a∈R,219A and B. 334Isc f, lower semicontinuous hull of funcN, set of positive integers, 359tion f, 3332009/8/20pageList of notationsRc, radial cone to set C, 337C, tangent cone to set C, 337V-f(r), Hessian matrix of second orderpartial derivatives, 179a. subdifferential. 338a, Clarke generalized gradient, 336as, epsilon subdifferential, 380pos w, positive hull of matrix W, 29Pr(A), probability of event A, 360ri relative interior. 337upper semideviation, 255Le, lower semideviation, 255@R. Value-at-Risk. 25Var[X], variance of X, 149, optimal value of the true problem, 1565=(51,……,5), history of the process,{a,b},186r, conjugate of function/, 338f(x, d), generalized directional deriva-g(x, h), directional derivative, 334O,(, term, 382p-efficient point, 116lid, independently identically distributed,1562009/8/20page xlllPrefaceThe main topic of this book is optimization problems involving uncertain parametersfor which stochastic models are available. Although many ways have been proposed tomodel uncertain quantities stochastic models have proved their flexibility and usefulnessin diverse areas of science. This is mainly due to solid mathematical foundations andtheoretical richness of the theory of probabilitystochastic processes, and to soundstatistical techniques of using real dataOptimization problems involving stochastic models occur in almost all areas of scienceand engineering, from telecommunication and medicine to finance This stimulates interestin rigorous ways of formulating, analyzing, and solving such problems. Due to the presenceof 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 thetheory and methods of stochastic programming have undergone major advances. all thesefactors motivated us to present in an accessible and rigorous form contemporary models andideas of stochastic programming. We hope that the book will encourage other researchersto apply stochastic programming models and to undertake further studies of this fascinatinand rapidly developing areaWe 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 into seven chapters The first chapter addresses modeling issues. 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 recommendationsChapters 2 and 3 present detailed development of the theory of two-stage and multistage stochastic programming problems. We analyze properties of the models and developoptimality conditions and duality theory in a rather general setting. Our analysis coversgeneral distributions of uncertain parameters and provides special results for discrete distributions, which are relevant for numerical methods. Due to specific properties of two- andmultistage stochastic programming problems, we were able to derive many of these resultswithout resorting to methods of functional analvsisThe 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 way
- 2020-12-09下载
- 积分：1
控制理论中的代数基础
中科大的教材，属于基础类的数学课程，课本教材简单通俗易懂，望大家下载啊前言在自动控制专业中,线性代数或矩阵论是一个重要的数学基础.比如,矩阵范数、矩阵函数及矩阵微分方程是线性系统理论必不可少的预备知识,线性系统多变量频域法建立在多项式矩阵及有理分式矩阵理论基础上,现代鲁棒控制方法可以采用线性矩阵不等式工具来实现.即便刈于非线性系统,除了需要引入更深刻的数学工具之外,矩阵分析方法仍是不可或缺的手段因此,一些人学自动控制专业特别将矩阵分析纳入研究生课程体系,就是要在人学本科线性代数的基础上,进一步增加内容以符合控制相关学科的专业需求作者在中国科学技术大学自动化系从事“控制理论中的代数基础”教学多年从选择现成教材到开始自编讲义,讲义形式从电子版到胶印版,内容在不断扩充中现在讲义内容己超出60至80学时的教学量,教师可以选择一部分讲授,其余部分可以计学生自学或作为可随时查阅的参考书.本书涉及范围较广,编写中参阅了不少经典文献.编写风格上追求叙述简洁、注重逻辑体系严谨性.因篇幅所限及个人倾向性,本书很少讨论相关的计算方法,虽然算法问题也很重要.如果作为教学用书,教师可自行选择讲授范围并增加一些实例.本书也可作为其它专业研究生、工程师和科研人员的参考书.本书共分八章.第一、二章扼要介绍抽象代数基础.第三、四章讲述线性空间与线性映射,特别是不变子空间分解定理等.第五章从多项式矩阵入手,讨论多项式矩阵 Smith标准形和复矩阵 ordan标准形,并介绍投影矩阵、正规矩阵和Hermite二次型等.第六章介绍矩阵范数、矩阵级数和矩阵函数,并讨论线性系统的稳定性、可控性与可观性.第七章包括各类广义逆矩阵、矩阵方程及矩阵不等式.第八章讨论多项式矩阵的互质、分式矩阵的既约分解,以及线性系统的零极点与实现理论.在本书编写过程中,承蒙中国科学技术大学自动化系各位同仁的支持,特别是奚宏生教授、吴刚教授的鼓励与支持.在本书排版与定稿过程中,中国科学技术大学出版社张莹莹、沈轩和韩继伟等编辑提岀了宝贵意见并给予帮助.硏究生魏波、王兴虎和陈珊杰对书稿进行了仔细校对.作者在此一并深表感谢.限于作者水平书中不妥与错误之处在所难免,敬请读者批评指正.作者2008年春lI目录第一章集合、映射与关系31.1集合1.2映射习题1-11.3代数运算1267831.4代数关系31.5等价类10习题12第二章基本代数系统142.1群142.2环与域162.2.1环162.2.2域..19§23代数系的同态习题2-124子群与陪集习题22§25环的理想§2.6多项式环§27同态基本定理423602习题2-3第三章线性空间与线性映射44531线性空间44532线性空间的基与维数533线性映射.52习题3-15734商空间58535对偶空间目录3.6内积空间37酉变换习题3-2..第四章线性变换与空间分解75§41不变子空间7542特征值问题75§43投影算子77§4.4最小多项式§4.5空间互质分解844.6空间循环分解87习题4198第五章相似变换与酉变换1015.1多项式矩阵1012 Smith标准形10653 Jordan标准形110习题5-111854正交投影与正规矩阵.12055二次型127§5.6奇值分解134习题52..137第六章矩阵范数与矩阵函数14056.1向量范数14056.2矩阵范数.146563向量和矩阵的极限153§6.4特征值与谱半径的估计158习题6-1160§6.5矩阵幂级数16266矩阵函数.164§6.7函数向量或矩阵的微积分173§68常用矩阵函数176§6.9线性系统的稳定性、可控性与可观性179目录习题62187第七章广义逆矩阵、矩阵方程189§7.1广义逆矩阵..18987.2 Penrose- Moore厂义逆矩阵193§7.3 Drazin逆与群逆习题71....20374矩阵的 Kronecker积.20437.5线性矩阵不等式209习题72214第八章多项式矩阵与有理分式矩阵21581多项式矩阵的理想21582多项式矩阵的因子与互质.21683有理分式矩阵.22584有理分式矩阵的既约分解228习题8-1..23238.5系统矩阵的等价变换233§86线性系统的实现理论23987传递函数矩阵的状态空间实现与可控可观24288线性系统的零板点249习题8-225参考书目260索引261目录第一章集合、映射与关系在认识世界的过程中,我们常常倾向于从一些具体事件中归纳出有规律性的东西来.比如说,我们把数字与具体对象分离开来,得到初等数学中数的概念,并给予了加、减、乘、除等运算规律:在髙等数学里,我们知道对向量、矩阵、函数等可以进行类似的计算在数学上,往往重要的不是对象本身,而是对象之间的关系这样就把对象抽象成集合.一般代数(或抽象代数)的主要内容就是研究所谓的代数系统,即具有运算的集合.一般代数在数学的其它分支以及相关学科里都有重要的作用.本书的前二章对一般代数作一个初步介绍81.1集集合的概念大家以前在不同场合会遇到过,这里我们来回顾一下有关的定义及常用记号若十个(有限或无限)确定的事物的全体叫做一个集合,组成一个集合的事物叫做这个集合的元素.一个没有元素的集合称为空集.通常我们用大写字母A,B,C,表示集合,用小写字母a,b,c,表示集合的元素,用②表示空集面的二种方式都可以表示一个集合:A={a1,a2,}其中第一种方式可用来表示有限或可列集合,第二种方式可读为满足条件P(x)的所有x组成的集合若a是集合A的一个元素,就说a属于A或A包含a,用符号a∈A或A3a米表示;反之若a不是集A的元,就说a不属于A或A不包含a,用符号agA或Aa米表示若集合B的每一个元素都属于集合A,就说B是A的子集,用符号BcA或A>B表示;否则就说B不是A的子集,用符号BgA或AB表示.任集合A总可以空集和其自身A作为该集合的子集,这两个子集称为平凡子集由一个集合A的所有子集作为元素而构成的集合,称为集A的幂集.不难证明,如果集A是有限集,并具有n个元素则A的幂集将有2个元素.在这个意义上我们常将A的幂集记为24第一章集合、映射与关系若集合A和集合B所包含的元素完全相同,那么A与B实际上表示同一个集合,这时称A等于B,即A_B.显然有A=B→ACB,AB式中双向蕴含号“←→”表示其左右两边互为(充分必要的)等价命题下面对二个集合A,B定义一些常见的运算并集AUB={x:x∈A或r∈B}交集A∩B={x:∈A且r∈B}差集4B={x:x∈A且xgB}直积A×B={(x,y):∈A,y∈B}集合的并和父都满足结合律与父换律,并且并与父之间还符合分配律,即对任意三个集合A,B,C有Au(B∩C)=(AUB)n(AUC)A∩(BUC)=(∩B)∪(A∩C)在很多情况下,我们的矿究对象是限制在定的范围内,形成个基本集合(全集),我们感兴趣的是基本集合里的了集之间的关系.现设有基本集合E,以及其中的集合A(AcE),称差集EA为集A的补集(余集),记x=EA作为直积的一个例子,两个实数集R的直积为平面点集R2=R×R多个集合之直积可以类似地定义为41×A2×……An={(x1,x2,…,mn):x;∈A,=1,2,…,m}式中(x1,x2,,xn)是元有序组812映射我们知道,函数概念反映了数与数之间的对应关系,现在我们把函数意义推广一下,考查一般集合里的元素之间的对应关系定义1.21(映射)对于两个集合A和B,如果能够建立某种规则∫,使得对任给a∈A,存在唯一的元b∈B与之对应,记为f:a口b或f(a)=b,那么就称∫是由集A到集B的一个映射,记作∫:A→B或A→B,其中a和b可分别叫做映射f的原象与象
- 2020-12-07下载
- 积分：1
