信賴域方法學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1信賴信賴(xnli)域方法域方法第一頁，共27頁。信賴域算法全局收斂算法這一節(jié)，將介紹另一種二次模型函數(shù)。但它沒有進(jìn)一步的使用。該方法具有整體收斂性法，長，這個(gè)就是阻尼牛頓從而得到一個(gè)縮短的步作一維搜索，）（）（沿著搜索方向）正定時(shí)，（，）（對(duì)它做了改進(jìn)，即當(dāng)局收斂算法，取有關(guān)），為了得到全（收斂性與初始點(diǎn)的選部收斂算法，傳統(tǒng)的牛頓法屬于局上一節(jié)，學(xué)習(xí)了牛頓法）（）（）（）（）（-xfxf-dxf0 xfk2kkk2k第1頁/共26頁第二頁，共27頁。第2頁/共26頁第三頁，共27頁。）（）（）（）（）（）（，產(chǎn)生新的迭代點(diǎn)選擇選擇適當(dāng)?shù)牟介L向，然后沿著這個(gè)搜索方向后，先確定一個(gè)搜索方

2、給定點(diǎn)化方法，一般策略是在前面介紹的無約束最優(yōu)kkk1kkkkkdxxddx第3頁/共26頁第四頁，共27頁。）（）（）（）（）（）（）（，或產(chǎn)生新的迭代點(diǎn)模型函數(shù)近似解（二次模型函數(shù)）得到目標(biāo)函數(shù)的二次逼近式在這個(gè)信賴域內(nèi)，優(yōu)化步的信賴半徑是第這里定義當(dāng)前點(diǎn)的鄰域k1kkk1kkkkknkxxdxxdkrr|x-x| |xR第4頁/共26頁第五頁，共27頁。就減小。大，反之，信賴域半徑則信賴域半徑可適當(dāng)擴(kuò)問題，模型比較好的逼近于原如果在一次迭代中近似步調(diào)節(jié)，半徑的大小通過迭代逐）的最小值點(diǎn)。信賴域（們可以找到上過程，用這種方法我函數(shù)的新模型。繼續(xù)以附近建立目標(biāo)，然后在一個(gè)點(diǎn)適當(dāng)?shù)奈灰疲苿?dòng)到

