工程優(yōu)化第4章-3

1、 最優(yōu)性條件最優(yōu)性條件 最速下降法最速下降法 牛頓法及其阻尼牛頓法牛頓法及其阻尼牛頓法 共軛方向法共軛方向法 共軛梯度法共軛梯度法 變尺度法（變尺度法（DFP算法和算法和BFGS算法）算法）無約束最優(yōu)化問題：無約束最優(yōu)化問題：min ( ):(1)nf xf RR 設(shè)設(shè) 是對稱正定矩陣，是對稱正定矩陣， 如果如果 則稱向則稱向量量p 和和q是是A共軛共軛的的(或稱為或稱為A正交正交)。 如果對有限個向量如果對有限個向量 ，有，有12,.,mppp()0(,1,2,.,)i TjpApij jm若若 則則p與與q是正交的。是正交的。 =0,Tp Aq則稱這個向量組是則稱這個向量組是A-共軛共軛

2、(或或A正交正交)向量組，也稱它們是一組向量組，也稱它們是一組A共共軛方向。軛方向。= ,=0,TTA I p Aq p qn nA,np qR共軛是正交的推廣共軛是正交的推廣共軛向量組是正交向量組的推廣。共軛向量組是正交向量組的推廣。 若若Rn中的非零向量中的非零向量p1,p2, pm是是A共軛向量組，則這共軛向量組，則這m 個向量是線性無關(guān)的。個向量是線性無關(guān)的。 在在n維空間中互相共軛的非零向量的個數(shù)不超過維空間中互相共軛的非零向量的個數(shù)不超過n。 設(shè)設(shè)n元函數(shù)元函數(shù)f(x)=1/2xTAx+bTx+c, A=AT正定，又設(shè)正定，又設(shè)n維非零維非零 向量組向量組p1, p2, pn是是A

3、共軛向量組，從任意點共軛向量組，從任意點x1出發(fā)，依出發(fā)，依 次以次以p1, p2, pn 為搜索方向進(jìn)行精確一維搜索，則為搜索方向進(jìn)行精確一維搜索，則 (1) f(xk+1)與與p1, p2, pk (k=1,2,n)正交；正交； (2) 最多最多n次迭代必達(dá)到二次函數(shù)次迭代必達(dá)到二次函數(shù)f(x)的極小點。的極小點。 在在n維空間中與維空間中與n個線性無關(guān)的向量都正交的一定是零向個線性無關(guān)的向量都正交的一定是零向 量。量。 設(shè)設(shè)n元函數(shù)元函數(shù)f(x)=1/2xTAx+bTx+c, A=AT正定，又設(shè)正定，又設(shè)n維非零向量組維非零向量組p1, p2, pn是是A共軛向量組，從任意點共軛向量組，

4、從任意點x1出發(fā)，相繼以出發(fā)，相繼以p1, p2, pn 為搜索方向進(jìn)行精確一為搜索方向進(jìn)行精確一維搜索，則維搜索，則 (1) f(xk+1)與與p1, p2, pk (k=1,2,n)正交；正交； (2) 最多最多n次迭代必達(dá)到二次函數(shù)次迭代必達(dá)到二次函數(shù)f(x)的極小點。的極小點。 一個算法若能在有限步內(nèi)求得正定二次函數(shù)的極一個算法若能在有限步內(nèi)求得正定二次函數(shù)的極 小點，則稱該算法具有二次收斂性小點，則稱該算法具有二次收斂性(又稱二次終止性又稱二次終止性)。 由由性質(zhì)性質(zhì)4可知，若能找到一組可知，若能找到一組A共軛向量共軛向量p1, p2, pn 則前面提到的結(jié)合最速下降法和則前面提到的

