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

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

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

3、共軛向量組，從任意點(diǎn)共軛向量組，從任意點(diǎn)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)的極小點(diǎn)。的極小點(diǎn)。 在在n維空間中與維空間中與n個(gè)線性無(wú)關(guān)的向量都正交的一定是零向個(gè)線性無(wú)關(guān)的向量都正交的一定是零向 量。量。 設(shè)設(shè)n元函數(shù)元函數(shù)f(x)=1/2xTAx+bTx+c, A=AT正定，又設(shè)正定，又設(shè)n維非零向量組維非零向量組p1, p2, pn是是A共軛向量組，從任意點(diǎn)共軛向量組，

4、從任意點(diǎn)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)的極小點(diǎn)。的極小點(diǎn)。 一個(gè)算法若能在有限步內(nèi)求得正定二次函數(shù)的極一個(gè)算法若能在有限步內(nèi)求得正定二次函數(shù)的極 小點(diǎn)，則稱(chēng)該算法具有二次收斂性小點(diǎn)，則稱(chēng)該算法具有二次收斂性(又稱(chēng)二次終止性又稱(chēng)二次終止性)。 由由性質(zhì)性質(zhì)4可知，若能找到一組可知，若能找到一組A共軛向量共軛向量p1, p2, pn 則前面提到的結(jié)合最速下降法和則前面提到的

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

6、先以正定二次函數(shù)為例，介紹一種生成共軛方向的方正定二次函數(shù)為例，介紹一種生成共軛方向的方法法，再將這種方法推廣到非二次函數(shù)上。，再將這種方法推廣到非二次函數(shù)上。 這種方法這種方法中每一個(gè)共軛向量都是依賴(lài)于迭代點(diǎn)處的負(fù)梯度中每一個(gè)共軛向量都是依賴(lài)于迭代點(diǎn)處的負(fù)梯度，因此稱(chēng)為因此稱(chēng)為共軛梯度法共軛梯度法，它，它是共軛方向法中的一種。是共軛方向法中的一種。令令1( ),2TTf xx Axb xcAA正定T (2) 若若 ，停止，停止，成的正交錐中找一個(gè)向量成的正交錐中找一個(gè)向量 ，即令，即令 使得使得 與與 共軛，即共軛，即由由21()0.TpAp(1) 從任取初始點(diǎn)從任取初始點(diǎn)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) 若若 ，停止，停止，成的正交錐中找一個(gè)向量成的正交錐中找一個(gè)向量 ，即令，即令 使得使得 與與 共軛，即共軛，即由由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) 以此類(lèi)推，以此類(lèi)推，45,.x x否則在否則在 和和 張張?k這樣便構(gòu)造了一組向量這樣便構(gòu)造了一組向量11(),1,2,.,1, kkkkpf xpkn12,.,np pp 實(shí)際上，這組向量實(shí)際上，這組向量 是一個(gè)是一個(gè)A共軛向量組。共軛向量組。12,.,np pp相鄰兩個(gè)向量是共軛的相鄰兩個(gè)向量是共軛的11(), pf x1()(),kTkkkTkf xAppAp設(shè)向量組設(shè)向量組 是由上述方法產(chǎn)生的向量是由上述方法產(chǎn)生的向量 組，向量組組，向量組 是由各點(diǎn)的梯度生成的是由各點(diǎn)的梯度生成的

