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
基于LMS 算法的多麦克风降噪
武汉理工大学 信息处理课设 基于LMS 算法的多麦克风降噪 给定主麦克风录制的受噪声污染的语音信号和参考麦克风录制的噪声，实现语音增强的目标，得到清晰的语音信号。2007控制科学与工程全国博士生学术论坛2007年8月其中日为语音信号与麦克风阵列所在平面的夹角,d为麦克风间距,c为声音传播速度,f为信号采样率。固定波束形成器通过延时求和单元产生参考语音信号y(n),y(n)与y(m)分别代表期望语音信号与噪声信号。y,(n)4x(m)=y(m)+y/(m(3)信号通过阻塞矩阵产生噪声参考信号用来估计波束形成输出信号中的噪声成分。选取B使其中任意行向量之和为零,即任意行向量线性无关。为了进一步降低噪声参考信号中的语音泄漏,参考文献“提出了用自适应阻塞矩阵替代固定阻塞矩阵的方法。ynly2nMM-[nJ]=BLun], u2n],umn自适应噪声抵消器ANC通过对输入噪声参考信号进行自适应滤波处理抵消了参考信号y,(m)中的噪声成分,得到增强的语音信号。em]=y[m-∑nnl3LMS自适应算法及改进31LMS自适应算法GSC架构中的自适应噪声抵消器ANC需要用增强的语音信号作为反馈对滤波器权值进行自适应更新。很多自适应算法基于LMS及其改进形式, Clark提出的块LMS算法使得滤波器的自适应逐块更新而非传统LMS滤波器逐点更新4, HOSHUYAMA、 Kellermann分别提出的基于范数约束自适应算法的权值更新,以及频域无约束实现。这些算法基本结构如图2所示y(n-1)(n-L+1)wo(ne(ny/(n)图2自适应横向滤波器结构图图2为图1中的M-1路L阶多通道自适应噪声对消器中某一路的展开形式,其抽头输入向量为[ym]yn-]yn-L+1],对应的抽头权向量为wmwn]w-]。LMS算法的梯度向量通过G2007控制科学与工程全国博士生学术论坛2007年8月计算抽头输入相关矩阵R和抽头输入与期望响应间互相关向量p得到VJ(n)=-2p+2Rv(m),将R和p的瞬态估计R(n)=y(m)y"(n),p(n)=y(n)y/(m)代入,得出梯度向量的瞬态估计:VJ(n)=-2y(n)y, (n+2y(n)y"(n)w(n)进而推出LMS算法权值更新公式为w(n+1)=w(n)+uy(n)Ly(n)-y"(n)w(n)32基于稳态噪声的自适应算法改进考查图2中具有L个抽头权值的LMS算法,抽头权值与抽头输入一一对应。在传统的逐点更新LMS算法中,每计算一个输出需要L次乘法,而更新一次抽头权值也需要L次乘法,故每次迭代需要2L次乘法。对于L个输出样值,所需要的乘法次数为2次。针对传统LMS算法复杂度高的缺点,Ca利用离散傅立叶变换在频域完成滤波器系数的自适应提出了快速块LMS箅法, Ann Spriet在此基础上通过改进LMS算法中的步长矩阵进一步降低了算法复杂度以上LMS算法改进均在图2的横向滤波器架构下进行,即抽头权值与抽头输入一一对应。考虑到稳态噪声的特点,本文提出了“一对多”的滤波器抽头权值更新算法,即L个输入样值共享一个滤波器权值。如此M路多麦克风语音增强系统中的ANC滤波器权值便由(M-1)×L维矩阵W[n=[w[η],n2[rl…wM-[r],其中H[n]=[won],w1[nw-r]退化为(M-1)×1维向量n]=[wryw2n],M-m]j。改进算法权值更新公式为w(n+D)=w(n)+uBu(nu"(n)[A-Bw(n)其中B为阻塞矩阵,A为固定波束形成器,为步长,U(n)为LxM维输入信号。与传统的“一对一”LMS滤波器相比,“一对多”结构在降低算法复杂度的同时,牺牲了前者具有的时间域严格对齐的特性。为降低这一缺点对系统降噪性能的影响,应在频域进行噪声对消,改进算法的多麦克风语音增强系统结构如图3所示。e(n)(n)B Yn图3改进的噪声消除算法结构图3中用虚线框表示可选滤波器权值w。由于实际应用中语音泄漏的存在,在参考语音信号中加入v能有效补偿由语音泄漏引起的语音崎变⑩。实际应用中由于阻塞矩阵输出不可避免的存在语音泄4642007控制科学与工程全国博士生学术论坛2007年8月漏,为了避免期望信号的消除,箅法中加入语音活动检测单元89,当前帧为噪声时更新滤波器系数,当前帧为语音信号时,滤波器系数不变33算法复杂度比较表1列出了本文算法与其他几种噪声消除算法之间算法复杂度的比较。我们采用实数乘法运算次数作为衡量算法复杂度的标准,每个N点傅立叶变换或其反变换需要Mlog2N次实数乘法运算。传统逐点LMS算法在时间域逐点更新滤波器权值。快速块LMS算法与多通道 Wiener算法通过FFT快速循环卷积特性实现LMS中的线性卷积运算,从而降低算法复杂度。本文算法在此基础上通过改进滤波器抽头权值更新算法进一步降低运算复杂度。由表1可见,当麦克风数目M4,L=32时,本文算法与多通道 Wiener滤波算法相比,R(3M+2)FT+8ML+2M63M+2)+4M2+6M_172(M+2)FFT+2ML6(M+2)+M40°文算法运算量降低了4倍左右。表1算法复杂度比较算法名称算法复杂度传统逐点LMS算法2ML快速块LMS算法(41(3M+2)FFT+16ML多通道 Wiener滤波算法53M+2)FFT+8M2+12M本文提出的算法(M+2)FF+2M…图4a)麦克风采集到的原始信号b)采用快速块LMS算法处理后的信号[4]c)采用多通道 Wiener滤波算法[10处理后的信号d采用本文算法处理后的信号4实验结果与分析实验采用线性排列的4个间距为4厘米的麦克风组成的语音采集系统,采样率为44KHZ,说话人位于阵列的正前方,噪声为稳态噪声,其与麦克风阵列法线所夹角度为50度。图4比较了麦克风采集到的信号、采用本文算法处理后的语音信号以及采用其他主流语音增强算法处理后的语音信号的时域波形。由4652007控制科学与工程全国博士生学术论坛2007年8月图4可见采用本文算法处理的语音信号背景噪声有明显降低。为进一步分析各种语音增强算法消噪能力,分别按照公式9计算各算法输出信号的信噪比,其中k代表帧序列号,N代表噪声,Y代表输出语音信号,L为帧长。∑(Y(k,2)2-|N(k,)SNRou(E)=10 log,o∑1MV6)图5釆用各箅法输出信号信噪比与输入信号信噪比之差来衡量噪声降低程度。由图5看出,在本文算法基础上在参考通道中加入可选滤波器权值能够进一步消除背景噪声,提高输出信噪比。苯文鲜法(使用权值w)木文好法未使用权值y块LMS算法Frame Number图5信噪比增强对比5结论本文在稳态噪声的前提下,提出了一种基于广义旁瓣消除器架构具有低算法复杂度的噪声消除算法,该算法通过改进LMS滤波器权值更新算法来达到降低算法复杂度的目的。实验结果证明,在稳态噪声环境下,该方法降噪性能优于传统LMS算法,同时有效降低了传统算法的算法复杂度。在现实生活中一些存在稳态噪声的场合,如发动机舱、厂房等该算法具有很强的实用价值。参考文献[U]LJ. Griffiths and C. W. Jim []. "An altemative approach to linearly constrained adaptive beamforming, IEEE Trans. AntennasProcess., voL. AP-30, no. I, pp 27-34, Jan. 1982.[2]0. Hoshuyama, A Sugiyama, and A Hirano [J]. "A robust adaptive beamformer for microphone arrays with a blocking matrixusing constrained adaptive filters, "IEEE Trans. Signal Process. vol 47, pp. 2677-2683, Oct. 1999[3]W. Herbordt and W Kellermann [J]. " Frequency-domain integration of acoustic echo cancellation and a generalized sidelobecanceller with improved robustness, "Eur. Trans. Telecommun., voL. 13, no 2, pp 123-132, Mar. -Apr. 2002.[4]Clark. G.A., S K Mitra, and S.R. Parker [J]. Block implementation of adaptive digital filters, "IEEE Trans. Circuits Syst,voL. CAS-28,PP584-592.1981.[5]Ann Spriet, Jan Wouters, Simon Doclo, Marc Moonen, "Frequency-Domain Criterion for the Speech Distortion WeightedMultichannel Wiener Filter for Robust Noise Reduction", Ap: //ftp. esat kuleuven. ac, be/pub/SISTA/doclo/reports/04-240 pdf[6JH. Buchner, J. Benesty, W. Kellermann J]. Generalized multichannel frequencydomain adaptive filtering: efficient realizationand application to hands free speech communication", Signal Processing 85(3), PP 549-570. 2005[7]W.Herbordt and W. Kellermann [A]. " Efficient Frequency-domain realization of robust generalized sidelobe cancellers", IEEE4662007控制科学与工程全国博士生学术论坛2007年8月Fourth workshop, multimedia signal Processing, PP. 377-382 2001[8]S. Van Gerven, F. Xie [J. "A Comparative Study of Speech Detection Methods", Proc. EUROSPEECH, VoL 3, Rhodos, Greecepp.1095-1098.1997[9]J Sohn, N.S.Kim, W Sung [] A Statistical Model-Based Voice Activity Detection", IEEE Signal Processing Lett. 6(1)1-31999[10]A Spriet, M. Moonen, J Wouters[]. Robustness Analysis of Multi-channel wiener Filtering and generalized sidelobeCancellation for Multi-microphone Noise Reduction in Hearing Aid Applications", IEEE Trans. Speech and Audio Processing, 13(4)PP.487-503.2005[IlJFerrara, E R r [] Fast implementation of LMS adaptive filters", IEEE Trans. Acoust. Speech Signal Process,voL.ASSP-28pp474-475.1980[12]S. Doclo and M. Moonen[J]. " Multi-microphone noise reduction using recursive GSVD-based optimal filtering with ANCpostprocessing stage, "IEEE Trans. Speech Audio Process., vol. 13, no. 1,Pp 53-69, Jan. 2005[13]Philipos C Loizou [J]. "Speech Enhancement Based on Perceptually Motivated Bayesian Estimators of the MagnitudeSpectrum" IEEE TRANSACTIONS ON SPEECH AND AUDIO PROCESSING, VOL 13, NO 5, Pp.857-869, 2005种新的基于稳态噪声的噪声消除算法旧WANFANG DATA文献链接作者:董鹏宇,朱子元,林涛作者单位:同济大学超大规模集成电路研究所,上海20009本文链接http://d.g.wanfangdata.comcn/confereNce6584700.aspx
- 2020-11-28下载
- 积分：1