5、結(jié)合最速下降法和Newton法優(yōu)點的算法就法優(yōu)點的算法就找到了，就是找到了，就是共軛方向法共軛方向法， 在下降迭代法中，若取下降方向是共軛方向，所得到在下降迭代法中，若取下降方向是共軛方向，所得到的方法我們稱為的方法我們稱為。怎么選取共軛方向？怎么選取共軛方向？這個算法具有二次收斂性。這個算法具有二次收斂性。 共軛方向的選取有很大任意性，而一組不同的共軛方向共軛方向的選取有很大任意性，而一組不同的共軛方向就對應(yīng)著不同的共軛方向法。就對應(yīng)著不同的共軛方向法。 作為一種迭代算法，我們自然希望共軛方向能在迭代過作為一種迭代算法，我們自然希望共軛方向能在迭代過程中逐次生成。程中逐次生成。 下面先以下面

6、先以正定二次函數(shù)為例，介紹一種生成共軛方向的方正定二次函數(shù)為例，介紹一種生成共軛方向的方法法，再將這種方法推廣到非二次函數(shù)上。，再將這種方法推廣到非二次函數(shù)上。 這種方法這種方法中每一個共軛向量都是依賴于迭代點處的負(fù)梯度中每一個共軛向量都是依賴于迭代點處的負(fù)梯度，因此稱為因此稱為共軛梯度法共軛梯度法，它，它是共軛方向法中的一種。是共軛方向法中的一種。令令1( ),2TTf xx Axb xcAA正定T (2) 若若 ，停止，停止，成的正交錐中找一個向量成的正交錐中找一個向量 ，即令，即令 使得使得 與與 共軛，即共軛，即由由21()0.TpAp(1) 從任取初始點從任取初始點x1 出發(fā)，沿出發(fā)

7、，沿負(fù)梯度方向負(fù)梯度方向進(jìn)行精確一維搜索進(jìn)行精確一維搜索:2111,xxp11()pf x 2()0f x2()f x1p2p2211()pf xp 1p2p212111()0(), TTpApf xpAp可得可得21111()()TTf xAppAp否則在否則在 和和 張張1? (5) 若若 ，停止，停止，成的正交錐中找一個向量成的正交錐中找一個向量 ，即令，即令 使得使得 與與 共軛，即共軛，即由由1()0.kTkpAp(3) 在在x2 處沿處沿 p2 方向進(jìn)行精確一維搜索，方向進(jìn)行精確一維搜索，3222,xxp1()0kf x1()kf xkp1kp11()kkkkpf xp kp1kp

8、11()0() kTkkkTkkpApf xpAp可得可得1()()kTkkkTkf xAppAp(4) 以此類推，以此類推，45,.x x否則在否則在 和和 張張?k這樣便構(gòu)造了一組向量這樣便構(gòu)造了一組向量11(),1,2,.,1, kkkkpf xpkn12,.,np pp 實際上，這組向量實際上，這組向量 是一個是一個A共軛向量組。共軛向量組。12,.,np pp相鄰兩個向量是共軛的相鄰兩個向量是共軛的11(), pf x1()(),kTkkkTkf xAppAp設(shè)向量組設(shè)向量組 是由上述方法產(chǎn)生的向量是由上述方法產(chǎn)生的向量 組，向量組組，向量組 是由各點的梯度生成的是由各點的梯度生成的

9、 向量組，向量組， ( ) 則則 (1) 是正交向量組；是正交向量組； (2) 是是A共軛向量組。共軛向量組。12,.,np pp() kkgf x12,.,np pp12,.,ng gg12,.,ng gg設(shè)向量組設(shè)向量組 是由上述方法產(chǎn)生的向量組，向量組是由上述方法產(chǎn)生的向量組，向量組 是由各點的梯度生成的向量組，是由各點的梯度生成的向量組， ( ) 則則 (1) 是正交向量組；是正交向量組； (2) 是是A共軛向量組。共軛向量組。12,.,np pp( )kkgf x12,.,np pp12,.,ng gg12,.,ng gg 2=i n由由 的構(gòu)造過程知，的構(gòu)造過程知，ip12,p p

