最優(yōu)化方法 尹秋響課件第五章

1、本章要點(diǎn)：本章要點(diǎn)：單純形單純形單純形搜索法的基本思想單純形搜索法的基本思想共軛方向、共軛方向法的基本定理共軛方向、共軛方向法的基本定理PowellPowell共軛方向法的基本思想共軛方向法的基本思想最速下降法的基本思想及特點(diǎn)最速下降法的基本思想及特點(diǎn)NewtonNewton法基本思想及特點(diǎn)法基本思想及特點(diǎn)牛頓方向牛頓方向MarquardtMarquardt法基本思想法基本思想最小二乘問題最小二乘問題共軛梯度法基本思想共軛梯度法基本思想擬擬NewtonNewton法的基本思想法的基本思想第五章第五章 無約束非線性問題的解法無約束非線性問題的解法 學(xué)習(xí)的重要性：學(xué)習(xí)的重要性：1、直接用于無約束的

2、實(shí)際問題；直接用于無約束的實(shí)際問題；2、其基本思想和邏輯結(jié)構(gòu)可以推廣到約束問題；其基本思想和邏輯結(jié)構(gòu)可以推廣到約束問題；3、約束問題可以轉(zhuǎn)化成無約束問題求解。約束問題可以轉(zhuǎn)化成無約束問題求解。方法分類：方法分類：1、間接法：、間接法：對簡單問題，求解必要條件或充分條件；對簡單問題，求解必要條件或充分條件；2、迭代算法：、迭代算法：零階法：只需計算函數(shù)值零階法：只需計算函數(shù)值 f(x) 一階法：需計算一階法：需計算 f(x)二階法：需計算二階法：需計算 2f(x) 直接法直接法梯度法梯度法5.1 直接直接搜索法搜索法優(yōu)點(diǎn)：計算不太復(fù)雜；易于實(shí)施與快速調(diào)試；所需的準(zhǔn)備時間較少優(yōu)點(diǎn)：計算不太復(fù)雜；易

3、于實(shí)施與快速調(diào)試；所需的準(zhǔn)備時間較少5.1.1 單純形搜索單純形搜索法法1962年由年由Spendley, Hext和和Himsworth提出，提出，80年代得到證明年代得到證明 x1 x2 x3 （一）（一）單純形單純形空間中最簡單、其空間中最簡單、其 “維數(shù)維數(shù)”與空間維數(shù)相同的圖形與空間維數(shù)相同的圖形 x2 x1 n維空間中具有維空間中具有n+1個頂點(diǎn)的個頂點(diǎn)的 “n維超多面體維超多面體” 稱為稱為n維單純形維單純形如果各頂點(diǎn)間的距離（棱長）相等，則稱為正規(guī)單純形如果各頂點(diǎn)間的距離（棱長）相等，則稱為正規(guī)單純形（二）（二）單純形法的基本思想單純形法的基本思想初始單純形初始單純形搜索方向搜

4、索方向與步長與步長 比較單純形比較單純形頂點(diǎn)的函數(shù)值頂點(diǎn)的函數(shù)值 新近似點(diǎn)新近似點(diǎn) 新的單純形新的單純形以以 min f(x1, x2)為例為例 ，說明迭代過程，說明迭代過程x2x1PHPLfH fG fL PFPR反射反射PR fRfR 擴(kuò)張失敗擴(kuò)張失敗 PS =PR新單純形新單純形PGPLPS PSPEPSPR壓縮壓縮PS fS 0，令，令 x( i ) = x( 0 )+he( i ) , (i=1,2,n) 其中其中 e( i ) = (0,.,0,1,0,0)T 為單位坐標(biāo)向量為單位坐標(biāo)向量 第第i個分量為個分量為1 x2 x1 x(0)x(1)x(2)hh(2) 取初始步長取初始步