9、 向量組，向量組， ( ) 則則 (1) 是正交向量組；是正交向量組； (2) 是是A共軛向量組。共軛向量組。12,.,np pp() kkgf x12,.,np pp12,.,ng gg12,.,ng gg設(shè)向量組設(shè)向量組 是由上述方法產(chǎn)生的向量組，向量組是由上述方法產(chǎn)生的向量組，向量組 是由各點(diǎn)的梯度生成的向量組，是由各點(diǎn)的梯度生成的向量組， ( ) 則則 (1) 是正交向量組；是正交向量組； (2) 是是A共軛向量組。共軛向量組。12,.,np pp( )kkgf x12,.,np pp12,.,ng gg12,.,ng gg 2=i n由由 的構(gòu)造過(guò)程知，的構(gòu)造過(guò)程知，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è)時(shí)，結(jié)論成立 下證時(shí)結(jié)論仍成立由假設(shè)可知，要證明由假設(shè)可知，要證明 時(shí)結(jié)論成立，只需證明時(shí)結(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 共軛向量組，從任意點(diǎn)共軛向量組，從任意點(diǎn)x1出發(fā)，相繼以出發(fā)，相繼以p1, p2, pn 為搜索方向進(jìn)行精確一維搜索，則為搜索方向進(jìn)行精確一維搜索，則 (1) f(xk+1)與與p1, p2, pk (k=1,2,n)正交；正交；因?yàn)橐驗(yàn)?11(),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)造過(guò)程知，的構(gòu)造過(guò)程知，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)生的向量組， 向量組向量組 是由各點(diǎn)的梯度生成的向量組，是由各點(diǎ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共軛向量組，從任意點(diǎn)共軛向量組，從任意點(diǎn)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)的極小點(diǎn)。的極小點(diǎn)。 11111(),(),1,2,.,1,(*)().()kkkkkTkkkTkpf xpf xpknf xAppAp 是一個(gè)是一個(gè)A共軛向量組共軛向量組12,.,np pp每一個(gè)搜索方向都依賴(lài)迭代點(diǎn)處的每一個(gè)搜索方向都依賴(lài)迭代點(diǎn)處的負(fù)梯度負(fù)梯度，對(duì)應(yīng)的算法稱(chēng)為，對(duì)應(yīng)的算

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

16、設(shè)設(shè) ，向量組，向量組 是由上述方法構(gòu)造的是由上述方法構(gòu)造的A共軛向量組，共軛向量組， ，利用前面，利用前面 所得的公式，得到幾個(gè)等價(jià)的計(jì)算公式：所得的公式，得到幾個(gè)等價(jià)的計(jì)算公式：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 對(duì)于正定二次函數(shù)，上面得到的對(duì)于正定二次函數(shù)，上面得到的5個(gè)計(jì)算公式是等價(jià)的；個(gè)計(jì)算公式是等價(jià)的； 這

19、這5種共軛梯度法也是完全等價(jià)的；種共軛梯度法也是完全等價(jià)的；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共軛梯度法共軛梯度法簡(jiǎn)潔，用的最多簡(jiǎn)潔，用的最多更好用更好用 對(duì)于非二次函數(shù)，產(chǎn)生的搜索方向不再相同，對(duì)于非二次函數(shù)，產(chǎn)生的搜索方向不再相同， 利用公式利用公式(2)-(5), (1)中含有中含有Hesse矩陣，通常不用矩陣，通常不用1x+122,kkkgg步驟步驟1. 選定初始點(diǎn)選定初始點(diǎn) 。步驟步驟2. 如果如果 ，算法停止，算法停止， ，否則轉(zhuǎn)步驟，否則轉(zhuǎn)步驟3。步驟步驟4. 精確一維搜索找最佳步長(zhǎng)精確一維搜索找最佳步長(zhǎng) ，令，令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. 計(jì)算計(jì)算 轉(zhuǎn)步驟轉(zhuǎn)步驟4。11=, =1.pg k1+11+1=,=,kkxxpg+11,1, kkkkpgpkk轉(zhuǎn)步驟轉(zhuǎn)步驟6。步驟步驟4. 精確一維搜索找最佳步長(zhǎng)精確一維搜索找最佳步長(zhǎng) ，令，令*+1kxxk1kkkkxxp步驟步驟5. 如果如果 ，算法停止，算法停止， ，否則轉(zhuǎn)步驟，否則轉(zhuǎn)步驟6。+1kg步驟步驟6. 如果如果k=n, 令令 算法停止算法停止,k=1 ，轉(zhuǎn)步驟，轉(zhuǎn)步驟4; 否則轉(zhuǎn)步驟否則轉(zhuǎn)步驟7。步驟步驟7. 計(jì)算計(jì)算 轉(zhuǎn)步驟轉(zhuǎn)

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

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

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 *. 共軛梯度法對(duì)正定二次函數(shù)，具有二次收斂性；共軛梯度法對(duì)正定二次函數(shù)，具有二次收斂性； 對(duì)非二次函數(shù)，由于目標(biāo)函數(shù)的對(duì)非二次函數(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ù)，且水平集 有界，則由共軛梯度法得到的點(diǎn)列有界，則由共軛梯度法得到的點(diǎn)列 有如下有如下性質(zhì)：性質(zhì)：(1) 為嚴(yán)格單調(diào)下降序列，且為嚴(yán)格單調(diào)下降序列，且 存在；存在；(2) 的任意聚點(diǎn)的任意聚點(diǎn) 都是都是 f (x)的最優(yōu)解。的最優(yōu)解。1( )()Lx f xf x kx( )kf x kx

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

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

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

