随机逼近算法简介

随机逼近算法简介随机逼近的研究目的在许多理论课或实际应用中,经常要求一个函数的零点或极值,如果函数有已知的解析表达式,那么在理论上解决这个问题并不困难;如果虽不知函数的表达式,但它在任一点的取值可以无误差的测量到,那么有不少行之有效的数值方法可供选用;当既不知函数的表达式,又不能无误差的测量到函数值时,如何求函数的零点或极值,正是随机逼近要解决的问题。随机逼近理论的发展随机逼近创始于50年代初,Robbins-Monrn[1]首先提出了求未知函数f(•)零点x0的一个递推算法。在Robbins-Monro的奠基性工作后,随机逼近取得蓬勃发展。主要的研究目标是考察各种相关的测量噪声[2]及拓广可适用的回归函数范围,[3]而收敛类型,除了最初的均方收敛,更多的是研究概率1收敛及弱收敛。从研究方法讲,文献[2]是用鞅收敛方法研究随机逼近算法概率1收敛的有代表性的专著,其基本特点是讨论独立噪声,它对20世纪70年代以前的工作做了一个很好的总结,之后,文件[3]把递推算法的收敛性和微分方程的稳定性建立了联系,从而使得考察的测量误差的范围有实质性的扩大。但这种方法要事先假定算法给出的估计值有界。经过半个多世纪的发展历程,随机逼近思想已经得到了不断的进步和完善。到目前为止，随机逼近控制方法有RM法、KW法o其中基于KW方法上的变形情况有:有限微分随机逼近算法(FDSA)、随机方向的随机逼近算法(RDSA)和同时扰动随机逼近算法(SPSA)o随机逼近算法简介3.1随机逼近问题对许多实际问题和理论问题的研究,常常归结为一个非线性方程组的求根问题,长期以来,人们发展了不少逐次逼近的数值解法。但是,在很多实际问题中，人们并不知道方程中非线性函数的形式，只可以对给定的自变量值，带随机误差地测量到函数值。在这种情况下,怎样去求这个未知的非线性函数的零点,是一个从实践到理论都很重要的问题。设未知函数为,它的零点为x0,即h(x0)=0(1)对h(•)可以在任意点x进行测量，但测量带有误差，若xn为第n次测量时所取定的自变量值，则函数的观测值为:yn+1=h(xn)+Zn+1(2)｛Zn｝是测量误差序列，可以依赖于xnoh(•)称为回归函数。用实际得到的序列｛xn｝和｛yn｝,去求回归函数的根x0,这就是随机逼近问题。下面用朱允文所举的一个例子说明随机逼近的实际性。假设发明了一种新药,必须确定它的最佳剂量,设剂量为x,人服药后的反应为f(X),而人们希望达到的最佳反应为a,定义h(x)=f(x)-a。显然，这里的f(•)和h(•)都只是一种形式上的写法,人们无法精确的知道药物剂量与药物反应之间的对应关系h(•),但是可以带随机误差地测量它,得到:yn+1=h(xn)-a+Zn+1解决这一实际问题就要求助于某种随机逼近算法。3.2RM算法的提出1951年,Robbins和Monro首次提出并研究了一种随机逼近算法,[1]他们取数列{ai}为增益系数:(3)对x0的第n+1次逼近为:xn+1=xn+anyn+1(4)其中yn如式(2)所定义,这就是著名的Robbins-Monro(RM)算法。当时，他们讨论了Zn为相互独立的情况，并且ℓ=1,在h(•)严格单调的时候，他们证明了xn对x0的平方收敛性:显然上面的结果是在比较强条件下得到的,但这标志着人们找到了对理论和实际都很重要的这类问题的一种处理方法。3.3KW算法的提出在RM算法提出后的第二年，出现了Kiefer-Wolfowitz(KW)算法,[4]也就是求h(x)极值的算法。如果能直接测量h(•)的导数，那么问题就归结为上面的RM算法。但有时只能测量h(•)本身,只好利用h(•)的测量值的差商去估计h(•)的导数值，这就是KW算法的基本思想。因此，KW算法与RM算法比较，除了在测量点上有一些变化外，算法的基本形式以及理论研究的基本思想都是一致的。增益系数{a1}又称步长因子,它所具有的性质(3),对随机逼近算法和其他某些随机逼近递推算法都是必要的。条件的实质是ai必须趋于0,也就是每步的修正量越来越小,直到把测量误差的影响慢慢压制下去,使aiyi中的。但是又说明,ai趋于0的速度不能太快。因为如果,这时即使，h(•)一致有界,?Uh(•)?U分析

定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析