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