29、1,初始尺度矩陣初始尺度矩陣H1,令令k=1. 計(jì)算計(jì)算 利用精確一維搜索找最佳步長(zhǎng)利用精確一維搜索找最佳步長(zhǎng) ， 令令 ，轉(zhuǎn)步驟，轉(zhuǎn)步驟2。+1=+1kkkHHHkk， 其中其中 稱(chēng)為修正矩陣。稱(chēng)為修正矩陣。 不同的修正矩陣，對(duì)應(yīng)著不同的變尺度法。不同的修正矩陣，對(duì)應(yīng)著不同的變尺度法。kHk+1=+.kkkkxxp. kkkpH gx1, H1對(duì)稱(chēng)對(duì)稱(chēng)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，為了使算法有為了使算法有較快的收斂速度，需要滿(mǎn)足以下幾個(gè)原則：較快的收斂速度，需要滿(mǎn)足以下幾個(gè)原則： 擬牛頓性質(zhì)，擬牛頓性質(zhì)， 二次收斂性，二次收斂性， 穩(wěn)定性。穩(wěn)定性。構(gòu)造構(gòu)造 Hk的原則的原則擬牛頓性質(zhì)擬牛頓性質(zhì)在在 點(diǎn)處對(duì)函數(shù)點(diǎn)處對(duì)函數(shù) 作二階作二階 Tayloy展開(kāi)：展開(kāi)：1kx 111212111( )()1()2TkkkTkkkkf xf xf xx xx xf xx xo x x( )f x 略去高階項(xiàng)略去高階項(xiàng) 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矩陣矩陣 對(duì)稱(chēng)正定，又有對(duì)稱(chēng)正定，又有121(2) kkkxf xg2+1kf x=(3)kkgA x1=(4)kkxAg( )=1/2+TTf xx Ax b x c A，對(duì)稱(chēng)正定稱(chēng)稱(chēng)(3)或或(4)為擬為擬Newton方程方程21(1)kkkgf xx121(2)kkkxf xg 構(gòu)造構(gòu)造 Hk的原則的原則-擬牛頓性質(zhì)擬牛頓性質(zhì)當(dāng)當(dāng) 時(shí)，時(shí)， 為了利用不包含二階導(dǎo)數(shù)的矩陣為了利用不包含二階導(dǎo)數(shù)的矩陣Hk取代取代 Hk+1滿(mǎn)足滿(mǎn)足構(gòu)造構(gòu)造 Hk的原則的原則-擬牛頓性質(zhì)擬牛頓性質(zhì)擬牛頓方程（或條件）擬牛頓方程（或條件） -12,kf x12kkHfx 1=(4)kkxAg, Hk+1 不唯一。不唯一。121(2) kkkxf xg當(dāng)