10、是是A共軛的，即共軛的，即210= ,TpAp結(jié)論結(jié)論(2)成立；成立；利用精確一維搜索的性質(zhì)知，利用精確一維搜索的性質(zhì)知，120= ,Tgp而而11=,pg故故210= ,Tgg結(jié)論結(jié)論(1)成立。成立。 =(1)(2),= +1.iin kn k假設(shè)時，結(jié)論成立 下證時結(jié)論仍成立由假設(shè)可知，要證明由假設(shè)可知，要證明 時結(jié)論成立，只需證明時結(jié)論成立，只需證明1= +n k1+kg(a) 證明證明所以所以結(jié)論結(jié)論(a)成立，進(jìn)而結(jié)論成立，進(jìn)而結(jié)論(1)成立。成立。與與12,.,kg gg正交，正交，1+kp與與12,.,kp ppA共軛。共軛。1+kg與與12,.,kg gg正交正交;12,.

11、,kp pp是是A共軛向量組，共軛向量組，利用性質(zhì)利用性質(zhì)4(1)可知，可知， 設(shè)設(shè)n元函數(shù)元函數(shù)f(x)=1/2xTAx+bTx+c, A=AT正定，又設(shè)正定，又設(shè)n維非零向量組維非零向量組p1, p2, pn是是A 共軛向量組，從任意點共軛向量組，從任意點x1出發(fā)，相繼以出發(fā)，相繼以p1, p2, pn 為搜索方向進(jìn)行精確一維搜索，則為搜索方向進(jìn)行精確一維搜索，則 (1) f(xk+1)與與p1, p2, pk (k=1,2,n)正交；正交；因為因為111(),1,(),2,., ,iiiif xipf xpin10,1,2,., ,+=Tikgpik11111,1,2,., ,+=Tik

12、TkiTiikigpigggppik0= ,(b) 證明證明結(jié)論結(jié)論(b)成立，進(jìn)而結(jié)論成立，進(jìn)而結(jié)論(2)成立。成立。1+kp與與12,.,kp pp是是A共軛的共軛的;由由 的構(gòu)造過程知，的構(gòu)造過程知，1121+= , ,., -TkipApikip1+kp與與kp是是A共軛的共軛的;下證下證1+kp與與121 -,.,kp pp是是A共軛的共軛的;1+= TikgAp121=0= , ,., -TkipApik，11()+iiiiiiiiiiggAxbgA xpbgAp11+=TTkiikpApgAp11+=Tiikiggg 111+=/Tikiiggg0=112+=0= , ,.,Tk

13、iggik，1+=TkikkgpAp設(shè)向量組設(shè)向量組 是由上述方法產(chǎn)生的向量組，是由上述方法產(chǎn)生的向量組， 向量組向量組 是由各點的梯度生成的向量組，是由各點的梯度生成的向量組， ( ) 則則 (1) 是正交向量組；是正交向量組； (2) 是是A共軛向量組。共軛向量組。12,.,np pp() kkgf x12,.,np pp12,.,ng gg注：為保證方向的共軛性，初始方向取負(fù)梯度方向。注：為保證方向的共軛性，初始方向取負(fù)梯度方向。12,.,ng gg 設(shè)設(shè)n元函數(shù)元函數(shù)f(x)=1/2xTAx+bTx+c, A=AT正定，又設(shè)正定，又設(shè)n維非零維非零 向量組向量組p1, p2, pn是是

14、A共軛向量組，從任意點共軛向量組，從任意點x1出發(fā)，相出發(fā)，相 繼以繼以p1, p2, pn 為搜索方向進(jìn)行精確一維搜索，則為搜索方向進(jìn)行精確一維搜索，則 (1) f(xk+1)與與p1, p2, pk (k=1,2,n)正交；正交； (2) 最多最多n次迭代必達(dá)到正定二次函數(shù)次迭代必達(dá)到正定二次函數(shù)f(x)的極小點。的極小點。 11111(),(),1,2,.,1,(*)().()kkkkkTkkkTkpf xpf xpknf xAppAp 是一個是一個A共軛向量組共軛向量組12,.,np pp每一個搜索方向都依賴迭代點處的每一個搜索方向都依賴迭代點處的負(fù)梯度負(fù)梯度，對應(yīng)的算法稱為，對應(yīng)的算

