【文章內(nèi)容簡(jiǎn)介】 2 ,k k k k k kkkx x d x f x f xk???? ??? ? ? ? ? ???? 為沿牛頓方向進(jìn)行一維搜索的最佳步長(zhǎng)，可稱為阻尼因子。 可通過(guò)如下極小化過(guò)程求得 ? ? ? ? ? ?1 m ink k k k kkf x f x d f x d???? ? ? ? ?k?k?? ? ? ?12k k kd f x f x???? ? ? ???? ? ? ?12k k kd f x f x???? ? ? ??? 如果把 看作是一個(gè)方向， 稱其為牛頓方向，則阻尼牛頓法的迭代公式為： 這樣，原來(lái)的牛頓法就相當(dāng)于阻尼牛頓法的步長(zhǎng)因子 取成固定值 1的情況。 由于阻尼牛頓法每次迭代都在牛頓方向上進(jìn)行一維搜索，這就避免了迭代后函數(shù)值上升的現(xiàn)象，從而保持了牛頓法二次收斂的特性，而對(duì)初始點(diǎn)的選取并沒(méi)有苛刻的要求。 k?阻尼牛頓法的計(jì)算步驟如下： 1）給定初始點(diǎn) ，收斂精度 ，置 。 0x ? 0k ?2）計(jì)算 和 。 ? ? ? ? ? ? 122k k kf x f x f x ???? ? ???、? ? ? ?12k k kd f x f x???? ? ? ? ???3）求 ，其中 為沿 進(jìn)行一維搜索的最佳步長(zhǎng)。 1k k kkx x d?? ?? k? kd4）檢查收斂精度。若 則 ，停機(jī)；否則，置 ，返回到 2繼續(xù)進(jìn)行搜索。 1kkxx ?? ?? *1kxx??1kk??牛頓法優(yōu)點(diǎn) (1) 如果 *G 正定且初始點(diǎn)選取合適， 算法 二階收斂． (2) 構(gòu)造搜索方向利用了函數(shù)的所有的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)，產(chǎn)生的搜索方向直指極小點(diǎn)； (3)對(duì)于正定二次函數(shù)，從任意初始點(diǎn)出發(fā)，一次迭代即可得到極小點(diǎn)。對(duì)于一般函數(shù)，迭代的次數(shù)比其它算法都要少。 阻尼牛頓法在特定條件下它具有收斂最快的優(yōu)點(diǎn)，并為其他的算法提供了思路和理論依據(jù) 牛頓法缺點(diǎn) (1) (2) 對(duì)多數(shù)問(wèn)題算法不是整體收斂的． 每次都需要計(jì)算 ,kG計(jì)算量大． (3) 每次都需要解 。kk gdG ??方程組有時(shí)奇異或病態(tài)的， 無(wú)法確定 ,kd或 kd不是下降方向． (4) 收斂到鞍點(diǎn)或極大點(diǎn)的可能性并不?。? (5)初始點(diǎn)需選在 X*附近，有一定難度 用阻尼牛頓法求解： ? ? ? ? ? ? Txxxxxxf 0,01m i n 0222141 ?????解： ??????????????????21102000 Gg顯然 0G不是正定的， 但： ???????? ???011210G于是， ???????? ???? ?020100 gGd沿方向 0d進(jìn)行線搜索， ? ?,116 400 ??? ?? dxf得其極小點(diǎn) .00 ??從而迭代不能繼續(xù)下去． 帶保護(hù)的牛頓法算法 給出 0:,210 ?? kRx n ??Step1: kG若 為奇異的，轉(zhuǎn) Step8，否則， Step2: 令 ,1 kkk gGd ???Step3: 若 ,1 kkkTk dgdg ??為奇異的，轉(zhuǎn) ，否則，則轉(zhuǎn) Step8，否則， Step4: 若 ,1 kkkTk dgdg ??則轉(zhuǎn) Step9，否則， Step5: 沿方向 kd進(jìn)行線搜索， 求出 ,k?并令 .1 kkkk dxx ????Step6: 若 ,21 ???kg停； Step7: 令 ,1?? kk轉(zhuǎn) Step1； Step8: 令 ,kk gd ?? 轉(zhuǎn) Step5； Step9: 令 ,kk dd ?? 轉(zhuǎn) Step5. 用帶保護(hù)的牛頓法求解： ? ? ? ? ? ? Txxxxxxf 0,01m i n 0222141 ?????解： ??????????????????21102000 Gg顯然 0G不是正定的， 但： ???????? ???011210G于是， ???????? ???? ?020100 gGd因?yàn)椋? ,000 ?dg T故令， ,2000 ???????????? gd沿 0d進(jìn)行線搜索得： ,210 ??? ? 0,1011 ??????????? xfx第二次迭代： ????????????????? ??2110,0111 Gg而： ???????? ???? ?121111 gGd使 ,0211 ??dg T 故令 ?????????????????? ???12121d沿 1d進(jìn)行線搜索， 得出 ,3 4 7 9 4 2 1 ??于是 : ? ? 22 ???????????? xfx此時(shí) : ???????? ???0 72g1 ( 0 , 1 , 2 , )k k kk sk?? ? ? ?xx1 ( ) ( 0 , 1 , 2 , )k k kka f k? ? ? ? ?x x x1 2 1[ ( ) ] ( ) ( 0 , 1 , 2 , )k k k kf f k??? ? ? ? ?x x x x1 2 1[ ( ) ] ( ) ( 0 , 1 , 2 , )k k k kk f f k?? ? ? ? ?x x x x一般迭代式： 梯度法： 牛頓法： 阻尼牛頓法： 梯度法與牛頓法： 梯度法構(gòu)造簡(jiǎn)單，只用到一階偏導(dǎo)數(shù)，計(jì)算量小，初始點(diǎn)可任選，且開(kāi)始幾次迭代，目標(biāo)函數(shù)值下降很快；其主要缺點(diǎn)是迭代點(diǎn)接近 X*時(shí)，即使對(duì)二次正定函數(shù)收斂也非常慢。 牛頓法收斂很快，對(duì)于二次函數(shù)只需迭代一次便達(dá)到最優(yōu)點(diǎn)，對(duì)非二次函數(shù)也能較快迭代到最優(yōu)點(diǎn)，但要計(jì)算二階偏導(dǎo)數(shù)矩陣及其逆陣，對(duì)維數(shù)較高的優(yōu)化問(wèn)題，其計(jì)算工作和存儲(chǔ)量都太大。 針對(duì)梯度法收斂速度慢，提出收斂速度更快的共軛梯度法。 針對(duì)牛頓法的缺點(diǎn)提出了變尺度法。 變尺度法 一：尺度矩陣的概念 變量的尺度變換是指放大或縮小各個(gè)坐標(biāo)。 通過(guò)尺度變換可以把函數(shù)的偏心程度降低到最低限度。尺度變換技巧能顯著地改善幾乎所有極小化方法的收斂性質(zhì)。 求目標(biāo)函數(shù) 的極小點(diǎn)。 ? ? 221225f x x x??引入變換 ? ?1122221 2 1 25,yxyxy y y y?????若矩陣 G是正定的，則總存在矩陣 Q，使得： 即將函數(shù)的偏心降為 0 對(duì)于一般二次函數(shù) ? ? 12TTf x x G x b x c? ? ?如果進(jìn)行尺寸變換 x Q x?則在新的坐標(biāo)系中，函數(shù) 的二次項(xiàng)變?yōu)? 1122T T Tx G x x Q G Q x?? ?fxTQ G Q I?（單位矩陣） 這說(shuō)明二次函數(shù)矩陣 G的逆陣，可以通過(guò)尺度變換矩陣 Q來(lái)求得。 牛頓方向便可寫成 ? ? ? ?? ?11k k T kk k k k T kkkd G f x Q Q f xx x d x Q Q f x????? ? ? ? ? ?? ? ? ? ?牛頓迭代公式變?yōu)? 用 右乘等式兩邊，得 1TQ G Q ??再用 Q左乘等式兩邊，得 TQ Q G I?所以 1TQ Q G ??1Q?例子： ? ? ? ?1221 2 1 2 1 222022, 250 5022200 501021052,Txf x x x x x x x GxxGQx Qx????? ? ? ??????? ???????????????????????其中 若取 作變換 則在變換后的坐標(biāo)系中，矩陣 G變?yōu)? 111002 0 1 0221 0 50 1 0 1005 2 5 211 100 022 2111000505 2 5 2TTQ G Q IG Q Q?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ? ??? ? ? ? ??? ? ? ?? ? ? ??? ? ? ? ??? ? ? ? ????? ? ? ?則只需通過(guò)一次迭代即可求得極小點(diǎn) ? ?* 00 Tx ?比較牛頓法迭代公式 ? ?? ?11k k T kkk k kkx x f xx x f x????? ? ?? ? ?和梯度法迭代公式 可以看出，差別在于牛頓法中多了 部分 (稱為尺度矩陣 H)。 T 故牛頓法就可以看成是經(jīng)過(guò)尺度變換后的 梯度法。經(jīng)過(guò)尺度變換，使函數(shù)的偏心率減小到 0，函數(shù)的等值面變成球面，使設(shè)計(jì)空間中任意點(diǎn)處的梯度都通過(guò)極小點(diǎn)。（對(duì)二次函數(shù)）。 二、變尺度矩陣 對(duì)于一般函數(shù) f(x)，當(dāng)用牛頓法尋求極小點(diǎn)時(shí)，其牛頓迭代公式為 ? ?? ?112( 0 , 1 , 2 , )kk k k kkkkkx x G g kg f xG f x???? ? ????? 為了避免在迭代公式中計(jì)算海賽矩陣的逆矩陣 ，可以用在迭代中逐步建立的變尺度矩陣 1kG?? ?kkH H x? 來(lái)替換 ，即構(gòu)造一個(gè)矩陣序列 來(lái)逼近海賽逆矩陣序列 。 1kG? ? ?kH? ?1kG?1 ( 0 , 1 , 2 , )kk k k kx x H g k?? ? ? ? 其中 是從 出發(fā)，沿方向 搜索而得到的最佳步長(zhǎng)。 k? kx k kkd H g?? 1） 為了保證迭代公式具有下降性質(zhì)，要求 Hk中的每個(gè)矩陣都是對(duì)稱正定的 為了使變尺度矩陣 確實(shí)與 近似，并必須附加某些條件： kH 1kG?證：若要求搜索方向 為下降方向，即要求 也就是 ，即 ，即 應(yīng)為對(duì)稱正定。 k kkd H g??0Tkkgd ? 0Tk k kg H g?? 0Tk k kg H g ? kH2）要求 之間的迭代具有簡(jiǎn)單的形式。顯然 kH1k k kH H E? ?? 為最簡(jiǎn)單的形式，其中 為校正矩陣。上式稱作校正公式。 kE3）要求 必須滿足擬牛頓條件。 ? ?kH擬牛頓條件： 設(shè)迭代過(guò)程已經(jīng)進(jìn)行了 k+1步， ， 均已求出，現(xiàn)在推導(dǎo) 所需要的條件： 當(dāng) f(x)為具有正定矩陣 G的二次函數(shù)時(shí)， 1kH ?1kg ?1kx ? 因?yàn)榫哂姓êＹ惥仃? 的一般函數(shù)，在極小點(diǎn)附近可用二次函數(shù)很好的近似，所以 1kG?如果迫使 滿足類似于上式的關(guān)系 1kH?? ? 111 kkk k kH g g x x??? ? ? ?那么 就可以很好地近似于 。 kH 11kG??? ? ? ?? ?? ? kkkkkkkkTkkTkkTTTTxxggGxxGggbGxgbGxgbGxxfcxbGxxxf???????????????????????1