蒙特卡罗最优化 PPT课件.ppt

Monte Carlo Optimization
主要内容
一、数值优化方法(Numerical optimization methods)
二、应用于求解随机优化问题的蒙特卡罗方法
(1)模拟退火算法(Simulated Annealing)
(2)EM算法(The EM algorithm)
optimization methods in R
Root-finding in one dimension
假设f:R→R为一连续函数,则方程f(x)=c的根x,满足g(x)=f(x)-c=(x)=0形式的方程求根问题。使用数值方法求此方程的根,可以选择是使用f的一阶导数还是不使用导数的方法。Newton方法或者Newton-Raphson方法是使用一阶导数的方法,而Brent的最小化算法是不使用导数的一种求根方法。
Bisection method(二分法)
如果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]代替。在每次迭代中,包含根的区间长度减少一半。即
可以看出,二分法不会失效,达到指定精度所需要的迭代次数也是事先可以得到的。如果在区间[a,b]里方程有多个根,则二分
常用的收敛准则有:
绝对收敛
时停止迭代。此准则可以不考虑x的单位情况下达到指定的精度。
法会找到一个根。二分法的收敛速度是线性的。
相对收敛
程序:
a <-
n <- 20
cat("true roots",-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("f does not have opposite sign at endpoints")
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)