蒙特卡罗最优化.ppt

该【蒙特卡罗最优化 】是由【太丑很想放照片】上传分享，文档一共【54】页，该文档可以免费在线阅读，需要了解更多关于【蒙特卡罗最优化 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。主要(Yao)内容
一、数值优化方法(Numericaloptimizationmethods)
二、应用于求解随机优化问题的蒙特卡罗方法
(1)模拟退火算法(SimulatedAnnealing)
(2)EM算法(TheEMalgorithm)
第一页,共五十四页。

-findinginonedimension
假设f:R→R为一连续函数,则方程f(x)=c的根x,满足g(x)=f(x)-c=(x)=0形式的方程求根问(Wen)题。使用数值方法求此方程的根,可以选择是使用f的一阶导数还是不使用导数的方法。Newton方法或者Newton-Raphson方法是使用一阶导数的方法,而Brent的最小化算法是不使用导数的一种求根方法。
第二页,共五十四页。
(二分(Fen)法)
如果f(x)在区间[a,b]上连续,以及f(a)和f(b)有相反的符号,则由中值定理知道存在a<c<b,使得f(c)=0。二分法通过在每次迭代中简单的判断f(x)在中点x=(a+b)/2处的符号来寻求方程的根。如果f(a)和f(x)有相反的符号则区间就被[a,x]代替,否则就被[x,b]代替。在每次迭代中,包含根的区间长度减少一半。即
第三页,共五十四页。
第四页,共五十四页。
可以看出,二分法不会失效,达到指定精度所需要的迭代次数也是事先(Xian)可以得到的。如果在区间[a,b]里方程有多个根,则二分
常用的收敛准则有:
绝对收敛
第五页,共五十四页。
时停止迭代(Dai)。此准则可以不考虑x的单位情况下达到指定的精度。
法会找到一个根。二分法的收敛速度是线性的。
相对收敛
第六页,共五十四页。
下面我们使用二分法求此方程的一个数值解(Jie)。我们首先要找到一个区间,比如(0,5n),使得函数
在区间两端有着不同的符号。然后即可使用二分法。
例1解方程
其中a为常数,n>2为一整数。显然,方程的解为
第七页,共五十四页。
程(Cheng)序:
a<-
n<-20
cat("trueroots",-a/(n-1)-sqrt(n-2-a^2+(a/(n-1))^2),
+-a/(n-1)+sqrt(n-2-a^2+(a/(n-1))^2),"\n")
bisec<-function(b0,b1){
f<-function(y,a,n){
a^2+y^2+2*a*y/(n-1)-(n-2)
}
it<-0
eps<-.Machine$^
r<-seq(b0,b1,length=3)
y<-c(f(r[1],a,n),f(r[2],a,n),f(r[3],a,n))
if(y[1]*y[3]>0)
stop("fdoesnothaveoppositesignatendpoints")
第八页,共五十四页。
while(it<1000&&abs(y[2])>eps){
it<-it+1
if(y[1]*y[2]<0){
r[3]<-r[2]
y[3]<-y[2]
}else{
r[1]<-r[2]
y[1]<-y[2]
}
r[2]<-(r[1]+r[3])/2
y[2]<-f(r[2],a=a,n=n)
print(c(r[1],y[1],y[3]-y[2]))
}
}
bisec(0,5*n)
第九页,共五十四页。
运(Yun)行结果:
trueroots-
第十页,共五十四页。