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

主要內(nèi)容一、數(shù)值優(yōu)化方法（Numericaloptimizationmethods）二、應(yīng)用于求解隨機(jī)優(yōu)化問題的蒙特卡羅方法（1）模擬退火算法（SimulatedAnnealing)（2）EM算法（TheEMalgorithm)現(xiàn)在是1頁\一共有54頁\編輯于星期三1.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ù)的一種求根方法?，F(xiàn)在是2頁\一共有54頁\編輯于星期三1.1.1Bisectionmethod(二分法）如果f(x)在區(qū)間[a,b]上連續(xù)，以及f(a)和f(b)有相反的符號，則由中值定理知道存在a<c<b，使得f(c)=0。二分法通過在每次迭代中簡單的判斷f(x)在中點(diǎn)x=(a+b)/2處的符號來尋求方程的根。如果f(a)和f(x)有相反的符號則區(qū)間就被[a,x]代替，否則就被[x,b]代替。在每次迭代中，包含根的區(qū)間長度減少一半。即現(xiàn)在是3頁\一共有54頁\編輯于星期三現(xiàn)在是4頁\一共有54頁\編輯于星期三可以看出，二分法不會失效，達(dá)到指定精度所需要的迭代次數(shù)也是事先可以得到的。如果在區(qū)間[a,b]里方程有多個根，則二分常用的收斂準(zhǔn)則有：絕對收斂現(xiàn)在是5頁\一共有54頁\編輯于星期三時停止迭代。此準(zhǔn)則可以不考慮x的單位情況下達(dá)到指定的精度。法會找到一個根。二分法的收斂速度是線性的。相對收斂現(xiàn)在是6頁\一共有54頁\編輯于星期三

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

例1解方程其中a為常數(shù)，n>2為一整數(shù)。顯然，方程的解為現(xiàn)在是7頁\一共有54頁\編輯于星期三程序：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")現(xiàn)在是8頁\一共有54頁\編輯于星期三while(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)現(xiàn)在是9頁\一共有54頁\編輯于星期三運(yùn)行結(jié)果：trueroots-4.2394734.186841現(xiàn)在是10頁\一共有54頁\編輯于星期三1.1.2Brent’smethod二分法是一種特殊的括入根算法。Brent通過逆二次插值方法將括入根方法和二分法結(jié)合起來。其使用y的二次函數(shù)來擬合x。如果三個點(diǎn)為(a,f(a)),(b,f(b)),(c,f(c)）,其中b為當(dāng)前最好的估計(jì)，則通過Lagrange多項(xiàng)式插值方法（y=0)對方程的根進(jìn)行估計(jì)，在R中，函數(shù)uniroot就是應(yīng)用Brent方法求解一元方程的數(shù)值根?，F(xiàn)在是11頁\一共有54頁\編輯于星期三例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)rootf.rootiterestim.prec4.186870e+002.381408e-041.400000e+016.103516e-05uniroot(function(y){a^2+y^2+2*a*y/(n-1)-(n-2)},interval=c(-n*5,0))$root[1]-4.239501現(xiàn)在是12頁\一共有54頁\編輯于星期三

1.1.3Newton’smethod現(xiàn)在是13頁\一共有54頁\編輯于星期三現(xiàn)在是14頁\一共有54頁\編輯于星期三現(xiàn)在是15頁\一共有54頁\編輯于星期三例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)}現(xiàn)在是16頁\一共有54頁\編輯于星期三b1<-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")}}現(xiàn)在是17頁\一共有54頁\編輯于星期三輸入：nt(5)輸出結(jié)果：154.2526180.747382224.2526184.1873470.0652709534.1873474.1868410.000505533844.1868414.1868413.032932e-08

