蒙特卡罗最优化.ppt

主要内容
一、数值优化方法（Numerical optimization methods）
二、应用于求解随机优化问题的蒙特卡罗方法
（1）模拟退火算法（Simulated Annealing)
（2）EM算法（The EM a= n*5)
unlist(out)
root iter
+00 -04 +01 -05
uniroot(function(y) {a^2 + y^2 + 2*a*y/(n-1) - (n-2)},
interval = c(-n*5, 0))$root
[1] -
第十二页，共五十四页。
Newton’s method
第十三页，共五十四页。
第十四页，共五十四页。
第十五页，共五十四页。
例3 使用Newton方法求例1方程的根。
程序：
nt<-function(b0){
a <-
n <- 20
f <- function(y, a, n) {
a^2 + y^2 + 2*a*y/(n-1) - (n-2)
}
fd<-function(y,a,n){
2*y+2*a/(n-1)
}
第十六页，共五十四页。
b1<-b0
b0<-b0-1
eps <- .Machine$^
it<-0
while(it<1000 && abs(b1-b0)>eps){
it<-it+1
b0<-b1
b1<-b0-f(b0,a,n)/fd(b0,a,n)
cat(it,c(b0,b1,abs(b1-b0)),"\n")
}
}
第十七页，共五十四页。
输入：nt(5)
输出结果：
1 5
2
3
4 -08
Newton方法依赖于f的形状和初值。该方法从初值开始就发散。
第十八页，共五十四页。
第十九页，共五十四页。
第二十页，共五十四页。
第二十一页，共五十四页。
第二十二页，共五十四页。
第二十三页，共五十四页。
第二十四页，共五十四页。
第二十五页，共五十四页。
第二十六页，共五十四页。
第二十七页，共五十四页。
第二十八页，共五十四页。
运行结果：
第二十九页，共五十四页。
第三十页，共五十四页。
第三十一页，共五十四页。
第三十二页，共五十四页。
运行结果：
第三十三页，共五十四页。
第三十四页，共五十四页。
第三十五页，共五十四页。
第三十六页，共五十四页。


第三十七页，共五十四页。
模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t， 即得到
第三十八页，共五十四页。
解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S
第三十九页，共五十四页。
第四十页，共五十四页。
第四十一页，共五十四页。
第四十二页，共五十四页。
第四十三页，共五十四页。
第四十四页，共五十四页。
第四十五页，共五十四页。