3、下們選擇一個(gè)為了得到要求的點(diǎn)，我代表目標(biāo)函數(shù)，接下來大致的某個(gè)鄰域內(nèi)這個(gè)模型假定在目標(biāo)函數(shù)的模型，并且，在其附近建立對(duì)于給定的初始點(diǎn)求逼近模型的最優(yōu)點(diǎn)。某個(gè)鄰域內(nèi)題就是在當(dāng)前迭代點(diǎn)的近似模型，信賴域子問于原目標(biāo)函數(shù)的始點(diǎn)附近構(gòu)造一個(gè)近似首先給出初始點(diǎn)，在初）（：對(duì)于問題：）（）（）（）（xfxxxxxfmin2211第5頁/共26頁第六頁，共27頁。)df(xd21d)(f)(fx-xd)x-)(xf(xx-x21x-x)(f)(fxfxxfxxfmink)2T)()(kk(k)k)2Tkk)()(kn（）（）（）（）（）（），得到二次模型（?。ǎǎㄌ幷归_，取二次近似）在給定點(diǎn)（將），（

4、：考慮無約束問題：TkkTkkxxdxx第6頁/共26頁第七頁，共27頁。尋優(yōu)問題）一些列相對(duì)簡單的局部化為是將復(fù)雜的最優(yōu)問題轉(zhuǎn)（可以看出信賴域算法）（：一系列子問題為解）的極小點(diǎn)問題就歸結(jié)（這樣，求函數(shù)問題并求極值）這個(gè)簡單模型近似于原內(nèi)建立一個(gè)簡單模型，代點(diǎn)的某個(gè)鄰域的取值實(shí)質(zhì)是在當(dāng)前迭（由此可以看出，限定步的信賴域半徑就是前面提到的第即的取值，令限定），（）近似（附近用為了在（）（）（kk)2T)()(k(k)kkkr|d| s.t.)df(xd21d)()(minxfdkrr|x-x|,r|ddxfdxTkkkkkxfxfdd）（10.5.3第7頁/共26頁第八頁，共27頁。|xfIx

5、f|d|10.5.5Ixfr|d|00-r|d|xf-ddxfddd0-r|d|0dddxfdxf10.5.3dk1 -k2kk2kkkkkk2k21kkkk21kkkkk2kkkk）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）得到可逆，有（）（設(shè)）（）（）（為最優(yōu)解的必要條件得到）（記：）（）（）（）（，使得子）的最優(yōu)解，則存在乘是（若是關(guān)鍵的求解信賴域子問題顯然TT第8頁/共26頁第九頁，共27頁。k1kk1kkk1kkk1kkkkkkk)(kkkkk2rrrrdxxr21rxd-xf)dx(f-fxfddxd或且，后繼點(diǎn)比較大，則逼近成功，若；

6、，且信賴域半徑功，后繼點(diǎn)仍取太小，就認(rèn)為逼近不成）（）（）（與預(yù)測下降量之比，即如果函數(shù)值實(shí)際下降量）是否成功來確定。（）逼近（還要根據(jù)用解，能否作為原問題的近似后，點(diǎn)求出信賴子問題）（）（）（）（）（）（）（）（）（）（）（kx第9頁/共26頁第十頁，共27頁。第10頁/共26頁第十一頁，共27頁。最近的點(diǎn)，以此類推。第11頁/共26頁第十二頁，共27頁。kk)2T)()(kk2kkkk11r|d| s.t.)df(xd21d)x(f)x(fmin.3xfx|xf|.xfxf.21k434110 x.1（）（）（）（）（）（）（）（：求解子問題）（）（；否則，計(jì)算則停止計(jì)算，得到解，）（若）

7、（），（計(jì)算）（，置）及精度要求，（一般，參數(shù)，信賴域半徑給定可行點(diǎn)）（Tkkd第12頁/共26頁第十三頁，共27頁。），轉(zhuǎn)步驟（置）（，令；如果令；如果，令如果）（令，；如果，令如果）（）（）（）（，令得到子問題的最優(yōu)解）（）（）（）（）（）（）（）（）（）（21kk.62rrrrr21r.5dxxxx.4d-xf)dx(f-fdk1kkk1kkk1kkkk1kkk1kkkkkkk)(kkkx第13頁/共26頁第十四頁，共27頁。優(yōu)解，試用信賴域方法求最，取信賴域半徑取初點(diǎn)）（：）（43411r,00 x54x-xxxxfmin112222141第14頁/共26頁第十五頁，共27頁。1dd

8、. .dd4d-5dmin1| . .dxfd21dxfxf defdmin2002xfesse4-0 xf5xf2221222121121111211tsdtsHTT）（：即求解）（）（）（）（：解子問題）（矩陣，）（，目標(biāo)函數(shù)的梯度）（解：經(jīng)計(jì)算得到函數(shù)值）（）（）（）（）（）（第15頁/共26頁第十六頁，共27頁。22rr10dxx12-52-5d-xfdxf-xf2d2dxf10ddd121121111111111112111，逼近成功，令）（）（）（）（量之比實(shí)際下降量與預(yù)測下降）（，）（函數(shù)值點(diǎn)，也是最優(yōu)解得到子問題的）（）（）（）（）（）（）（）（）（）（）（）（）（）（TK第1

9、6頁/共26頁第十七頁，共27頁。是最優(yōu)解）（，）（得到經(jīng)過第三次迭代。計(jì)算，令降量之比，實(shí)際下降量與預(yù)測下）（）（，算的得到子問題的解）（：，解子問題）（）（，）（算得到進(jìn)行第二次迭代，經(jīng)計(jì)）（）（）（）（）（）（）（）（）（）（）（）（）（20 x00 xf1xf42rr20dxx21-20-21d0dxf10d4dd . .dd2d-2dmin2002xf,20 xf2xf3332322322222222212221222222ts第17頁/共26頁第十八頁，共27頁。的子列（反證法）。再證不存在不收斂到的子列（反證法），先證存在收斂到。的子列，推出矛盾即可假定存在不收斂到法，的子列即可

10、。使用反證不收斂到證明思路：證明不存在）（，則列用信賴域方法求得的序上連續(xù)，）在（），（），（是有界閉集，）（）（是給定的初始點(diǎn)，上的實(shí)函數(shù)，）是（定理：設(shè)）（）（）（）（00000.|xf|limxxfxfxfxfxf |xxxfkkk211nSS第18頁/共26頁第十九頁，共27頁。方向的下降量。自然不會(huì)小于沿著任何域上最大的下降量，根據(jù)定義，這是在信賴）。（）（量次迭代函數(shù)的預(yù)測下降首先估計(jì)第矛盾是某個(gè)正數(shù)，下面推出，均有對(duì)所有充分大的的子列。反證法，假定存在收斂到）（先證明有對(duì)每個(gè)，使得上連續(xù)，因此存在正數(shù)）在（是有界閉集，由于）（），（為簡便，記證明：）（）（）（）（d-xf|f|k

11、0|xf|M.|f|xf.xffxffkkkkk22k2k2kkkkMSS第19頁/共26頁第二十頁，共27頁。r|f|21r|f|2fff2-r|f|f|rfff10.5.9r2|f|fff2|f|r00dfff|f|, 0|f|2fff-|f|f|f-f|f|f-21)|f|f- (f(f -xfff-xf|f|f-dk2k2kkk2kk2k3kkkk2kk2kkk2k4kkkk2k3k22kkk2kkk2kk2k2kk2kk2)(kk2kkkk2kTTTTTTTkQMQQxQ下降量）式，即時(shí)，根據(jù)（當(dāng)）時(shí)，下降量，（當(dāng)是最速下降方向，因此由于得到平穩(wěn)點(diǎn)）（令）（）（）（）（）（）（時(shí)的下

12、降量沿著這個(gè)方向步長為向個(gè)下界，取最速下降方為給出最大下降量的一）（）（）（10.5.8）（10.5.9）（10.5.10）（10.5.11）（10.5.12第20頁/共26頁第二十一頁，共27頁。0.rlim0.rlim. 0010.5.15xf|f|minr21xf-xf10.5.14,|f|k|f|minr|f|21d-xf xf-xfd-xfxf-xf|f|minr|f|21d-xf10.5.1210.5.10kkkkkkk1kkkkkkkkk1kkkkk1kkkkkkkki。綜上分析均導(dǎo)致信賴域半徑減小間的不成功步，對(duì)于任意兩個(gè)成功步之由此可見，對(duì)于成功步，從而右端也趨于）式左端趨于

13、時(shí)，（列，必有極限，由此當(dāng)）為單調(diào)減有下界數(shù)（由于（，）（）（）式得到由此由（，有根據(jù)假設(shè)，對(duì)充分大的，）（）（）（）（由此得到）（）（）（）（對(duì)于成功步，）（）（）式，預(yù)測下降量）式和（綜合（）（）（）（）（）（）（）（）（）（）（）（）（）（kMMM）（10.5.13）（10.5.14）（10.5.15第21頁/共26頁第二十二頁，共27頁。k2k2kkkkkk2kkkkk2kkkk2kkkkk2kkk2kkkkkkkk2kkkkkkkkkkkkkkkkkkkkkkkkkkkkr21|d|21|d|21d-xf|dfd21ddxfd21-|1-|dfd21ddxfd21-dfd21dfxf

14、 ddxfd21dfxf -ddxf -r21r|f|21d-xf10.5.13,d-xfddxf -1-d-xfdxf -xf1-MMkTTTTTTTT）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（因此）（）（）（）（）（）（分子，）（）（分母）式知上式得有（對(duì)于充分大的）（）（）（）（）（）（）（）（）（10.5.16第22頁/共26頁第二十三頁，共27頁。3minr61xf-xf10.5.14k.31|f|k.31|f|0|xf|.|f|,f0|xf|lim0

15、|xf|.1lim0rlimr1.lim0rlim.r2k1kkikiiikkkkkkkkkkkkkkkkkiiiMkkkkMiii，）（）（）式得到步迭代成功，則由（且第如果，有對(duì)每個(gè)，有對(duì)每個(gè)，集的子列，因此存在指標(biāo)存在收斂到）（根據(jù)前面證明，有對(duì)每個(gè)及正數(shù)子序列，用反證法，假設(shè)存在）（下面證明的子列。存在收斂到）（因此，矛盾時(shí)非減，這與時(shí)，義，當(dāng)另一方面，根據(jù)算法定，因此前面已經(jīng)證明了）（）（）（）（）（）（10.5.17）（10.5.18第23頁/共26頁第二十四頁，共27頁。0|xf|lim323131|f|f-f|ff-f|f|10.5.2010.5.1810.5.1731|f-f

16、|i0.|f-f|0 x-xxf. 00 xf-xfxf-xf xf-xf xf-xf |x-x|x-x|x-x|61|x-x|6110.5.19.k10.5.19xx|,x-x|61xf-xf0kkkkkkkkkkkkkkkkkkik1kk1k1kkiiiiiiiiiiiiiiii1 - i2i1i1iii1 - i2i1i1iiii）（因此矛盾。）式得出）式和（），（由（能保證，因此取充分大的指標(biāo)趨于時(shí)，趨于當(dāng)上連續(xù)，）在有界集（由于，因此左端也趨于式右端趨于當(dāng)指標(biāo)趨于無窮時(shí)，上）（）（）（）（）（）（）（）（）（）式推得利用（成立）式對(duì)每個(gè)，因此（由于對(duì)不成功步）（）（，因此有由于不等式左端趨于）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（