蒙特卡羅最優(yōu)化-課件

蒙特卡羅最優(yōu)化主要內(nèi)容一、數(shù)值優(yōu)化方法（Numericaloptimizationmethods）二、應(yīng)用于求解隨機優(yōu)化問題的蒙特卡羅方法（1）模擬退火算法（SimulatedAnnealing)（2）EM算法（TheEMalgorithm)21.NumericaloptimizationmethodsinR1.1Root-findinginonedimension

假設(shè)f:R→R為一連續(xù)函數(shù)，則方程f(x)=c的根x,滿足g(x)=f(x)-c=0.為此我們只考慮f(x)=0形式的方程求根問題。使用數(shù)值方法求此方程的根，可以選擇是使用f的一階導(dǎo)數(shù)還是不使用導(dǎo)數(shù)的方法。Newton方法或者Newton-Raphson方法是使用一階導(dǎo)數(shù)的方法，而Brent的最小化算法是不使用導(dǎo)數(shù)的一種求根方法。31.1.1Bisectionmethod(二分法）如果f(x)在區(qū)間[a,b]上連續(xù)，以及f(a)和f(b)有相反的符號，則由中值定理知道存在a<c<b，使得f(c)=0。二分法通過在每次迭代中簡單的判斷f(x)在中點x=(a+b)/2處的符號來尋求方程的根。如果f(a)和f(x)有相反的符號則區(qū)間就被[a,x]代替，否則就被[x,b]代替。在每次迭代中，包含根的區(qū)間長度減少一半。即45可以看出，二分法不會失效，達到指定精度所需要的迭代次數(shù)也是事先可以得到的。如果在區(qū)間[a,b]里方程有多個根，則二分常用的收斂準(zhǔn)則有：絕對收斂6時停止迭代。此準(zhǔn)則可以不考慮x的單位情況下達到指定的精度。法會找到一個根。二分法的收斂速度是線性的。相對收斂7大家學(xué)習(xí)辛苦了，還是要堅持繼續(xù)保持安靜8

下面我們使用二分法求此方程的一個數(shù)值解。我們首先要找到一個區(qū)間，比如(0,5n)，使得函數(shù)在區(qū)間兩端有著不同的符號。然后即可使用二分法。

例1解方程其中a為常數(shù)，n>2為一整數(shù)。顯然，方程的解為9程序：a<-0.5n<-20cat("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<-0eps<-.Machine$double.eps^0.25r<-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")10while(it<1000&&abs(y[2])>eps){it<-it+1if(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])/2y[2]<-f(r[2],a=a,n=n)print(c(r[1],y[1],y[3]-y[2]))}}bisec(0,5*n)11運行結(jié)果：trueroots-4.2394734.186841121.1.2

Brent’smethod二分法是一種特殊的括入根算法。Brent通過逆二次插值方法將括入根方法和二分法結(jié)合起來。其使用y的二次函數(shù)來擬合x。如果三個點為(a,f(a)),(b,f(b)),(c,f(c)）,其中b為當(dāng)前最好的估計，則通過Lagrange多項式插值方法（y=0)對方程的根進行估計，在R中，函數(shù)uniroot就是應(yīng)用Brent方法求解一元方程的數(shù)值根。13例2應(yīng)用uniroot求例1中的方程的根。程序：a<-0.5n<-20out<-uniroot(function(y){a^2+y^2+2*a*y/(n-1)-(n-2)},lower=0,upper=n*5)unlist(out)

root

f.root

iter

estim.prec4.186870e+002.381408e-041.400000e+01

6.103516e-05uniroot(function(y){a^2+y^2+2*a*y/(n-1)-(n-2)},interval=c(-n*5,0))$root[1]-4.23950114

1.1.3Newton’smethod151617例3使用Newton方法求例1方程的根。程序：nt<-function(b0){a<-0.5n<-20f<-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)}18b1<-b0b0<-b0-1eps<-.Machine$double.eps^0.25it<-0while(it<1000&&abs(b1-b0)>eps){it<-it+1b0<-b1b1<-b0-f(b0,a,n)/fd(b0,a,n)cat(it,c(b0,b1,abs(b1-b0)),"\n")

}}19輸入：nt(5)輸出結(jié)果：

15

4.2526180.7473822

24.2526184.1873470.06527095

34.1873474.1868410.0005055338

4

4.1868414.1868413.032932e-08

Newton方法依賴于f的形狀和初值。該方法從初值開始就發(fā)散。2021222324252627282930運行結(jié)果：31323334運行結(jié)果：35

3637382.應(yīng)用于求解隨機優(yōu)化問題的蒙特卡羅方法2.1模擬退火算法39模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時趨于平衡的概率為e-ΔE/(kT)，其中E為溫度T時的內(nèi)能，ΔE為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到40解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)“產(chǎn)生新解→計算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。退火過程由冷卻進度表(CoolingSchedule)控制，包括控制參數(shù)的初值t及其衰減因子Δt、每個t值時的迭代次數(shù)L和停止條件S4142434445464748495051給定一些觀察數(shù)據(jù)x，假設(shè)x符合如下高斯分布：求混合高斯分布的三組參數(shù)2.2EM算法問題來源EM算法是個聚類算法，即根據(jù)給定觀察數(shù)據(jù)自動對數(shù)據(jù)進行分類。52該混合高斯分布一共有K個分布，并且對于每個觀察到的x，如果我們同時還知道它屬于K中的哪一個分布，則我們可以根據(jù)最大似然估計求出每個參數(shù)。結(jié)論：簡單問題特別注意是個向量，而是個數(shù)值。表示屬于第k個高斯分布的觀察數(shù)據(jù)x。53實際問題觀察數(shù)據(jù)x屬于哪個高斯分布是未知的所以要用EM