Newton方法依賴于f的形狀和初值。該方法從初值開始就發(fā)散?，F(xiàn)在是18頁\一共有54頁\編輯于星期三現(xiàn)在是19頁\一共有54頁\編輯于星期三現(xiàn)在是20頁\一共有54頁\編輯于星期三現(xiàn)在是21頁\一共有54頁\編輯于星期三現(xiàn)在是22頁\一共有54頁\編輯于星期三現(xiàn)在是23頁\一共有54頁\編輯于星期三現(xiàn)在是24頁\一共有54頁\編輯于星期三現(xiàn)在是25頁\一共有54頁\編輯于星期三現(xiàn)在是26頁\一共有54頁\編輯于星期三現(xiàn)在是27頁\一共有54頁\編輯于星期三現(xiàn)在是28頁\一共有54頁\編輯于星期三運(yùn)行結(jié)果：現(xiàn)在是29頁\一共有54頁\編輯于星期三現(xiàn)在是30頁\一共有54頁\編輯于星期三現(xiàn)在是31頁\一共有54頁\編輯于星期三現(xiàn)在是32頁\一共有54頁\編輯于星期三運(yùn)行結(jié)果：現(xiàn)在是33頁\一共有54頁\編輯于星期三

現(xiàn)在是34頁\一共有54頁\編輯于星期三現(xiàn)在是35頁\一共有54頁\編輯于星期三現(xiàn)在是36頁\一共有54頁\編輯于星期三2.應(yīng)用于求解隨機(jī)優(yōu)化問題的蒙特卡羅方法2.1模擬退火算法現(xiàn)在是37頁\一共有54頁\編輯于星期三模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達(dá)到平衡態(tài)，最后在常溫時達(dá)到基態(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，即得到現(xiàn)在是38頁\一共有54頁\編輯于星期三解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。退火過程由冷卻進(jìn)度表(CoolingSchedule)控制，包括控制參數(shù)的初值t及其衰減因子Δt、每個t值時的迭代次數(shù)L和停止條件S現(xiàn)在是39頁\一共有54頁\編輯于星期三現(xiàn)在是40頁\一共有54頁\編輯于星期三現(xiàn)在是41頁\一共有54頁\編輯于星期三現(xiàn)在是42頁\一共有54頁\編輯于星期三現(xiàn)在是43頁\一共有54頁\編輯于星期三現(xiàn)在是44頁\一共有54頁\編輯于星期三現(xiàn)在是45頁\一共有54頁\編輯于星期三現(xiàn)在是46頁\一共有54頁\編輯于星期三現(xiàn)在是47頁\一共有54頁\編輯于星期三現(xiàn)在是48頁\一共有54頁\編輯于星期三現(xiàn)在是49頁\一共有54頁\編輯于星期三給定一些觀察數(shù)據(jù)x，假設(shè)x符合如下高斯分布：求混合高斯分布的三組參數(shù)2.2EM算法問題來源EM算法是個聚類算法，即根據(jù)給定觀察數(shù)據(jù)自動對數(shù)據(jù)進(jìn)行分類。現(xiàn)在是50頁\一共有54頁\編輯于星期三該混合高斯分布一共有K個分布，并且對于每個觀察到的x，如果我們同時還知道它屬于K中的哪一個分布，則我們可以根據(jù)最大似然估計(jì)求出每個參數(shù)。結(jié)論：簡單問題特別注意是個向量，而是個數(shù)值。表示屬于第k個高斯分布的觀察數(shù)據(jù)x?，F(xiàn)在是51頁\一共有54頁\編輯于星期三實(shí)際問題觀察數(shù)據(jù)x屬于哪個高斯分布是未知的所以要用EM算法來解決這種實(shí)際問題。現(xiàn)在是52頁\一共有54頁\編輯于星期三EM算法過程：1、用隨機(jī)函數(shù)初始化K個高斯分布的參數(shù)，同時保證Expectation2、依次取觀察數(shù)據(jù)x，比較x在K個高斯函數(shù)中概率的大小，把x歸類到這K個高斯中概率最大