15、法稱為共軛梯度共軛梯度法法。存在問題：計算量、存儲量都很大存在問題：計算量、存儲量都很大11111(),(),1,2,.,1,(*)().()kkkkkTkkkTkpf xpf xpknf xAppAp 針對針對 f(x)=1/2xTAx+bTx+c, A=AT正定，最多正定，最多n次迭代達(dá)到極次迭代達(dá)到極小點找到了一組共軛方向：小點找到了一組共軛方向：針對一般的函數(shù)，將這組方向進(jìn)行推廣：針對一般的函數(shù)，將這組方向進(jìn)行推廣：2 kAfx直接對直接對(*)式推廣：式推廣：在正定二次函數(shù)在正定二次函數(shù)的前提下，將的前提下，將 變形變形怎么解決呢？怎么解決呢？能否將能否將 中的中的A去掉？去掉？kk

16、設(shè)設(shè) ，向量組，向量組 是由上述方法構(gòu)造的是由上述方法構(gòu)造的A共軛向量組，共軛向量組， ，利用前面，利用前面 所得的公式，得到幾個等價的計算公式：所得的公式，得到幾個等價的計算公式：1( ),2TTf xx Ax b x c AA正定T12,.,np pp()kkgf x 1+1()()(,1967)()()(1)TkkTkkkTkkTkkgApf xApDanielpAppAp +1+1+1() ()(2)(,1972)() ()kkkkkTkkTgggSorensonWolfepgg +1+1()(3)(,1972)()kkkTkkTggDixonMyerspg 1+1()kkkkkkkk

17、kkggAxbgA xpbgAp 利用定理利用定理1，可知，可知 是正交向量組，因此是正交向量組，因此(2)中中 ; 并且并且 .+1+1+1() ()(2)(,1972)() ()kkkkkTkkTgggSorensonWolfepgg +1+1()(3)(,1972)()kkkTkkTggDixonMyerspg 12,.,ng gg10+=Tkkgg10+=Tkkgp+122(4)(Re,1964)kkkgFlecherevesg +1+1()(3)(,1972)()kkkTkkTggDixonMyerspg +1+1() ()(5)(,1969)()kkkkkTkTgggPolyakP