5、長h0，令，令 x( i ) = x( 0 )+Z( i ) , (i=1,2,n) 其中其中 Z( i ) = (q,.,q,p,q,q)T第第i個分量為個分量為p hnnq211 hnnnp211x2x1x(0)x(1)x(2)hqp p q棱長為棱長為h的正規(guī)單純形的正規(guī)單純形 2、計算函數(shù)值計算函數(shù)值fi = f (x(i)，(i=0,1,2,n)，并比較大小，找出最差點(diǎn)，并比較大小，找出最差點(diǎn) x(H)，次差，次差 點(diǎn)點(diǎn)x(G) 和最好點(diǎn)和最好點(diǎn)x(L)，即，即fL = f (x(L) = min fi fH = f (x(H) = max fi fG = f (x(G) = max

6、 fi 0in 0in 0in iH 計算除去計算除去x(H)后的形心后的形心 x(F) )(1)(1Hniixxn3、按終止準(zhǔn)則判斷是否已達(dá)到精度要求，若已達(dá)到，停止計算，否則轉(zhuǎn)按終止準(zhǔn)則判斷是否已達(dá)到精度要求，若已達(dá)到，停止計算，否則轉(zhuǎn)44、求反射點(diǎn)求反射點(diǎn)x(R)5、將將fR 與與fL ，fG 和和fH 作比較作比較 (1)若若fRfL ,反射成功，進(jìn)行擴(kuò)張，擴(kuò)張點(diǎn)反射成功，進(jìn)行擴(kuò)張，擴(kuò)張點(diǎn)x(E) 若若fEfL ，擴(kuò)張成功，令，擴(kuò)張成功，令 x(H)= x(E) ,轉(zhuǎn)向轉(zhuǎn)向2 否則，擴(kuò)張失敗，令否則，擴(kuò)張失敗，令 x(H)= x(R) ,轉(zhuǎn)向轉(zhuǎn)向2(2)若若fLfRfG ,反射成功，但

7、改進(jìn)不大，不進(jìn)行擴(kuò)張，反射成功，但改進(jìn)不大，不進(jìn)行擴(kuò)張， x(H)= x(R) ,轉(zhuǎn)向轉(zhuǎn)向2(3)若若fGfRfH ,反射不太成功，在反射不太成功，在x(F)與與 x(R)之間壓縮之間壓縮(4)若若fRfH , 反射失敗，在反射失敗，在x(H)與與 x(F)之間壓縮之間壓縮 6、若若fSfH ，壓縮成功，令，壓縮成功，令 x(H)= x(S) ,轉(zhuǎn)向轉(zhuǎn)向2 否則，進(jìn)行收縮。否則，進(jìn)行收縮。 PHPGPLPFPRPE幾點(diǎn)說明：幾點(diǎn)說明：1、關(guān)于初始步長關(guān)于初始步長h的選取的選取 （一般可取（一般可取0.5h15） (1) 開始取開始取h為為1.62；(2) 進(jìn)行到發(fā)現(xiàn)進(jìn)行到發(fā)現(xiàn)fH fL 已已

8、很小，但尚未達(dá)到精度，這時取很小，但尚未達(dá)到精度，這時取x(0)= x(L)， 重新開始重新開始， 并取步長為：并取步長為： 當(dāng)離精度要求已不遠(yuǎn)時，當(dāng)離精度要求已不遠(yuǎn)時，h=0.51； 當(dāng)離精度要求還很遠(yuǎn)時，當(dāng)離精度要求還很遠(yuǎn)時，h 2。2、終止準(zhǔn)則終止準(zhǔn)則 P1093、擴(kuò)張因子擴(kuò)張因子 r =1.22例例5.1.1 用單純形搜索法求解用單純形搜索法求解 min f(x) =6010 x14x2x12 +x22x1x2 設(shè)設(shè)x(0)=0, 0T , e(1) = 1, 0T, e(2) = 0, 1T, 取取h=2, =0.5, =2, =1, 終止準(zhǔn)則為終止準(zhǔn)則為|(fHfL)/fL|0.0

9、01x1 x2x(H)x(G)x(F)x(R)x(E)x(L)x1x2x(H)x(L)x(G)x(F)x(R)x1x2x(G)x(H)x(L)x(F)x(R)x(E)5.1.3 Powell共軛方向共軛方向法（方向加速法）法（方向加速法） 1964年由年由Powell提出，后經(jīng)提出，后經(jīng)Zangwoll（1967年）和年）和Brent（1973年）改進(jìn)，年）改進(jìn)， 是迄今為止是迄今為止最有效的直接搜索法最有效的直接搜索法。 該算法該算法有效有效地地利用利用了了迭代迭代過程中的過程中的歷史信息歷史信息，建立起能，建立起能加速收斂加速收斂的方向的方向 有理論基礎(chǔ)，有理論基礎(chǔ)，以二次對稱函數(shù)以二次對

10、稱函數(shù) f(x) = c + bTx + 1/2 xTAx 為模型為模型進(jìn)行研究。進(jìn)行研究。? 為什么選擇二次函數(shù)作為模型為什么選擇二次函數(shù)作為模型 ?1、在非線性目標(biāo)函數(shù)中，最簡單的是二次函數(shù)，故任何對一般函數(shù)有效在非線性目標(biāo)函數(shù)中，最簡單的是二次函數(shù)，故任何對一般函數(shù)有效 的方法首先應(yīng)對二次函數(shù)有效；的方法首先應(yīng)對二次函數(shù)有效；2、在最優(yōu)點(diǎn)附近，非線性函數(shù)可用一個二次函數(shù)作近似，故對二次函數(shù)在最優(yōu)點(diǎn)附近，非線性函數(shù)可用一個二次函數(shù)作近似，故對二次函數(shù) 使用良好的方法，通常對一般函數(shù)也有效；使用良好的方法，通常對一般函數(shù)也有效；3、很多實(shí)際問題的目標(biāo)函數(shù)是二次函數(shù)。很多實(shí)際問題的目標(biāo)函數(shù)是二

11、次函數(shù)。（一）（一）共軛方向共軛方向 設(shè)設(shè)A是是nn階對稱正定矩陣，階對稱正定矩陣，p(0), p(1)為兩個為兩個n維向量，若維向量，若 成立成立 p(0)T A p(1) = 0 則稱向量則稱向量p(0)與與p(1)為為A共軛或共軛或A正交，稱該兩向量的方向為正交，稱該兩向量的方向為A共軛方向。共軛方向。 若若 AI（單位矩陣），（單位矩陣），p(0)T p(1) = 0，即，即p(0)與與p(1)是正交的。是正交的?！肮曹椆曹棥笔鞘恰罢徽弧备拍罡拍畹耐茝V的推廣 =|p(0)|.|p(1)|cos 021 1 , 22121120 , 1 p Ap App , 21p , 01p ,

12、2112A(1)(0)T(1)(0)(1)(0)因為共軛的。是與則例：例：? 共軛方向有什么用共軛方向有什么用 ?（二）（二）共軛方向法的基本定理共軛方向法的基本定理定理定理5.1.1：設(shè)設(shè)A為為nn階對稱正定矩陣，階對稱正定矩陣，p(0), p(1)，, p(n-1)為為n個相互個相互A共軛共軛 的的n維非零向量（即維非零向量（即p(i) 0, i=0,1, n-1, 且且p( i )T A p( j ) = 0，i j），）， 則此向量系必線性無關(guān)。則此向量系必線性無關(guān)。 推推 論：論： 在在n維空間中，互相共軛的非零向量的個數(shù)不超過維空間中，互相共軛的非零向量的個數(shù)不超過n個。個。 定理

13、定理5.1.2：若若p(0), p(1), , p(n-1)是是n個非零的個非零的A共軛向量，則二次目標(biāo)函數(shù)共軛向量，則二次目標(biāo)函數(shù) f(x) = c + bTx + 1/2 xTAx的最優(yōu)點(diǎn)的最優(yōu)點(diǎn) x*為為( )1*( )( )( )0iTniiTiipbxppAp! 可得到非二次函數(shù)最優(yōu)點(diǎn)的一個近似點(diǎn)；其中可得到非二次函數(shù)最優(yōu)點(diǎn)的一個近似點(diǎn)；其中A是是Hesse矩陣！矩陣！? 上式用于非二次函數(shù)，可否得到最優(yōu)點(diǎn)上式用于非二次函數(shù)，可否得到最優(yōu)點(diǎn) ？定理定理5.1.3:設(shè)設(shè)A為為n階對稱正定矩陣，對于二次目標(biāo)函數(shù)階對稱正定矩陣，對于二次目標(biāo)函數(shù)f(x) = c + bTx + 1/2 xT

14、Ax，從任意初始點(diǎn)從任意初始點(diǎn)x(0)出發(fā)，逐次進(jìn)行一維搜索，即出發(fā)，逐次進(jìn)行一維搜索，即 min f ( x( i )+ t p( i ) ) = f ( x( i )+ti p( i ) ) i0 若搜索方向若搜索方向p(0), p(1), , p(n-1)是非零的是非零的A共軛向量，則至多進(jìn)行共軛向量，則至多進(jìn)行n次迭代必可次迭代必可得到極小點(diǎn)得到極小點(diǎn)x* ，即有，即有 x( i+1) =x( i ) +ti p( i ) , i =0,1,n1 x* = x( k ) , 0kn 上述搜索方法具上述搜索方法具有二次收斂性有二次收斂性? 對非二次函數(shù)，采用上述方法，對非二次函數(shù)，采用上

15、述方法，n 次迭代是否也可得到極小點(diǎn)次迭代是否也可得到極小點(diǎn) ？? 如何簡便地找出如何簡便地找出n個個A共軛的向量共軛的向量 ？定理定理5.1.4:假設(shè)假設(shè)1. n元函數(shù)元函數(shù)f(x) = c + bTx + 1/2 xTAx 中的矩陣中的矩陣A是對稱正定的；是對稱正定的；2. 向量向量p(0), p(1), , p(m-1) (mn)是互相是互相A共軛的；共軛的；3. x(0), x(1)是不同的任意兩點(diǎn)，分別從是不同的任意兩點(diǎn)，分別從x(0), x(1)出發(fā)，依次沿出發(fā)，依次沿p(0), p(1), , p(m-1) 作一維精確搜索，設(shè)最后一次一維搜索的極小點(diǎn)分別為作一維精確搜索，設(shè)最后一

16、次一維搜索的極小點(diǎn)分別為x(0)*和和x(1)*, 那么，那么， 向量向量 p = x(0)*x(1)*與與p(0), p(1), , p(m-1)互為互為A共軛。共軛。已知前已知前m個共軛方向，個共軛方向，就可以找到第就可以找到第m+1個共軛方向個共軛方向p(1)x(0)x(1)p(0)p(0)x(0)*x(1)*x*x(0)x(1)p(0)p(0)p(1)p(1)x(0)*x(1)*p(2)x*（三）（三）Powell共共軛方向法的基本思想軛方向法的基本思想) 1, 1 (), 1 () 1, 1 () 2, 1 () 2 , 1 () 1 , 1 () 0 , 1 () 0()0 , 1

17、 (), 1 () 1 () 1()2() 1 ()0( nxxpnpnpnppxxxxxxxxnnn) 1, 2(), 2() 1, 2() 2, 2() 2 , 2() 1 , 2() 0 , 2() 1, 1 ()0 , 2(), 2()2() 1 () 1()2() 1 ( nxxpnpnpnppnxxxxxxxxnn) 1, 3(), 3() 1, 3() 2, 3() 2 , 3() 1 , 3() 0 , 3() 1, 2()0 , 3(), 3()3()2() 1 ()3()2( nxxpnpnpnppnxxxxxxxxn) 1,(),() 1,() 2,() 2 ,() 1

18、,() 0 ,() 1, 1()0,(),()() 1()2() 1() 1( nnxxpnnpnnpnnnpnpnnnxxxxxxxxnnnnnnn表表5.1.1 Powell共軛方向法的迭代過程共軛方向法的迭代過程階段起點(diǎn)階段起點(diǎn)x(k, 0)n+1次一維搜索過程次一維搜索過程新共軛方向新共軛方向)(kp一邊搜索，一邊搜索，一邊找共軛方向一邊找共軛方向共分共分n個階段，每一階段都進(jìn)行個階段，每一階段都進(jìn)行n+1次搜索，最后產(chǎn)生一個共軛方向次搜索，最后產(chǎn)生一個共軛方向任意任意n個線性無關(guān)的方向個線性無關(guān)的方向二維空間中的二維空間中的Powell方法示意方法示意p(0)p(1)e(2)e(1)

19、p(0) =e(1)p(1) =e(2)以以二次函數(shù)二次函數(shù)f(x1 , x2 ) 為例為例x(1,0)x(1,1)x(1,2)(1)pp(1)x(2,2)(2)px(2,0)x(2,1)x*對于二次函數(shù)對于二次函數(shù),x* 即為極小點(diǎn)即為極小點(diǎn)（四）（四）Powell方法的原始算法方法的原始算法開始開始給定給定x(0) , e(1) , e(2) , e(n) 及及 否否x(k) = x(k, n)+k p(n -1) 其中其中k為最優(yōu)步長為最優(yōu)步長 k=1, p( i ) = e(i+1), i=0, 1, , n-1 j=0, x(k, j) = x( k-1 ) x(k, j+1) =

20、x(k, j)+j p( j ) 其中其中j為最優(yōu)步長為最優(yōu)步長 j=j+1 j=n滿足精度滿足精度否否k=k+1 x*=x(k+1)結(jié)束結(jié)束是是是是 p( i ) = p(i+1), i=0, 1, , n-2(, )(,0)(1)(, )(,0)|k nknk nkxxpxx幾點(diǎn)說明幾點(diǎn)說明1、迭代中逐次產(chǎn)生的是共軛方向，是較好的搜索方向，所以迭代中逐次產(chǎn)生的是共軛方向，是較好的搜索方向，所以Powell法又稱法又稱 方向加速法方向加速法；2、原始算法僅有理論意義。原始算法僅有理論意義。因為只有在每次搜索均為一維完全精確搜索因為只有在每次搜索均為一維完全精確搜索的條件下，每個階段產(chǎn)生的方向

21、才是相互共軛的條件下，每個階段產(chǎn)生的方向才是相互共軛的方向。的方向。但實(shí)際一維搜索都是近似的，產(chǎn)生的方向不但實(shí)際一維搜索都是近似的，產(chǎn)生的方向不一定共軛，一定共軛，有時甚至是線性相關(guān)的有時甚至是線性相關(guān)的，導(dǎo)致搜，導(dǎo)致搜索空間降維，這時將找不到真正的極小點(diǎn)。索空間降維，這時將找不到真正的極小點(diǎn)。p(1)x(0)x(1)p(0)p(0)x(0)*x(1)*x*p(1) 對于一般函數(shù)對于一般函數(shù), n個階段迭代后一般得不到極小點(diǎn)個階段迭代后一般得不到極小點(diǎn),但由于共軛方向的個數(shù)只有但由于共軛方向的個數(shù)只有n個個, 如果繼續(xù)按上述如果繼續(xù)按上述方法迭代方法迭代, 產(chǎn)生的方向就不再是相互共軛方向了產(chǎn)生

22、的方向就不再是相互共軛方向了, 收斂速度會變慢收斂速度會變慢.（五）（五）原始算原始算法一種簡便改進(jìn)法一種簡便改進(jìn)重新開始重新開始：每進(jìn)行每進(jìn)行n個階段的迭代，或當(dāng)收斂速度變慢時，以當(dāng)前點(diǎn)為起點(diǎn)，個階段的迭代，或當(dāng)收斂速度變慢時，以當(dāng)前點(diǎn)為起點(diǎn)， 回到第一步重新開始回到第一步重新開始（六）（六）改進(jìn)的改進(jìn)的Powell算法算法1. 基本思想基本思想 :為克服搜索方向的線性相關(guān)問題，為克服搜索方向的線性相關(guān)問題，Powell對原始算法進(jìn)行了改進(jìn)。對原始算法進(jìn)行了改進(jìn)。? 如何判定方向組是如何判定方向組是“最相互共軛最相互共軛”的的 ?定理定理5.1.5 設(shè)設(shè)A是是n階對稱正定矩陣，方向組階對稱正

23、定矩陣，方向組p(0), p(1), ,p(n-1) 按下式意義是規(guī)范化的：按下式意義是規(guī)范化的： p( i )T A p( i ) = 1， ( i=0,1, n-1), 置置Q p(0), p(1), ,p(n-1) ，則方向組，則方向組p(0), p(1), ,p(n-1) 相互相互A共軛的充要條件為：共軛的充要條件為： 行列式行列式 |Q| 的值達(dá)到它的最大值。的值達(dá)到它的最大值。改進(jìn)改進(jìn)Powell算法的算法的理論基礎(chǔ)理論基礎(chǔ)在每個階段產(chǎn)生新的方向在每個階段產(chǎn)生新的方向p后后, 更換方向組的方法更換方向組的方法不是一律去掉第一個方向不是一律去掉第一個方向p(0), 而是有選擇地去掉某

24、個方向而是有選擇地去掉某個方向 p(J), 原則是原則是使新的方向組使新的方向組“ 最相互共軛最相互共軛”5.2 梯度梯度法法直接搜索法收斂速度一般比較慢，需要計算大量的函數(shù)值。直接搜索法收斂速度一般比較慢，需要計算大量的函數(shù)值。梯度反映了函數(shù)值變化的規(guī)律，充分利用梯度信息構(gòu)造算梯度反映了函數(shù)值變化的規(guī)律，充分利用梯度信息構(gòu)造算法，能加速收斂。法，能加速收斂。使用函數(shù)的梯度（一階導(dǎo)數(shù)）或使用函數(shù)的梯度（一階導(dǎo)數(shù)）或Hesse矩陣（二階導(dǎo)數(shù)）的矩陣（二階導(dǎo)數(shù)）的優(yōu)化算法稱為梯度法優(yōu)化算法稱為梯度法目標(biāo)：目標(biāo)：求出平穩(wěn)點(diǎn)求出平穩(wěn)點(diǎn) （滿足（滿足 f(x)=0的的x * ）。）。由于由于 f(x)=

25、0 一般是非線性方程組，解析法往往行不通，一般是非線性方程組，解析法往往行不通， 所以梯度法通常也是逐次逼近的迭代法所以梯度法通常也是逐次逼近的迭代法假定：假定： f(x)和和 2f(x)連續(xù)存在連續(xù)存在5.2.1 最速下降法最速下降法(Cauchy法法)1847年年Cauchy提出。特點(diǎn)提出。特點(diǎn)是是直觀易懂，但收斂速度慢直觀易懂，但收斂速度慢（一）（一）基本思想基本思想x(k+1) = x(k) + tk p(k)x(k)x*p(k) = f(x (k) )x(k+1)p(k+1) = f(x (k+1) )瞎子下山：瞎子下山：由于他看不到哪里由于他看不到哪里是山谷，不可能沿直接指向山是山

26、谷，不可能沿直接指向山谷的路線走，他只能在當(dāng)前位谷的路線走，他只能在當(dāng)前位置上，靠手杖作局部探索，哪置上，靠手杖作局部探索，哪里最陡就往哪里前進(jìn)一步，然里最陡就往哪里前進(jìn)一步，然后在新的位置上再用手杖尋找后在新的位置上再用手杖尋找最陡方向，再下降一步。這就最陡方向，再下降一步。這就是最速下降法的形象比喻。是最速下降法的形象比喻。？多變量最優(yōu)化迭代解法的一般迭代公式多變量最優(yōu)化迭代解法的一般迭代公式可用一維搜索技術(shù)解決可用一維搜索技術(shù)解決關(guān)鍵是如何確定搜索方向關(guān)鍵是如何確定搜索方向p(k)迭代公式迭代公式 x(k+1) = x(k) tk f(x(k) ) （二）（二）算法算法開始開始給定給定x

27、(0) , M , 1 , 2 , 令令 k=0計算計算 f( x(k ) ) | f( x(k ) )| Mx*=x(k)是是結(jié)束結(jié)束是是一維搜索求一維搜索求tk 精度為精度為 2 否否x(k+1) = x(k) tk f(x(k) ) k=k+1 x(k+1)p(k)x(k)f(x)等值面等值面 f(x (k+1) )x(0)x(1)x(2)兩維情形下最速下降法搜索路徑兩維情形下最速下降法搜索路徑（三）（三）最速下降法的搜索路徑呈直角鋸齒形最速下降法的搜索路徑呈直角鋸齒形tk（四）（四）優(yōu)缺點(diǎn)優(yōu)缺點(diǎn)1、優(yōu)點(diǎn)：、優(yōu)點(diǎn)：計算簡單，需記憶的容量??；計算簡單，需記憶的容量?。粚Τ跏键c(diǎn)要求低，穩(wěn)定性

28、高；遠(yuǎn)離極小點(diǎn)對初始點(diǎn)要求低，穩(wěn)定性高；遠(yuǎn)離極小點(diǎn)時收斂快，常作為其它方法的第一步。時收斂快，常作為其它方法的第一步。2、缺點(diǎn)：、缺點(diǎn)：收斂速度較慢（線性或不收斂速度較慢（線性或不高于線性）。原因是最速下降方向只高于線性）。原因是最速下降方向只有在該點(diǎn)附近有意義。有在該點(diǎn)附近有意義。尤其當(dāng)目標(biāo)函數(shù)等值面是很扁的橢圓、尤其當(dāng)目標(biāo)函數(shù)等值面是很扁的橢圓、橢球或類似圖形時，收斂更慢。橢球或類似圖形時，收斂更慢。定理定理5.2.1 設(shè)從點(diǎn)設(shè)從點(diǎn)x(k) 出發(fā)，沿方向出發(fā)，沿方向p作作一維搜索，一維搜索， tk為最優(yōu)步長因子，即為最優(yōu)步長因子，即 f(x(k) + tk p) = min f( x(k)

29、 + t p) 則成立則成立 f(x(k) + tk p) T p =0, 即新點(diǎn)處的梯度與搜索方向垂直。即新點(diǎn)處的梯度與搜索方向垂直。tp(k+1)例例5.2.1 用最速下降法求函數(shù)用最速下降法求函數(shù) f (x1, x2)x12+4x22 的極小點(diǎn)，（迭代兩次），的極小點(diǎn)，（迭代兩次）， 并驗證相鄰兩個搜索方向是正交的。初始點(diǎn)取為并驗證相鄰兩個搜索方向是正交的。初始點(diǎn)取為x(0)=1,1T 。解：解：梯度梯度 f (x)2x1, 8x2 T 。1. 第一次迭代：第一次迭代： f ( x(0) )2, 8 T ， x(1) = x(0) + t0 p(0) = x(0) t0 f (x(0)

30、1,1T t0 2, 8 T 用一維搜索求用一維搜索求t0 ，對簡單，對簡單f(x)，可用解析法求解：，可用解析法求解：設(shè)設(shè) 0 (t)f ( x(1) )f ( 1,1T t2, 8 T )(12t)2+4(18t)2 0(t)520t680 t0 0.130769x(1) =0.738462, 0.046152T2. 第二次迭代：第二次迭代： f ( x(1) )1.476924, 0.369216 Tx(2) = x(1) t1 f (x(1) =0.7384621.476924t10.046152+0.369216t1 1(t)f ( x(2) )(0.7384621.476924t)

31、2+4(0.046152+0.369216t)2 1(t)2.317625t+5.453173t0 t1 0.45005x(2) =0.110762, 0.110767T f ( x(2) )0.221524, 0.886136 T3. 驗證相鄰兩個搜索方向是正交的：驗證相鄰兩個搜索方向是正交的： f (x(0)T f (x(1) =2, 8 1.476924, 0.369216 T =0.00012 0 f (x(1)T f (x(2) = 1.476924, 0.369216 0.221524, 0.886136 T =0.000001 05.2.2 Newton法（二階方法）法（二階方法

32、）？由最速下降法可知，從全局角度來看，負(fù)梯度方向一般不是一個特別由最速下降法可知，從全局角度來看，負(fù)梯度方向一般不是一個特別好的方向，有沒有更好的方向好的方向，有沒有更好的方向 ?)x0(x)f(xx21x)f(x)f(xf(x)3(k)2TT(k)(k) xf(x;(k)f(x)在在x(k)處的處的二次近似函數(shù)二次近似函數(shù)（一）基本（一）基本Newton法法取取 f(x; x(k)的平穩(wěn)點(diǎn)作為的平穩(wěn)點(diǎn)作為f(x) 最優(yōu)點(diǎn)的一個近似點(diǎn)最優(yōu)點(diǎn)的一個近似點(diǎn) f (x; x(k) = f (x(k)+ 2f (x(k) x = 0 x x(k) = x = 2f (x(k)1 f (x(k)Newt

33、on迭代公式迭代公式 x(k+1) = x(k) 2f (x(k)1 f (x(k)x(k)f(x(k)f(x; x(k)x(k+1) 或或 x(k+1) = x(k)H(x(k)1g(x(k)H(x(k)1g(x(k)! 當(dāng)當(dāng)f(x)是二次函數(shù)時，一次迭代就可達(dá)到平穩(wěn)點(diǎn)是二次函數(shù)時，一次迭代就可達(dá)到平穩(wěn)點(diǎn) ！! 當(dāng)當(dāng)f(x)是單變量函數(shù)時，本方法即為是單變量函數(shù)時，本方法即為Newton-Raphson法法！結(jié)束結(jié)束 基本基本Newton法的算法法的算法開始開始給定給定x(0) , , 令令 k=0計算計算g(k) = f( x(k ) ) x*=x(k)是是p(k) =H(x(k)1g(k

34、)x(k+1) = x(k) +p(k) k=k+1否否計算計算 H(x(k)|g(k )| 例例5.2.2 用基本用基本Newton法求函數(shù)法求函數(shù) f (x1, x2)8x12+4x1x2+5x22 的極小點(diǎn)。的極小點(diǎn)。 初始點(diǎn)取為初始點(diǎn)取為x(0)=10, 10T 。解：解： f (x)16x1+4x2, 4x1+10 x2 T 2f (x)H(x)= 16 4 4 10H(x)1 =10 4 4 161144 x(1) = x(0)H(x(0)1 f (x(0)1010= 10 4 4 16114420014000因為因為f(x)是二次函數(shù)，所以一步迭代就達(dá)到平穩(wěn)點(diǎn)，又因為是二次函數(shù)，

35、所以一步迭代就達(dá)到平穩(wěn)點(diǎn)，又因為H(x(1)是正是正定矩陣，所以定矩陣，所以x(1)是極小點(diǎn)。是極小點(diǎn)。說明：說明：1、基本、基本Newton法要求法要求Hesse矩陣具有逆矩陣。矩陣具有逆矩陣。如果如果H(x(k)是正定的，則是正定的，則H(x(k)1必存在，從而算法是可行的，并且保證求得必存在，從而算法是可行的，并且保證求得的平穩(wěn)點(diǎn)是極小點(diǎn)。的平穩(wěn)點(diǎn)是極小點(diǎn)。然而在迭代過程中要求然而在迭代過程中要求H(x(k)是正定的這一條件不一定能保證，只有當(dāng)初始是正定的這一條件不一定能保證，只有當(dāng)初始點(diǎn)合適時才能滿足。一般在極小點(diǎn)附近的點(diǎn)合適時才能滿足。一般在極小點(diǎn)附近的Hesse矩陣容易為正定的。矩

36、陣容易為正定的。所以所以基本基本Newton法在極小點(diǎn)附近才比較有效法在極小點(diǎn)附近才比較有效。2、 Newton法的搜索方向法的搜索方向H (x)1 f (x)不一定是下降方向。不一定是下降方向。因為若是下降方向，則應(yīng)有因為若是下降方向，則應(yīng)有 f (x)TH (x)1 f (x)0，但由于，但由于H (x)1不一定是正定的，所以上式不一定成立不一定是正定的，所以上式不一定成立3、Newton法的最大優(yōu)點(diǎn)是：當(dāng)初始點(diǎn)選得合適時收斂很快，具有二階收法的最大優(yōu)點(diǎn)是：當(dāng)初始點(diǎn)選得合適時收斂很快，具有二階收斂斂 速度，是目前算法中最快的一種。速度，是目前算法中最快的一種。 對初始點(diǎn)要求高，一般要求初始

37、點(diǎn)離極小點(diǎn)較近，否則不收斂。有時即使是對初始點(diǎn)要求高，一般要求初始點(diǎn)離極小點(diǎn)較近，否則不收斂。有時即使是收斂的，但因初始點(diǎn)離極大點(diǎn)或鞍點(diǎn)較近，會收斂于極大點(diǎn)或鞍點(diǎn)。收斂的，但因初始點(diǎn)離極大點(diǎn)或鞍點(diǎn)較近，會收斂于極大點(diǎn)或鞍點(diǎn)。4、方向、方向H (x)1 f (x)稱為稱為Newton方向，是一個好方向，對二次函數(shù)此方向方向，是一個好方向，對二次函數(shù)此方向 直指平穩(wěn)點(diǎn)。直指平穩(wěn)點(diǎn)。（二）修正（二）修正Newton法法? 怎樣才能使怎樣才能使Newton法成為一個下降算法法成為一個下降算法 ？修正修正Newton迭代公式：迭代公式： x(k+1) = x(k) tk H(x(k)1 f (x(k)

38、沿沿Newton方向一維方向一維搜索得到的最優(yōu)步搜索得到的最優(yōu)步長長 保證了保證了 f(x(k+1) f(x(k) ，且不必要求且不必要求H(x)為正定矩陣。為正定矩陣。? 出現(xiàn)出現(xiàn) (1) H(x(k) 1不存在；或不存在；或(2) tk =0 時怎么辦時怎么辦 ？改用最速下降法改用最速下降法 ，即，即 p(k) = f (x(k) 修正修正Newton法與基本法與基本Newton法的優(yōu)點(diǎn)是：法的優(yōu)點(diǎn)是： 收斂快，程序簡單。前者更實(shí)用可靠。收斂快，程序簡單。前者更實(shí)用可靠。缺點(diǎn)是要求計算缺點(diǎn)是要求計算Hesse矩陣及其逆矩陣，計算量大，尤其當(dāng)維數(shù)矩陣及其逆矩陣，計算量大，尤其當(dāng)維數(shù)n較大時。

39、較大時。5.2.3 Marquart法法最速下降法的優(yōu)點(diǎn)：對初始點(diǎn)要求不高，穩(wěn)定性好；遠(yuǎn)離最優(yōu)點(diǎn)時收斂較快。最速下降法的優(yōu)點(diǎn)：對初始點(diǎn)要求不高，穩(wěn)定性好；遠(yuǎn)離最優(yōu)點(diǎn)時收斂較快。 缺點(diǎn)是離最優(yōu)點(diǎn)較近時收斂很慢。缺點(diǎn)是離最優(yōu)點(diǎn)較近時收斂很慢。牛頓法的優(yōu)缺點(diǎn)剛好與最速下降法相反。牛頓法的優(yōu)缺點(diǎn)剛好與最速下降法相反。 1963年年Marquardt提出將最速下降法與提出將最速下降法與Newton法結(jié)合，開始用最速下降法，法結(jié)合，開始用最速下降法，在接近最優(yōu)點(diǎn)時用在接近最優(yōu)點(diǎn)時用Newton法。法。 在迭代公式在迭代公式x(k+1) = x(k) +tk p(k)中，取步長中，取步長tk1 ，搜索方向為

40、，搜索方向為p(k) 2f (x(k) + kI1 f (x(k)其中其中 k同時起控制搜索方向和步長的作用，同時起控制搜索方向和步長的作用，I為單位矩陣為單位矩陣 (1) 開始階段取很大，如開始階段取很大，如 0=104 ，p(0) 2f (x(0) + 0I1 f (x(0) f (x(0) 1 0(2) 在迭代過程中，讓在迭代過程中，讓 k0， p(k) 2f (x(k)1 f (x(k)（一）方法思想（一）方法思想最速下降法最速下降法 Newton法法 具體在每一步是否縮小具體在每一步是否縮小 k，要通過檢驗?zāi)繕?biāo)函數(shù)值來決定，要通過檢驗?zāi)繕?biāo)函數(shù)值來決定 ：若若f(x(k+1) f(x(

41、k)，取，取 k+1 1，重作第，重作第k步迭代。步迭代。 （二）算法（二）算法開始開始給定給定x(0) , M， , 令令 k=0， 0=104 x*=x(k)是是結(jié)結(jié)束束p(k) = 2f (x(k) + kI1 f (x(k)否否否否 kM是是計算計算 f( x(k ) ) | f( x(k ) ) | x(k+1) = x(k) +p(k)f(x(k+1) f(x(k) k+1= 0.5 k , k=k+1是是否否 k= 2 k（三）評注（三）評注 PP124I 可推廣為可推廣為半正定矩半正定矩陣陣若若 2f (x(k) + kI1不存在不存在x(k+1) = x(k) + tkp(k

42、)5.2.4 非線性最小二乘問題非線性最小二乘問題（一）最小二乘問題（一）最小二乘問題在工程實(shí)際問題中，經(jīng)常遇到一類特殊的求極小值問題，其目標(biāo)函數(shù)具有在工程實(shí)際問題中，經(jīng)常遇到一類特殊的求極小值問題，其目標(biāo)函數(shù)具有平方和形式：平方和形式：nm (x),fF(x)m1i2i例例5.2.3 求解方程組求解方程組fi(x)=0，（，（i=1,2, m)的問題可化為求解下列優(yōu)化問題的問題可化為求解下列優(yōu)化問題m1i2i(x)f F(x)min例例5.2.4 通過通過m組實(shí)驗數(shù)據(jù)來建立物理量組實(shí)驗數(shù)據(jù)來建立物理量y與另外與另外l個物理量個物理量t1, t2 , tl 之間的函數(shù)關(guān)系：之間的函數(shù)關(guān)系：y

43、= Y(t1, t2 , , tl ; x1, x2, , xn) “接近接近”的衡量標(biāo)準(zhǔn)常用平方和形的衡量標(biāo)準(zhǔn)常用平方和形式式 m1i2im1i2(i)221(i)l(i)2(i)1m1i2(i)(i)(x)fy)x,.,x,x;t,.,t ,Y(t)yy(F(x)即要確定其中即要確定其中n個待定參數(shù)個待定參數(shù)x1,x2,xn ，使得經(jīng)驗公式的計算值，使得經(jīng)驗公式的計算值 與實(shí)驗值與實(shí)驗值 盡可能地接近。盡可能地接近。(i)y(i)y求解求解min F(x) 為求解方便，引入向量函數(shù)為求解方便，引入向量函數(shù) f(x)=f1(x),f2(x),fm(x)T 最小二乘問題化為：最小二乘問題化為：

44、 min F(x) = min f(x)Tf(x) = min |f(x)|2（二）最小二乘問題的求解（二）最小二乘問題的求解可直接用前面介紹的單純形法、可直接用前面介紹的單純形法、Powell共軛方向法、最速下降法、共軛方向法、最速下降法、Newton法、法、Marquart法求解法求解 最小二乘法最小二乘法 （Gauss-Newton法）法）！ 如用如用Newton法求解，則要求法求解，則要求F(x)的的Hesse矩陣，是否可以不求矩陣，是否可以不求H(x) ！由于最小二乘問題目標(biāo)函數(shù)形式的特殊性，可用計算一階導(dǎo)數(shù)來代替二階導(dǎo)由于最小二乘問題目標(biāo)函數(shù)形式的特殊性，可用計算一階導(dǎo)數(shù)來代替二階

45、導(dǎo)數(shù)的計算數(shù)的計算 ： F(x(k)=2J(x(k)Tf(x(k) Newton方向：方向： p(k) = 2F(x(k)1 F(x(k)Jacobi 矩陣矩陣 J(x)=Jij(x)mn Jij(x) = jix(x)f 2F(x(k) 2J(x(k)TJ(x(k) 迭代公式：迭代公式：x(k+1) = x(k) J(x(k)TJ(x(k)1 J(x(k)Tf(x(k) x(k+1) = x(k) J(x(k)TJ(x(k)1 J(x(k)Tf(x(k) 修正修正Gauss-Newton迭代公式迭代公式tk? ! 如果在某次迭代中如果在某次迭代中J(x(k)TJ(x(k)變成奇異的，則變成奇

46、異的，則Gauss-Newton法失效法失效 !可直接取負(fù)梯度方向可直接取負(fù)梯度方向J(x(k)Tf(x(k) 為搜索方向為搜索方向修正修正Gauss-Newton法的算法法的算法: P1275.2.5 共軛梯度法共軛梯度法 由由Powell共軛方向法可知，共軛方向是好方向，是否有比共軛方向法可知，共軛方向是好方向，是否有比Powell共軛方向共軛方向 法更簡單的方法構(gòu)建共軛方向？法更簡單的方法構(gòu)建共軛方向？（一）（一）FletcherReeves共軛梯度法的基本思想共軛梯度法的基本思想任取初始點(diǎn)任取初始點(diǎn)x(0) ，然后沿著逐次迭代產(chǎn)生的共軛方向，然后沿著逐次迭代產(chǎn)生的共軛方向p(k)進(jìn)行一

47、維搜索：進(jìn)行一維搜索：x(k+1) = x(k) + tk p(k)得到下一個迭代點(diǎn)。得到下一個迭代點(diǎn)。當(dāng)當(dāng)f(x)為二次函數(shù)為二次函數(shù)時，至多經(jīng)過時，至多經(jīng)過n次次迭代就可得到極小迭代就可得到極小點(diǎn)點(diǎn)構(gòu)造共軛方向構(gòu)造共軛方向p(0),p(n-1)的方法：的方法： p(0) = f(x(0) p(k+1) = f(x(k1) + kp(k) 即下一個共軛方向是當(dāng)前點(diǎn)處負(fù)即下一個共軛方向是當(dāng)前點(diǎn)處負(fù)梯度方向與已求得的最后一個共梯度方向與已求得的最后一個共軛方向的線性組合。軛方向的線性組合。 p(0) = f(x(0) f(x(1)p(1) = f(x(1)+ 0p(0)x(0)x(1) ! 要使

48、得要使得p(0),p(n-1)相互共軛，相互共軛， 顯然顯然 k不能隨便取不能隨便取 ！2(k)21)(k(k)T(k)1)(kT1)(kk)f(x)f(x)f(x)f(x)f(x)f(x記記 g(k) = f(x(k)FR共軛梯度法的迭代公式：共軛梯度法的迭代公式：x(k+1) = x(k) + tk p(k)p(k+1) = g(k) + kp(k) k=|g(k)|2 |g(k+1)|2 p(0) = g(0) 以二次目標(biāo)函數(shù)為模型，經(jīng)推導(dǎo)得：以二次目標(biāo)函數(shù)為模型，經(jīng)推導(dǎo)得：（詳細(xì)看（詳細(xì)看P129下半頁的內(nèi)容，注意下半頁的內(nèi)容，注意式式5.2.19及及5.2.20的推導(dǎo)）的推導(dǎo)）幾點(diǎn)說

49、明：幾點(diǎn)說明：1、“ 重新開始重新開始”的策略的策略原因同原因同Powell共軛梯度法（誤差、共軛梯度的個數(shù)）共軛梯度法（誤差、共軛梯度的個數(shù)）2、何時執(zhí)行重新開始步驟？、何時執(zhí)行重新開始步驟？ 見見PP131（二）（二）FR法的算法法的算法開始開始給定給定x(0) , |g(k+1 )| 否否k=0， p(0)=g(0) x*=x(0)是是結(jié)束結(jié)束g(0) = f( x(0 ) )|g(0)| x(k+1) = x(k) + tk p(k), g(k+1) = f(x(k+1 )其中其中tk為最優(yōu)步長為最優(yōu)步長x(0)=x(k+1)g(0)=g(k+1)是是否否ak = |g(k+1)|2

50、/ |g(k )|2 p(k+1) = g(k) + kp(k) k=k+1x*=x(k+1)是是結(jié)束結(jié)束k = n 否否例例5.2.6 用用FR共軛梯度法解共軛梯度法解 min f (x)6010 x1 4x2 +x12 +x22 x1x2 初始點(diǎn)取為初始點(diǎn)取為x(0)=0, 0T 。解：解： f (x)102x1x2, 42x2x1 T p(0) g(0) f (x (0)10, 4T進(jìn)行一維搜索，對簡單進(jìn)行一維搜索，對簡單f(x)，可用解析法求解：，可用解析法求解：f (x(1)= f (x(0)t p(0)= f (x)|x=10t, 4tT = 60116t+76t2f (t)152

51、0t1160 t0 0.76315789x(1) = x(0) + t0 p(0) =7.63157894, 3.052631578Tg(1) f (x (1)2.21052631, 5.52631579Ta0= |g(1)|2 / |g(0 )|2 =35.42659277 / 116p(1) = g(1) + 0p(0) =0.84349308, 6.747922437T再用解析法求最優(yōu)步長再用解析法求最優(yōu)步長 t1 得得t1 0.436781609x(2) = x(1) + t1 p(1) =7.999999993, 5.999999997Tg(2) f (x (2)0, 0T所以，所以

52、，x* = 8, 6T f * = 8（三）（三）其它的共軛梯度法（自學(xué)）其它的共軛梯度法（自學(xué)）（四）（四）評注評注1、共軛梯度法的優(yōu)點(diǎn)是不必計算、共軛梯度法的優(yōu)點(diǎn)是不必計算Hesse矩陣及其逆矩陣，程序簡單，對大規(guī)模矩陣及其逆矩陣，程序簡單，對大規(guī)模 問題很有吸引力。對一般函數(shù)為超線性收斂。問題很有吸引力。對一般函數(shù)為超線性收斂。2、收斂速度依賴于一維搜索的精確性及、收斂速度依賴于一維搜索的精確性及Hesse矩陣的特征值的分布。矩陣的特征值的分布。5.2.6 擬擬Newton法（變尺度法）法（變尺度法）Newton法的最大優(yōu)點(diǎn)是靠近極小點(diǎn)時收斂速度快，主要缺點(diǎn)是要計算法的最大優(yōu)點(diǎn)是靠近極小

53、點(diǎn)時收斂速度快，主要缺點(diǎn)是要計算Hesse矩陣及其逆矩陣，計算量大矩陣及其逆矩陣，計算量大? 有沒有可能既保持有沒有可能既保持Newton法快速的優(yōu)點(diǎn)，又不計算法快速的優(yōu)點(diǎn)，又不計算Hesse矩陣及其逆矩陣矩陣及其逆矩陣 ?1959年年Davidon提出變尺度法，提出變尺度法，1963年經(jīng)年經(jīng)Fletcher和和Powell改進(jìn)，形成改進(jìn)，形成DFP法法1970年年Broyden等人提出更穩(wěn)定的等人提出更穩(wěn)定的BFGS變尺度法。變尺度法。（一）（一）擬擬Newton法與變尺度法法與變尺度法若一個算法的一維搜索方向為若一個算法的一維搜索方向為p(k) =H(k) f(x(k) H(k)g(k)

54、其中其中H(k)稱為尺度矩陣（稱為尺度矩陣（nn階），由于迭代過程中階），由于迭代過程中H(k)是變化的，該算法為變尺度法是變化的，該算法為變尺度法如果一個變尺度法的尺度矩陣滿足擬如果一個變尺度法的尺度矩陣滿足擬Newton條件條件 x(k+1)x(k) = H(k+1) f(x(k+1) f(x(k)則稱為擬則稱為擬Newton法法（二）（二）擬擬Newton法的基本思想法的基本思想Newton方向方向 p(k) = 2f(x(k)1 f(x(k)? 不想求不想求Hesse矩陣及其逆矩陣，有什么辦法矩陣及其逆矩陣，有什么辦法 ?從從形式形式上模仿，造一個方向上模仿，造一個方向： p(k) =

55、H(k) f(x(k)尺度矩陣尺度矩陣H(k) 既近似既近似 2f(x(k)1 ，計，計算又要方便！算又要方便！H(k)應(yīng)滿足的條件：應(yīng)滿足的條件： (1).滿足擬滿足擬Newton條件：條件：x(k+1)x(k) = H(k+1) f(x(k+1) f(x(k)(2).H(k)為正定矩陣，這樣為正定矩陣，這樣p(k)為下降方向為下降方向(3).由由H(k)出發(fā)計算出發(fā)計算H(k+1)應(yīng)簡便應(yīng)簡便:(4).應(yīng)使算法具有二次收斂性。應(yīng)使算法具有二次收斂性。校正矩陣校正矩陣H(k+1)H(k)E(k)（三）（三）DFP算法算法 p(0) = f(x(0) H(0) = I p(k) = H(k)

56、f(x(k) x(k+1) =x(k)+tkp(k)H(k+1)H(k) s(k) s(k)Ts(k)T y(k)H(k) y(k)Ty(k)T H(k) y(k)T H(k) y(k)其中其中 y(k) = g(k+1)g(k) s(k) = x(k+1)x(k)1、上述算法具有三個性質(zhì)：、上述算法具有三個性質(zhì)：(1) 校正公式的分母總大于零校正公式的分母總大于零, 校正公式總有物理意義；校正公式總有物理意義；(2) H(k)都是正定的，所以每次迭代方向都是下降方向；都是正定的，所以每次迭代方向都是下降方向；(3) 對二次函數(shù)對二次函數(shù) f(x) = c+bTx+0.5xTAx (A為正定矩

57、陣為正定矩陣)，迭代得到的搜索方向，迭代得到的搜索方向 p(0), p(1) , p(k1)相互相互 A共軛，所以共軛，所以DFP是一種共軛方向法；是一種共軛方向法； 且且 H(n) = A1 ，說明，說明H(k) 逐次逼近逐次逼近A1 2、DFP法的重新開始策略法的重新開始策略由于計算的舍入誤差及一維搜索精度不夠，會破壞由于計算的舍入誤差及一維搜索精度不夠，會破壞H(k)的正定性，導(dǎo)致算法失效。的正定性，導(dǎo)致算法失效。（1）一維搜索后，如果一維搜索后，如果 f(x(k+1) f(x(k)，意味著，意味著 p(k) 不是下降方向，不是下降方向， H(k)不是正不是正 定矩陣，則重新開始，重置定

58、矩陣，則重新開始，重置H(k) = I；（2）每迭代每迭代n+1次后重新開始，令次后重新開始，令x(0) = x(k+1) , H(0) = I3、DFP法的算法法的算法開始開始給定給定x(0) , |g(k+1 )| f0 =f( x(0 ) ) , g(0) = f( x(0 ) )x(k+1) = x(k) + tk p(k), 其中其中tk為最優(yōu)步長為最優(yōu)步長fk+1 =f(x(k+1 ), g(k+1) = f(x(k+1 )x(0)=x(k+1)f0 = fk+1g(0)=g(k+1)是是否否y(k) = g(k+1)g(k) s(k) = x(k+1)x(k)x*=x(k+1)是是結(jié)束結(jié)束k = n 否否fk+1 fk否否是是H(0)= I， p(0)=g(0) , k=0p(k+1) = H(k+1) g(k+1) k=k+1H(k+1)H(k) s(k)