【正文】 SW(SorensonWolfe 21121( ) ( )4, ( ) ( )??????k T kkk k T k kd f x gd f x d?Daniel 115, ()???TkkkTkggdg? k Dixon ( 1 )( 1 ) ( 1 ) ( 1 ) ( 1 )()( ) ( ) ( ) ( )( 1 ) ( ) ( )1, ( ) , 0.2 , ( ) , , ,( ) m i n ( ) jj j j jjjj j jjxy x d f y k jfyf y d f y dy y d???? ? ????? ? ?? ? ???? ? ???給 定 初 始 點 , 允 許 誤 差 0. 置若 則 停 止 計 算 否 則 作 一 維 搜 索求 滿 足 令 FR共軛梯度法 3,如果 j n,轉(zhuǎn)步 4,否則 ,轉(zhuǎn) 5 ( 1 ) ( 1 ) ( )2( 1 )2()4 , ( )()(): 1 , 2.j j jjjjjd f y dfyfyjj????????????令 = 其 中 置 轉(zhuǎn) 步( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )5 , , ( )1 , : 1 , 2.j n kx y y x d f yj k k? ? ?? ? ??? ? ?令 = ,置 轉(zhuǎn) 步可以證明 ,對一般函數(shù) ,共軛梯度法在一定條件下是收斂的 , FR算法中使用精確線搜索，我們有如下收斂性結(jié)果 k1: ( )L i ps c hi t z . F RA r m i j o 0 , 0 ,l i m i nf 0( A r m i j o( ) ( ) ( ) )????? ????? ? ??? ? ? ?nkkkkk k k k T kkkf R R f xkggf x d f x c f x d 假 設(shè) 函 數(shù) 有 下 界 ， 梯 度 是連 續(xù) 的 在 共 軛 梯 度 法 中 ， 步 長 參 數(shù) 是由 精 確 線 搜 索 確 定 的 ， 并 且 滿 足 充 分 下 降 條 件 ( 即條 件 ). 若 則 條 件 : 選 擇 步 長 滿 足 定 理4. 1 擬牛頓條件和算法步驟 擬牛頓法 基本思想 : 牛頓法成功的關(guān)鍵在于利用了 Hesse矩陣提供的曲率信息，而計算 Hesse矩陣工作量大，并且有的目標(biāo)函數(shù)的 Hesse矩陣很難計算，甚至不好求出，這就導(dǎo)致僅利用目標(biāo)函數(shù)一階導(dǎo)數(shù)的方法 ,擬牛頓法就是利用目標(biāo)函數(shù)值 f和一階導(dǎo)數(shù) g的信息 ,構(gòu)造出目標(biāo)函數(shù)的 曲率近似，而不需要明顯形成 Hesse矩陣，同時具有收斂速度快的優(yōu)點。 牛頓法的迭代公式為 擬牛頓法 ( 1 ) ( ) ( ) ( 1 0 .4 .1 )k k kkx x d?? ?=( ) ( )kkdx 其 中 是 在 處 的 牛 頓 方 向( ) 2 ( ) 1 ( )( ) ( ) 1 0 2k k kd f x f x?? ? ?= ( . 4 . )()k .kx? 是 從 出 發(fā) 沿 牛 頓 方 向 搜 索 的 最 優(yōu) 步 長2 ( ) 1 2 ( ) 1( ) , ( )kkkf x H f x????為 構(gòu) 造 的 近 似 矩 陣 先 分 析與 一 階 導(dǎo) 數(shù) 的 關(guān) 系 . ( 1 ) ( 1 ) ( 1 )( 1 ) 2 ( 1 ) ( 1 )( ) ( ) ( ) (( ( ) (k k T kk T k kf x f x f x x xx x f x x x? ? ?? ? ?? ? ? ?? ? ?)+1 ) )2( 1 ) ( 1 ), ( ) Ta y l o rkkk x f x x??設(shè) 在 第 次 迭 代 后 , 得 點 將 在 點 展 開( 1 ) 2 ( 1 ) ( 1 )( ) ( ) ( ) ( ) ( ( 1 0 . 4 . 3 )k k kg x f x f x f x x x? ? ?? ? ? ? ?+ ) ( 1 )kx ?于 是 在 附 近()kxx?令 ,則( ) ( 1 ) 2 ( 1 ) ( ) ( 1 )( ) ( ) ( ) (k k k k kf x f x f x x x? ? ?? ? ? ? ?+)記 擬牛頓法 ( ) ( 1 ) ( )( ) ( 1 ) ( )( 10 .4 .4)( ) ( ) ( .5)k k kk k kp x xq f x f x????? ? ? ? 則 ( ) 2 ( 1 ) ( )( ) ( 1 0 . 4 . 6 )k k kq f x p???2 ( 1 )H e s s ia n ( ) ,kfx ??設(shè) 矩 陣 可 逆 則( ) 2 ( 1 ) 1 ( )( ) ( 1 0 . 4 . 7 )k k kp f x q????( ) ( ) ( 1 )12 ( 1 ) 11, , ( 10 .4 .7 )He ss i a n . He ss i a n( ) ,k k kkkkp q xHf x H??????于 是 計 算 出 和 可 根 據(jù) 估 計 在 處 的矩 陣 的 逆 令 取 代 牛 頓 法 中 的 陣的 逆 則 滿 足()稱為 擬牛頓條件 (方程 )， 也稱為 割線方程 . 怎樣確定滿足這個條件的 H k+1 ? 擬牛頓法 ( ) ( )1= ( 1 0 . 4 . 8 )kk kp H q?算法 擬牛頓法 000011 ( ) , ( 0 , 1 )( ) , 0.2( ) , , ,3 ( ) , ( , ) { | , 0 }, ??? ? ?? ? ????? ? ? ???n n nkkkkk k k kk k kkkx R H Rg f x kgd H gR x d x x x dx x d??????初 始 化 給 定 初 始 點 , 正 定 矩 陣 ,。計 算 置平 穩(wěn) 性 檢 驗 若 則 停 止 否 則 , 計 算 搜 索 方 向線 搜 索 沿 射 線 進 行 線 搜 索 ，求 出 步 長 令 擬牛頓法 1114 = ( ) ,k k ?????kkkkg f x HH( 修 正 擬 牛 頓 方 程 ), 計 算 對 校 正 ， 得使 滿 足 擬 牛 頓 條 件 ， 令 ＋ 1 ， 轉(zhuǎn) 24. 2 對稱秩 1校正 2 ( ) 1111( ) ,., ,.kkkkf x nHnH n IHH????當(dāng) 是 階 對 稱 正 定 矩 陣 時 滿 足 擬 牛 頓 條 件的 矩 陣 也 應(yīng) 是 階 對 稱 矩 陣 于 是 構(gòu) 造 如 此 的 近 似矩 陣 的 一 般 策 略 是 :取 為 任 意 一 階 對 稱 正 定 矩 陣 ( 如 單 位 陣 ) 然 后 通 過 修 正 給 出 令?Hk稱為 校正矩陣 .確定 ?Hk的一個方法是令 擬牛頓法 1 ( 1 0 .4 .9 )k k kH H H? ? ? ?( ) ( )k k TkkH Z Z??? () () .kk Zn? 是 一 常 數(shù) , 是 維 列 向 量() ( 1 0 . 4 . 8 ) ,kZ 的 選 擇 應(yīng) 使 得 到 滿 足 令( ) ( ) ( ) ( ) ( )k k k k T kkkp H q Z Z q???() 從而 ( ) ( )()( ) ( )kkk kk T kkp H qZZq??? () 利用 (),(),()可寫成 擬牛頓法 ()( 1 0 . 4 . 1 1 ) ,kTq等 號 兩 端 左 乘 整 理 得( ) T ( ) ( ) ( ) ( ) 2( ) ( )k k k k T kkkq p H q Z q???() ( ) ( ) ( ) ( )1 ( ) T ( ) ( )( ) ( )()k k k k Tkkkk k k kkp H q p H qHHq p H q??????() 秩 1校正公式 利用秩 1校正極小化函數(shù) f(x),在第 k次迭代中 ,令 搜索方向 ( ) ( )()kkkd H f x? ? ?() 擬牛頓法 ()k kd ?然 后 沿 方 向 搜 索 , 求 步 長 , 滿 足( ) ( ) ( ) ( )0( ) m i n ( )k k k kkf x d f x d??? ?? ? ? 確定后繼點 ( 1 ) ( ) ( )k k kkx x d?? ?? () 對稱秩 2校正 擬牛頓法 定義校正矩陣 ( ) ( ) ( ) ( ) T( ) T ( ) ( ) T ( )k k T k kkkk k k k kkp p H q q HHp q q H q? ? ?() DFP(DavidonFletcherPower)公式 ( ) ( ) ( ) ( ) T1 ( ) T ( ) ( ) T ( )k k T k kkkkk k k k kkp p H q q HHHp q q H q? ? ? ?() 則 ?1， DFP算法 (變尺度法 ) DFP算法 擬牛頓法 ()( 1 )1( 1 )1()( ) ( )( ) ( ) ( ) ( )0( 1 ) ( ) (1 , , 0 ,2 , , ( )13 , 4 , , , ,( ) m i n ( )knnkkkkkkk k k kkk k kkSt e p x ESt e p H I xg f xkSt e p d H gSt e p x df x d f x dx x d????????????????? ? ???給 定 初 始 點 允 許 誤 差置 計 算 出 在 處 的 梯 度置令從 出 發(fā) 沿 進 行 一 維 搜 索 求 使 令), ( 1 )( 1 )( 1 ) ( 1 )( 1 ) ( ) ( 1 ) ( ) ( )1115 , , ( ) , , , 66 , , , 2 。 , 77, ( ) , , ,( 10 . 8 ) , : 1 , 3kkkk k k k kk k kkSte pfxx x Ste pSte p k n x x Ste p Ste pSte p g f x p x x q g gH k k Ste p??????????????? ? ? ? ? ???檢 驗 是 否 滿 足 收 斂 準(zhǔn) 則 若停 止 得 否 則 轉(zhuǎn)若 則 令 轉(zhuǎn) 否 則 轉(zhuǎn)令由 公 式 計 算 置 轉(zhuǎn)例 1用 DFP方法求解下列問題 221 2 1m in 2 4 2x x x? ? ?初始點及初始矩陣分別為 ( 1 )12 1 0,1 0 1? ? ? ???? ? ? ?? ? ? ?xH12( , ) Tx x x?在 點 的 梯 度124( 1 )2xgx????????第 1次迭代 (1)x在 點 處 的 梯 度142g???????令搜索方向 ( 1 )1142d H g???? ? ??????( 1 ) ( 1 ),:xd ? 1從 出 發(fā) 沿 方 向 進 行 一 維 搜 索 , 求 步 長( 1 ) ( 1 )0m i n ( )f x d? ?? ?得到 1518? ?令 ( 2 ) ( 1 ) ( 1 )12 4 8 / 951 2 4 / 918x