18、olakRibieregg -1-12-1-1)()kkkkkTkTkkkkkpgppggpgg在(3)中，由,得到( +122(4)(Re,1964)kkkgFlecherevesg +1+1+1() ()(2)(,1972)() ()kkkkkTkk TgggSorenson Wolfepgg 1+11() ()=()()()(2)kTkTkTTkkkkkkkkpggpggpggg中 +1+1() ()(5)(,1969)()kkkkkTkTgggPolyakPolakRibieregg 對于正定二次函數(shù)，上面得到的對于正定二次函數(shù)，上面得到的5個計算公式是等價的；個計算公式是等價的； 這

19、這5種共軛梯度法也是完全等價的；種共軛梯度法也是完全等價的；1+1()()(,1967)()()(1)TkkTkkkTkkTkkgApf xApDanielpAppAp +1+1+1() ()(2)(,1972)() ()kkkkkTkkTgggSorensonWolfepgg +1+1()(3)(,1972)()kkkTkkTggDixonMyerspg +1+1() ()(5)(,1969)()kkkkkTkTgggPolyakPolakRibieregg +122(4)(Re,1964)kkkgFlecherevesg SW共軛梯度法共軛梯度法DM共軛梯度法共軛梯度法FR共軛梯度法共軛梯

20、度法PPR共軛梯度法共軛梯度法介紹介紹FR共軛梯度法共軛梯度法Daniel共軛梯度法共軛梯度法簡潔，用的最多簡潔，用的最多更好用更好用 對于非二次函數(shù)，產(chǎn)生的搜索方向不再相同，對于非二次函數(shù)，產(chǎn)生的搜索方向不再相同， 利用公式利用公式(2)-(5), (1)中含有中含有Hesse矩陣，通常不用矩陣，通常不用1x+122,kkkgg步驟步驟1. 選定初始點選定初始點 。步驟步驟2. 如果如果 ，算法停止，算法停止， ，否則轉(zhuǎn)步驟，否則轉(zhuǎn)步驟3。步驟步驟4. 精確一維搜索找最佳步長精確一維搜索找最佳步長 ，令，令1g*1xx*+1,kxx步驟步驟3. 取取k1kkkkxxp步驟步驟5. 如果如果

21、，算法停止，算法停止， 否則否則+1kg步驟步驟6. 如果如果k=n, 令令 k=1 ，轉(zhuǎn)步驟，轉(zhuǎn)步驟4; 否則轉(zhuǎn)步驟否則轉(zhuǎn)步驟7。步驟步驟7. 計算計算 轉(zhuǎn)步驟轉(zhuǎn)步驟4。11=, =1.pg k1+11+1=,=,kkxxpg+11,1, kkkkpgpkk轉(zhuǎn)步驟轉(zhuǎn)步驟6。步驟步驟4. 精確一維搜索找最佳步長精確一維搜索找最佳步長 ，令，令*+1kxxk1kkkkxxp步驟步驟5. 如果如果 ，算法停止，算法停止， ，否則轉(zhuǎn)步驟，否則轉(zhuǎn)步驟6。+1kg步驟步驟6. 如果如果k=n, 令令 算法停止算法停止,k=1 ，轉(zhuǎn)步驟，轉(zhuǎn)步驟4; 否則轉(zhuǎn)步驟否則轉(zhuǎn)步驟7。步驟步驟7. 計算計算 轉(zhuǎn)步驟轉(zhuǎn)

22、步驟4。1+11+1=,=,kkxxpg 誤差可能會使誤差可能會使n步迭代得不到正定二次函數(shù)的極小點。步迭代得不到正定二次函數(shù)的極小點。 Rn中共軛方向最多有中共軛方向最多有n個，個，n步后構(gòu)造的搜索方向不再是共軛步后構(gòu)造的搜索方向不再是共軛的的， 會降低收斂速度，會降低收斂速度，步驟步驟6：重新開始技術(shù)：重新開始技術(shù)：xn+1作為新的作為新的x1+122,kkkgg+11,1, kkkkpgpkk2212112( )242fxxxx xx，已知初始點，已知初始點(1,1)T解：解： 1）第一次迭代：沿負(fù)梯度方向搜尋）第一次迭代：沿負(fù)梯度方向搜尋計算初始點處的梯度計算初始點處的梯度112112

23、12244()422x xxxgf xxx=, 迭代精度迭代精度 。 1142pg ,1114141212xp 0.001精確一維搜索求最佳步長，精確一維搜索求最佳步長，令令10.25211120.5xxp,221()2gf x ,11141 2xp 112()(14 12 ) 40203f xpf =,=, 08020= =, 得得不滿足精度，繼續(xù)迭代：不滿足精度，繼續(xù)迭代：2）第二次迭代：）第二次迭代：2221150.2520gg2121pgp 22xp220.5x,212g,142p,142g,21.5,22220.51.50.5 1.5,精確一維搜索求最佳步長，精確一維搜索求最佳步長，

24、 11()(220 5 1 5 )=, . + . f xpf22(22 )2(0.5 1.5 )2(22 )(0.5 1.5 )4(22 )=因因30g得到最優(yōu)解得到最優(yōu)解:3222xxp=+令令21 , 0= , 得得 22(2 2 )2(0.5 1.5 )2(2 2 )(0.5 1.5 )4(2 2 )= 330()0gf x ,22220.5 1.5xp=42, 342xx *. 共軛梯度法對正定二次函數(shù)，具有二次收斂性；共軛梯度法對正定二次函數(shù)，具有二次收斂性； 對非二次函數(shù)，由于目標(biāo)函數(shù)的對非二次函數(shù)，由于目標(biāo)函數(shù)的Hesse矩陣不再是常數(shù)矩矩陣不再是常數(shù)矩陣，因而產(chǎn)生的方向不再是

25、共軛方向；陣，因而產(chǎn)生的方向不再是共軛方向； 共軛梯度法在一定條件下也是收斂的，且收斂速度通常優(yōu)共軛梯度法在一定條件下也是收斂的，且收斂速度通常優(yōu)于最速下降法，具有較高的求解效率。于最速下降法，具有較高的求解效率。 設(shè)設(shè) f (x)存在連續(xù)一階偏導(dǎo)數(shù)，且函數(shù)為凸函數(shù)，且水平集存在連續(xù)一階偏導(dǎo)數(shù)，且函數(shù)為凸函數(shù)，且水平集 有界，則由共軛梯度法得到的點列有界，則由共軛梯度法得到的點列 有如下有如下性質(zhì)：性質(zhì)：(1) 為嚴(yán)格單調(diào)下降序列，且為嚴(yán)格單調(diào)下降序列，且 存在；存在；(2) 的任意聚點的任意聚點 都是都是 f (x)的最優(yōu)解。的最優(yōu)解。1( )()Lx f xf x kx( )kf x kx

26、*xlim()kkf x 共軛梯度法在無約束優(yōu)化方法中占有重要的地位，是目共軛梯度法在無約束優(yōu)化方法中占有重要的地位，是目前最常用的方法之一。前最常用的方法之一。 (1) 對凸函數(shù)全局收斂（下降算法）；對凸函數(shù)全局收斂（下降算法）； (2) 計算公式簡單，不用求計算公式簡單，不用求Hesse矩陣或者逆矩陣，計算量矩陣或者逆矩陣，計算量 小，存儲量小，每步迭代只需存儲若干向量，小，存儲量小，每步迭代只需存儲若干向量，適用于大適用于大 規(guī)模問題規(guī)模問題； (3) 具有二次收斂性；具有二次收斂性； (對于正定二次函數(shù)，至多對于正定二次函數(shù)，至多n次迭代可達(dá)最優(yōu)解）次迭代可達(dá)最優(yōu)解） (4) Crow

27、der和和Wolfe證明，證明，共軛梯度法的收斂速率不壞共軛梯度法的收斂速率不壞 于最速下降法于最速下降法。 如果初始方向不用負(fù)梯度方向，則其收斂速率是線如果初始方向不用負(fù)梯度方向，則其收斂速率是線 性收斂的；性收斂的； (5) 共軛梯度法是目前共軛梯度法是目前求解無約束優(yōu)化問題最常用的方求解無約束優(yōu)化問題最常用的方 法之一法之一。注：不同的注：不同的k公式，對于正定二次函數(shù)是等價的，公式，對于正定二次函數(shù)是等價的， 對非正定二次函數(shù)，有不同的效果，對非正定二次函數(shù)，有不同的效果，經(jīng)驗上經(jīng)驗上PPR 效果效果 較好較好。 Newton法和阻尼法和阻尼Newton法具有收斂速度快的優(yōu)點，但法具有

28、收斂速度快的優(yōu)點，但需要計算需要計算Hesse矩陣的逆，矩陣的逆，計算量大，存儲量也很大。計算量大，存儲量也很大。12= kkkpf xf x 為減少計算量，用一個為減少計算量，用一個n階階對稱正定矩陣對稱正定矩陣Hk近似代替近似代替Hesse矩陣的逆矩陣的逆 ，即，即 ，從而搜索方，從而搜索方向是向是 ，由此搜索方向產(chǎn)生的方法稱為變尺度法，由此搜索方向產(chǎn)生的方法稱為變尺度法， Hk稱為尺度矩陣，這是一種稱為尺度矩陣，這是一種擬擬Newton法法，被認(rèn)為是無約束優(yōu)，被認(rèn)為是無約束優(yōu)化問題中最有效的方法之一化問題中最有效的方法之一。12kfx12kkHfx kkkpH g 任取初始點任取初始點x

29、1,初始尺度矩陣初始尺度矩陣H1,令令k=1. 計算計算 利用精確一維搜索找最佳步長利用精確一維搜索找最佳步長 ， 令令 ，轉(zhuǎn)步驟，轉(zhuǎn)步驟2。+1=+1kkkHHHkk， 其中其中 稱為修正矩陣。稱為修正矩陣。 不同的修正矩陣，對應(yīng)著不同的變尺度法。不同的修正矩陣，對應(yīng)著不同的變尺度法。kHk+1=+.kkkkxxp. kkkpH gx1, H1對稱對稱0, k=1dk=- Hkf(xk)一維搜索得一維搜索得k xk+1=xk+ k dk|xk+1-xk| ?修正修正Hk產(chǎn)生產(chǎn)生Hk+1Stop. xk+1-解解k=k+1yN構(gòu)造構(gòu)造 Hk的原則的原則變尺度法的關(guān)鍵在于如何構(gòu)造變尺度法的關(guān)鍵在

30、于如何構(gòu)造Hk，為了使算法有為了使算法有較快的收斂速度，需要滿足以下幾個原則：較快的收斂速度，需要滿足以下幾個原則： 擬牛頓性質(zhì)，擬牛頓性質(zhì)， 二次收斂性，二次收斂性， 穩(wěn)定性。穩(wěn)定性。構(gòu)造構(gòu)造 Hk的原則的原則擬牛頓性質(zhì)擬牛頓性質(zhì)在在 點處對函數(shù)點處對函數(shù) 作二階作二階 Tayloy展開：展開：1kx 111212111( )()1()2TkkkTkkkkf xf xf xx xx xf xx xo x x( )f x 略去高階項略去高階項 11112111( )()2TTkkkkkkf xf xf xx xx xf xx x在在xk+1 附近，函數(shù)兩端求導(dǎo)，得附近，函數(shù)兩端求導(dǎo)，得1211

31、( )kkkf xf xf xx x211+1kkkkkggf xxx令令 可得可得記記21(1)kkkgf xx = ,=,kkkx x gf x1+1=,=,kkkkkkg ggx xx 11112111( )()2TTkkkkkkf xf xf xx xx xf xx x211+1+kkkkkggf xxx21(1)kkkgf xxHesse矩陣矩陣 對稱正定，又有對稱正定，又有121(2) kkkxf xg2+1kf x=(3)kkgA x1=(4)kkxAg( )=1/2+TTf xx Ax b x c A，對稱正定稱稱(3)或或(4)為擬為擬Newton方程方程21(1)kkkgf xx121(2)kkkxf xg 構(gòu)造構(gòu)造 Hk的原則的原則-擬牛頓性質(zhì)擬牛頓性質(zhì)當(dāng)當(dāng) 時，時， 為了利用不包含二階導(dǎo)數(shù)的矩陣為了利用不包含二階導(dǎo)數(shù)的矩陣Hk取代取代 Hk+1滿足滿足構(gòu)造構(gòu)造 Hk的原則的原則-擬牛頓性質(zhì)擬牛頓性質(zhì)擬牛頓方程（或條件）擬牛頓方程（或條件） -12,kf x12kkHfx 1=(4)kkxAg, Hk+1 不唯一。不唯一。121(2) kkkxf xg當(dāng)