最優(yōu)化計(jì)算方法(工程優(yōu)化)第4章

1、 最優(yōu)性條件最優(yōu)性條件 最速下降法最速下降法 牛頓法及其阻尼牛頓法牛頓法及其阻尼牛頓法 共軛方向法共軛方向法 共軛梯度法共軛梯度法 變尺度法（變尺度法（DFP算法和算法和BFGS算法）算法） 目的是找目的是找 中的一點(diǎn)中的一點(diǎn) ，使對(duì)，使對(duì) ，均有，均有 ，稱，稱 為為(1)的全局極小點(diǎn)。的全局極小點(diǎn)。 min( ):(1)nf xfRR無約束最優(yōu)化問題：無約束最優(yōu)化問題：*()( )f xf xnR*xnxR 求解求解 (1)的計(jì)算方法稱為的計(jì)算方法稱為無約束最優(yōu)化方法無約束最優(yōu)化方法。*x( ),min( )min( ),( ),.nx Dx Rf xxDf xF xF xothers其中

2、 無約束最優(yōu)化方法應(yīng)用廣泛，理論也比較成熟；無約束最優(yōu)化方法應(yīng)用廣泛，理論也比較成熟； 可將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題來處理；可將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題來處理；解析法無約束優(yōu)化方法直接法：利用函數(shù)的一階或二階導(dǎo)數(shù)的方法：利用函數(shù)的一階或二階導(dǎo)數(shù)的方法收斂速度快，需要計(jì)算梯度或者收斂速度快，需要計(jì)算梯度或者Hesse矩陣矩陣：僅利用函數(shù)值的信息，尋找最優(yōu)解：僅利用函數(shù)值的信息，尋找最優(yōu)解不涉及導(dǎo)數(shù)，適用性強(qiáng)，但收斂速度慢不涉及導(dǎo)數(shù)，適用性強(qiáng)，但收斂速度慢可求得目標(biāo)函數(shù)的梯度時(shí)使用解析法可求得目標(biāo)函數(shù)的梯度時(shí)使用解析法在不可能求得目標(biāo)函數(shù)的梯度或偏導(dǎo)數(shù)時(shí)使用直接法在不可能求得目標(biāo)函

3、數(shù)的梯度或偏導(dǎo)數(shù)時(shí)使用直接法本章介紹解析法本章介紹解析法 所謂所謂最優(yōu)性條件最優(yōu)性條件，是指最優(yōu)化問題的最優(yōu)解所要滿足的，是指最優(yōu)化問題的最優(yōu)解所要滿足的必要條件或充分條件必要條件或充分條件。 這些條件對(duì)于最優(yōu)化算法的建立和最優(yōu)化理論的推導(dǎo)都是這些條件對(duì)于最優(yōu)化算法的建立和最優(yōu)化理論的推導(dǎo)都是至關(guān)重要的。至關(guān)重要的。 解析法要用到目標(biāo)函數(shù)的梯度或者解析法要用到目標(biāo)函數(shù)的梯度或者Hesse矩陣，容易想到矩陣，容易想到利用一階必要條件將無約束優(yōu)化問題轉(zhuǎn)化成一個(gè)梯度為利用一階必要條件將無約束優(yōu)化問題轉(zhuǎn)化成一個(gè)梯度為0 0確定確定的方程組。的方程組。 這里用到的一階必要條件就是最優(yōu)性條件。這里用到的一

4、階必要條件就是最優(yōu)性條件。 設(shè)設(shè) ，若，若 為為 的局部極小點(diǎn)，且在的局部極小點(diǎn)，且在 內(nèi)連續(xù)可微，則內(nèi)連續(xù)可微，則 *( )0.f x:nf RRx( )f x( *)N x*x xf 若若 為為 的局部極小點(diǎn)，且在的局部極小點(diǎn)，且在 內(nèi)內(nèi) 二次連續(xù)二次連續(xù)可微，則可微，則 半正定。半正定。 *xN xf*2*( )0,( )f xf x 設(shè)設(shè) ，若在，若在 內(nèi)內(nèi) 二次連續(xù)可微，且二次連續(xù)可微，且 正定，則正定，則 為為 的嚴(yán)格局部極小的嚴(yán)格局部極小 點(diǎn)。點(diǎn)。 如果如果 負(fù)定，則負(fù)定，則 為為 的嚴(yán)格局部極大點(diǎn)。的嚴(yán)格局部極大點(diǎn)。*( )0,f x:nf RRx( )f x( *)N x 2

5、f x( )f x 2f xx( )f x 設(shè)設(shè) 是凸函數(shù)且在是凸函數(shù)且在 處連續(xù)可微，則處連續(xù)可微，則 為為 的全局極小點(diǎn)的充要條件是的全局極小點(diǎn)的充要條件是 設(shè)設(shè) 是嚴(yán)格凸函數(shù)且在是嚴(yán)格凸函數(shù)且在 處連續(xù)可微，若處連續(xù)可微，若 則則 為為 的唯一全局極小點(diǎn)。的唯一全局極小點(diǎn)。*( )0,f x:nf RRx( )f xxx( )f x*( )0.f x:nf RRx利用最優(yōu)性條件求解下列問題：利用最優(yōu)性條件求解下列問題：令令即即：得到駐點(diǎn)：得到駐點(diǎn)：利用二階條件利用二階條件判斷駐點(diǎn)是否判斷駐點(diǎn)是否是極小點(diǎn)是極小點(diǎn) 332122111min33f xxxxx22122121,2 ,ffxxx

6、xx 0,f x212221 020 xxx 12341111,.0202xxxx 利用一階條件利用一階條件求駐點(diǎn)求駐點(diǎn)函數(shù)函數(shù)的的Hesse陣：陣：在點(diǎn)在點(diǎn)處的處的Hesse陣依次為：陣依次為：利用二階條件利用二階條件判斷駐點(diǎn)是否判斷駐點(diǎn)是否是極小點(diǎn)是極小點(diǎn) f x234111,.202xxx 12220022xf xx1234, ,x x x x 2120,02f x 2234202 0,.0202f xf x 222 0,0 2f x11,0 x 的行列式小于的行列式小于0 0； 2120,02f x 232002f x 222 00 2f x 242 002f x是正定矩陣；是正定矩陣

7、；是負(fù)定矩陣；是負(fù)定矩陣；是鞍點(diǎn)；是鞍點(diǎn)；14,x x是極小點(diǎn)；是極小點(diǎn)；2x是極大點(diǎn)。是極大點(diǎn)。3x： 迭代點(diǎn)沿某方向產(chǎn)生根據(jù)迭代點(diǎn)是否沿某個(gè)方向產(chǎn)生信賴域方法： 迭代點(diǎn)在某區(qū)域內(nèi)搜索產(chǎn)線搜索方法生 對(duì)某些較簡單的函數(shù)，這樣做有時(shí)是可行的；對(duì)某些較簡單的函數(shù)，這樣做有時(shí)是可行的； 但對(duì)一般但對(duì)一般n元函數(shù)元函數(shù) f(x) 來說，由條件來說，由條件 得到的是一個(gè)得到的是一個(gè)非線性方程組，解它相當(dāng)困難。非線性方程組，解它相當(dāng)困難。 為此，常直接使用迭代法。為此，常直接使用迭代法。( )0f x:1kk(1) 選定某一初始點(diǎn)選定某一初始點(diǎn)，并令，并令(2) 確定搜索方向確定搜索方向(3) 從從出發(fā)

8、，沿方向出發(fā)，沿方向求步長求步長，以產(chǎn)生下一個(gè)迭代點(diǎn)，以產(chǎn)生下一個(gè)迭代點(diǎn)(4) 檢查得到的新點(diǎn)檢查得到的新點(diǎn)是否為極小點(diǎn)或近似極小點(diǎn)。是否為極小點(diǎn)或近似極小點(diǎn)。，轉(zhuǎn)，轉(zhuǎn)(2)繼續(xù)進(jìn)行迭代。繼續(xù)進(jìn)行迭代。 在以上步驟中，選取步長在以上步驟中，選取步長可選用精確一維搜索或者非精確一可選用精確一維搜索或者非精確一維搜索，維搜索， 下降方向的選取正是下面我們要介紹的，下降方向的選取正是下面我們要介紹的，下降方向選取的不下降方向選取的不同，得到不同的算法。同，得到不同的算法。若是，則停止迭代。若是，則停止迭代。否則，令否則，令1x:1.k .kdkxkdk+1.kx+1kx從而得到第從而得到第 k+1次

9、迭代點(diǎn)，即次迭代點(diǎn)，即步長步長 由精確一維搜索得到。由精確一維搜索得到。k負(fù)梯度方向負(fù)梯度方向 這是函數(shù)值減少這是函數(shù)值減少最快的方向最快的方向 假設(shè)假設(shè) f 連續(xù)可微，連續(xù)可微，()kkdf x 0()min()kkkkkf xdf xd1+()kkkkkkkxxdxf x負(fù)梯度方向負(fù)梯度方向 是函數(shù)值減少最快的方向是函數(shù)值減少最快的方向 ？令令 是單位長度的向量，是單位長度的向量， P是什么方向時(shí)，函數(shù)值是什么方向時(shí)，函數(shù)值 下降最快？也就是下降最快？也就是p是什么方向時(shí)，是什么方向時(shí)， 取得最小值？取得最小值？ 當(dāng)當(dāng) 時(shí)，時(shí)， 最小，最小值為最小，最小值為 ，此時(shí)由，此時(shí)由 可得可得 (

10、)kkdf x p1,0,p()( )+( )( )Tf xpf xf xpo()f xp( )Tf xp( )( )cos( ),)Tf xpf xpf xp cos( ),)1f xp ( )Tf xp( )f x ( )( )Tf xpf x ( )( )f xpf x 最速下降法是求最速下降法是求多元函數(shù)極值多元函數(shù)極值的的最古老最古老的數(shù)值算的數(shù)值算法，早在法，早在1847年法國數(shù)學(xué)家年法國數(shù)學(xué)家Cauchy提出該算法，后來提出該算法，后來Curry作了進(jìn)一步的研究。作了進(jìn)一步的研究。 該方法直觀，簡單，計(jì)算方便，而且后來的一些新的該方法直觀，簡單，計(jì)算方便，而且后來的一些新的有效的

11、方法大多數(shù)是對(duì)它的改進(jìn)，或受它的啟發(fā)而得到有效的方法大多數(shù)是對(duì)它的改進(jìn)，或受它的啟發(fā)而得到的。的。1x:1k (), *kkf xxx()kkdf x (1) 選定某一初始點(diǎn)選定某一初始點(diǎn)， 并令并令(2) 若若 ，否則轉(zhuǎn)（，否則轉(zhuǎn)（3）；）； 由精確一維搜索確定步長步長由精確一維搜索確定步長步長 ，即由一個(gè)極小化，即由一個(gè)極小化問題求得最佳步長問題求得最佳步長0(3)kmin()kkf xd1,1,kkkkxxdkk令令 轉(zhuǎn)（轉(zhuǎn)（2）。）。算法框圖算法框圖x1, 0, k=1| f(xk ) |0得得 xk+1=x(k)+kdkk=k+12212121min( )224 ,f xxxx xx

12、111+4+=12xd，11( )=+=1+4 ,12fxdf 0=( )8020, 利用最速下降法求解利用最速下降法求解令令22= 1+42 122 1+4124 1+4解解：函數(shù)的梯度為：函數(shù)的梯度為1212224( ),2+4xxf xxx第第1次迭代：次迭代：取取11,1.Tx 14,2f x 114=,2df x2=402031=1/4,得得222+=1/2+2xd，22( )=+=2+ ,1/2+2fxdf 0=( )105, 令令22= 2+2 1/2+22 2+1/2+24 2+,221=,2df x 2=5511/21=1/4,得得14=,2d2111142=+=+1/4=1

13、21/2xxd ，第第2次迭代：次迭代：21,2f x2=1/2,3222215/2=+=+1/2=1/223/2xxd ，32,1f x1212224( ),2+4xxf xxx335/2+2+=3/2xd，33( )=+=5/2+2 ,3/2fxdf 0=( )205, 令令22= 5/2+22 3/22 5/2+23/24 5/2+2332=,1df x2=10527/4得得第第3次迭代：次迭代：3=1/4,43335/223=+=+1/4=3/215/4xxd，41/2,1f x35/2=3/2x，32,1f x繼續(xù)迭代可得到函數(shù)的近似最優(yōu)解。繼續(xù)迭代可得到函數(shù)的近似最優(yōu)解。 設(shè)目標(biāo)函

14、數(shù)設(shè)目標(biāo)函數(shù) f (x)連續(xù)可微，且水平集連續(xù)可微，且水平集 有界，則最速下降法或者在有限迭代步后終止；或者得有界，則最速下降法或者在有限迭代步后終止；或者得 到點(diǎn)列到點(diǎn)列 ，它的任何聚點(diǎn)都是，它的任何聚點(diǎn)都是f (x)的駐點(diǎn)。的駐點(diǎn)。 在收斂定理的假設(shè)下，若在收斂定理的假設(shè)下，若f (x)為凸函數(shù)，則最速下降法為凸函數(shù)，則最速下降法 或在有限迭代步后達(dá)到最小點(diǎn)；或得到點(diǎn)列或在有限迭代步后達(dá)到最小點(diǎn)；或得到點(diǎn)列 ，它，它 的任何聚點(diǎn)都是的任何聚點(diǎn)都是 f (x)的全局最小點(diǎn)。的全局最小點(diǎn)。1( )()Lx f xf xkxkx 最速下降法在兩個(gè)相鄰點(diǎn)之間的搜索方向是正交的。最速下降法在兩個(gè)相鄰

15、點(diǎn)之間的搜索方向是正交的。 最速下降法向極小點(diǎn)逼近是曲折前進(jìn)的，這種現(xiàn)象稱為最速下降法向極小點(diǎn)逼近是曲折前進(jìn)的，這種現(xiàn)象稱為鋸齒鋸齒現(xiàn)象現(xiàn)象。 除特殊的目標(biāo)函數(shù)和極特殊的初始點(diǎn)外，這種現(xiàn)象都會(huì)發(fā)生。除特殊的目標(biāo)函數(shù)和極特殊的初始點(diǎn)外，這種現(xiàn)象都會(huì)發(fā)生。令令利用精確一維搜索，可得利用精確一維搜索，可得由此得出由此得出1. 相鄰兩次迭代的方向互相垂直相鄰兩次迭代的方向互相垂直( )(),kkf xd ()()0kkTkkkf xdd 0=()kkTkkf xdd()kkf xd+1=()kTkdd+1=()kTkf xd0 x1x2x0d1d2d注：注：在最速下降法中，利用精確一維在最速下降法中，

16、利用精確一維搜索求最搜索求最佳步長，使得相鄰兩次迭代佳步長，使得相鄰兩次迭代的搜索方向總是垂直的，的搜索方向總是垂直的，使得逼近極小點(diǎn)過程是使得逼近極小點(diǎn)過程是“之之”字形，字形， 這樣從任何一個(gè)初始點(diǎn)開始，都可以很快到達(dá)極小點(diǎn)附這樣從任何一個(gè)初始點(diǎn)開始，都可以很快到達(dá)極小點(diǎn)附近，但是近，但是越靠近極小點(diǎn)步長越小，移動(dòng)越慢，越靠近極小點(diǎn)步長越小，移動(dòng)越慢，導(dǎo)致最速下降導(dǎo)致最速下降法的收斂速度很慢。法的收斂速度很慢。 實(shí)際運(yùn)用中，在可行的計(jì)算時(shí)間內(nèi)得不到需要的結(jié)果。實(shí)際運(yùn)用中，在可行的計(jì)算時(shí)間內(nèi)得不到需要的結(jié)果。對(duì)正定二次函數(shù)，用最速下降法產(chǎn)生的點(diǎn)列：偶數(shù)項(xiàng)點(diǎn)對(duì)正定二次函數(shù)，用最速下降法產(chǎn)生的點(diǎn)

17、列：偶數(shù)項(xiàng)點(diǎn) 列均在一條直線上，奇數(shù)項(xiàng)點(diǎn)列也均在一條直線上，且列均在一條直線上，奇數(shù)項(xiàng)點(diǎn)列也均在一條直線上，且 都過最優(yōu)點(diǎn)都過最優(yōu)點(diǎn). 對(duì)正定二次函數(shù)對(duì)正定二次函數(shù) ，用最速下降法產(chǎn)生的點(diǎn)，用最速下降法產(chǎn)生的點(diǎn)列：偶數(shù)項(xiàng)點(diǎn)列均在一條直線上，奇數(shù)項(xiàng)點(diǎn)列也均在一條直線列：偶數(shù)項(xiàng)點(diǎn)列均在一條直線上，奇數(shù)項(xiàng)點(diǎn)列也均在一條直線上，且都過最優(yōu)點(diǎn)上，且都過最優(yōu)點(diǎn). 則：則： 12Tf xx Ax分析分析：因?yàn)橄噜彿较蛘?，：因?yàn)橄噜彿较蛘唬?242/ / /./ /kddd22kAxtAx() kkkdf xAx因?yàn)?2,ktdtd22.kxtxt與與k有關(guān)有關(guān) 2212min( )25f xxx12,2

18、Tx 14,100,Tf x0( )8(24 )5000(2 100 ), 為了清除為了清除最佳步長最速下降法中最佳步長最速下降法中兩個(gè)搜索方向正交兩個(gè)搜索方向正交的不良后的不良后果，提出了許多改進(jìn)的方法，如：果，提出了許多改進(jìn)的方法，如：(1) 選擇不同初始點(diǎn)選擇不同初始點(diǎn)令令取初始點(diǎn)取初始點(diǎn)22( )= (24 ,2100 )= 2425 2100f 11=4, 100Tdfx 第第1次迭代次迭代11+= 24 ,2100Txd16260.0200307231252得得21121+1.919877, 0.3071785 10Txxd然后再從然后再從 開始新的迭代，經(jīng)過開始新的迭代，經(jīng)過10

19、次迭代，得最優(yōu)解次迭代，得最優(yōu)解 計(jì)算中可以發(fā)現(xiàn)，開始幾次迭代，步長比較大，函數(shù)值下計(jì)算中可以發(fā)現(xiàn)，開始幾次迭代，步長比較大，函數(shù)值下降將較快，但當(dāng)接近最優(yōu)點(diǎn)時(shí)，步長很小，目標(biāo)函數(shù)值下降很降將較快，但當(dāng)接近最優(yōu)點(diǎn)時(shí)，步長很小，目標(biāo)函數(shù)值下降很慢。慢。2x*(0,0)Tx 221.919877, 0.3071785 10Tx如果不取初點(diǎn)為如果不取初點(diǎn)為 而取而取 1(2,2)Tx 1(100,0)Tx *(0,0)Tx 111122,50200,0,Tfxxx一步就得到了極小點(diǎn)。一步就得到了極小點(diǎn)。 可見：可見：造成鋸齒現(xiàn)象與初始點(diǎn)的選擇有關(guān)造成鋸齒現(xiàn)象與初始點(diǎn)的選擇有關(guān)，但怎樣選一，但怎樣選一

20、個(gè)初始點(diǎn)也是一件困難的事。個(gè)初始點(diǎn)也是一件困難的事。11,21(100,0) ,Tx 11=200,0,Tdfx 220= 10020025 00400 100200dd 22(100200 ,00 )= 10020025 00,f 2111+100,0+1/2200,0= 0,0TTTxxd第第1次迭代次迭代 雖然后一初始點(diǎn)較前一初始點(diǎn)離最優(yōu)點(diǎn)雖然后一初始點(diǎn)較前一初始點(diǎn)離最優(yōu)點(diǎn) 遠(yuǎn)，遠(yuǎn)，但迭代中不含上面出現(xiàn)的鋸齒現(xiàn)象。但迭代中不含上面出現(xiàn)的鋸齒現(xiàn)象。 采用非精確一維搜索求步長采用非精確一維搜索求步長, 可使相鄰兩個(gè)迭代點(diǎn)處的梯度不正交，從而改變收斂性?？墒瓜噜弮蓚€(gè)迭代點(diǎn)處的梯度不正交，從而改

21、變收斂性。 對(duì)于最速下降法，有時(shí)為了減少計(jì)算工作量，采用固定步對(duì)于最速下降法，有時(shí)為了減少計(jì)算工作量，采用固定步長，稱為固定步長最速下降法。長，稱為固定步長最速下降法。 但但 到底取多大，沒有統(tǒng)一的標(biāo)準(zhǔn)，到底取多大，沒有統(tǒng)一的標(biāo)準(zhǔn)， 取小了，收斂太慢，取小了，收斂太慢，而而 取大了，又會(huì)漏掉極小點(diǎn)。取大了，又會(huì)漏掉極小點(diǎn)。（2）采用不精確的一維搜索：）采用不精確的一維搜索：2kkkdxx（3）采用加速梯度法：）采用加速梯度法： 由于最速下降法在極小點(diǎn)附近成由于最速下降法在極小點(diǎn)附近成“鋸齒鋸齒”狀，因此下降過狀，因此下降過程中的搜索方向可取程中的搜索方向可取 下兩步繼續(xù)用最速下降方向即下兩步繼

22、續(xù)用最速下降方向即負(fù)梯度方向負(fù)梯度方向。 Shah等人于等人于1964年提出了一種年提出了一種“平行切線法平行切線法”（簡記為（簡記為PARTAN法），又稱加速梯度法。法），又稱加速梯度法。負(fù)梯度方向和負(fù)梯度方向和 結(jié)合結(jié)合2kkkdxx這兩種方向交替使用，效用要比最速下降法好的多。這兩種方向交替使用，效用要比最速下降法好的多。1x kx0k 21211,0.kx則二次函數(shù)二次函數(shù) A為對(duì)稱正定，為對(duì)稱正定， 分別分別 為其最小和最大特征值，從任意初點(diǎn)為其最小和最大特征值，從任意初點(diǎn) 出發(fā)，對(duì)二次函出發(fā)，對(duì)二次函 數(shù)，用最速下降法產(chǎn)生的序列數(shù)，用最速下降法產(chǎn)生的序列 ，對(duì)于，對(duì)于 有有( )

23、1/2,Tf xx Ax12, 由于由于 而函數(shù)而函數(shù) 的極小點(diǎn)恰好是的極小點(diǎn)恰好是 。故最速下。故最速下降法對(duì)于降法對(duì)于二次函數(shù)關(guān)于任意初點(diǎn)均收斂二次函數(shù)關(guān)于任意初點(diǎn)均收斂，而且是，而且是線性收斂線性收斂的。的。1( )2Tf xx Ax122121()()(),kkf xf x+1+11221121kkxx*0 x 下面說明最速下降法收斂性的幾何意義?？紤]具有對(duì)稱正下面說明最速下降法收斂性的幾何意義?？紤]具有對(duì)稱正交矩陣的函數(shù)交矩陣的函數(shù)12, 0,f x xc c函數(shù)的等值線為函數(shù)的等值線為其中其中 22112211( )22Tf xx Axxx1200A210改寫為：改寫為：22122

24、212122xxcc12 c22 c121222c22 c0 x1x 這是以這是以 和和 為半軸的為半軸的橢橢圓圓 從下面的分析可見從下面的分析可見 兩個(gè)特征值的相對(duì)兩個(gè)特征值的相對(duì) 大小決定最速下降法的收斂性。大小決定最速下降法的收斂性。 （1）當(dāng)）當(dāng) 時(shí)，等值線時(shí)，等值線變?yōu)閳A變?yōu)閳A 此時(shí)此時(shí) 因而由上述定理知因而由上述定理知：212101100 | 0 xx 即只需迭代一步就到了極小點(diǎn)，這表明最速下降法用于等即只需迭代一步就到了極小點(diǎn)，這表明最速下降法用于等值線為圓的目標(biāo)出發(fā)時(shí)，只需迭代一步就到了極小點(diǎn)值線為圓的目標(biāo)出發(fā)時(shí)，只需迭代一步就到了極小點(diǎn)。1x2x1x2x（2）當(dāng)）當(dāng) 時(shí)時(shí),

25、等值線為橢圓。此時(shí)對(duì)于一般的初始點(diǎn)等值線為橢圓。此時(shí)對(duì)于一般的初始點(diǎn)將產(chǎn)生鋸齒現(xiàn)象。將產(chǎn)生鋸齒現(xiàn)象。2210121kkxx （3）當(dāng)）當(dāng) ， 等值線是很扁的橢圓等值線是很扁的橢圓 此時(shí)此時(shí) ，對(duì)于一般的初始點(diǎn)，對(duì)于一般的初始點(diǎn),收斂收斂 速度可能十分緩慢，鋸齒現(xiàn)象嚴(yán)重。速度可能十分緩慢，鋸齒現(xiàn)象嚴(yán)重。21211120 x1x2x 前面介紹精確一維搜索時(shí)介紹了牛頓法，即用目標(biāo)函前面介紹精確一維搜索時(shí)介紹了牛頓法，即用目標(biāo)函數(shù)的二次泰勒多項(xiàng)式近似代替函數(shù)本身，用二次多項(xiàng)式的極數(shù)的二次泰勒多項(xiàng)式近似代替函數(shù)本身，用二次多項(xiàng)式的極小點(diǎn)近似函數(shù)的極小點(diǎn)。小點(diǎn)近似函數(shù)的極小點(diǎn)。 這種方法可以推廣到多維的情

26、形。這種方法可以推廣到多維的情形。 求解無約束極小化問題的最古老的算法之一，現(xiàn)在已經(jīng)求解無約束極小化問題的最古老的算法之一，現(xiàn)在已經(jīng)發(fā)展成一類算法發(fā)展成一類算法-Newton型方法。型方法。1+12kkkkxxfxfx 1()=()kkkkf xxxfx一維優(yōu)化的一維優(yōu)化的Newton迭代公式迭代公式多維優(yōu)化的多維優(yōu)化的Newton迭代公式迭代公式 算法的基本思路：算法的基本思路： 考慮從考慮從 到到 的迭代過程，在的迭代過程，在 點(diǎn)處對(duì)函數(shù)點(diǎn)處對(duì)函數(shù) Tayloy展開：展開：kx1kx f x 22( )()1()2TkkkTkkkkf xf xf xx xx xf xx xo x x 令令

27、 ，有，有kx略去高階項(xiàng)略去高階項(xiàng) 21( )( )()2TTkkkkkkf xQ xf xf xx xx xf xx x 20kkkQ xf xf xxx 若若Hesse矩陣矩陣 正定，則正定，則 存在，由此求出存在，由此求出二次函數(shù)二次函數(shù) 的極小點(diǎn)為的極小點(diǎn)為 ：以此以此 作為作為 極小點(diǎn)極小點(diǎn) 的一個(gè)新的近似。此公式的一個(gè)新的近似。此公式即為多元函數(shù)求極值的即為多元函數(shù)求極值的Newton迭代公式迭代公式。 Q x1kx*x f x2=kkkf xxxf x2kf x12kf x1+12kkkkxxfxfx f x1x11,: 1ffxk12kkkdf xf x 選定初始點(diǎn)選定初始點(diǎn)

28、, 計(jì)算計(jì)算已知目標(biāo)函數(shù)已知目標(biāo)函數(shù) , 給定誤差限給定誤差限 . 如果如果 ，算法停止，算法停止， ，否，否 則轉(zhuǎn)步驟則轉(zhuǎn)步驟3。 計(jì)算搜索方向計(jì)算搜索方向kf x*kxx1,1kkkxxdkk 令令，轉(zhuǎn)步驟，轉(zhuǎn)步驟2. 步驟步驟3中的中的Newton迭代公式，可以換成通過方程組迭代公式，可以換成通過方程組 求得求得 ，這樣可以減少計(jì)算工作，這樣可以減少計(jì)算工作量，而且解線性方程組已有標(biāo)準(zhǔn)程序。量，而且解線性方程組已有標(biāo)準(zhǔn)程序。注意：此時(shí)步注意：此時(shí)步長取常數(shù)長取常數(shù)12+=0kkkf xdf xkd稱為牛頓方向稱為牛頓方向x1, 0, k=12f(xk) d= -f(xk) 得得dk ,

29、xk+1=xk+dk| dk | ,12120TkmmpAppp=+.+TkkkpAp=,故故01kkm= ,= ,., ,0TkipApik = ,0=0+TkkkpAp+.+證明證明： 利用利用性質(zhì)性質(zhì)2即可。即可。 若若Rn中的非零向量中的非零向量p1,p2, pm是是A共軛向量組，則這共軛向量組，則這m 個(gè)向量是線性無關(guān)的。個(gè)向量是線性無關(guān)的。 在在n維空間中互相共軛的非零向量的個(gè)數(shù)不超過維空間中互相共軛的非零向量的個(gè)數(shù)不超過n。 Rn中線性無關(guān)的非零向量最多有中線性無關(guān)的非零向量最多有n個(gè)。個(gè)。 設(shè)設(shè)n元函數(shù)元函數(shù)f(x)=1/2xTAx+bTx+c, A=AT正定，又設(shè)正定，又設(shè)n

30、維非零維非零 向量組向量組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)正交；正交； (2) 最多最多n次迭代必達(dá)到二次函數(shù)次迭代必達(dá)到二次函數(shù)f(x)的極小點(diǎn)。的極小點(diǎn)。 性質(zhì)性質(zhì)4中中(1) f(xk+1)與與p1, p2, pk (k=1,2,n)正交；正交；( )f xAxb 是按照精確一維搜索得到的，所以有是按照精確一維搜索得到的，所以有11()kkf xAxb1( )2TTf xx A

31、xb xck1()0kTkf xp1()()kkkkf xf xAp1()0,1,2,.,1.kTif xpik下證下證()kkkA xpb()kkkAxbAp()kkkf xAp 111()kkkkkf xApAp .11111().iikkikkf xApApAp ,1,2,.,1,ik證明：證明：111111()()().()()TTkiiiiTiikTikTikkf xpf xpAppAppApp 11111()().()()iTiiTiiiTkiTkkkf xppAppAppAp 0 ,P1, P2 , Pn 是是A共軛向量組共軛向量組111111()().kiikkikkf xf

32、xApApAp ,故故 f(xk+1)與與p1, p2, pk (k=1,2,n)正交。正交。性質(zhì)性質(zhì)4中中(1) f(xk+1)與與p1, p2, pk (k=1,2,n)正交；正交；性質(zhì)性質(zhì)4中中(2) 最多最多n次迭代必達(dá)到二次函數(shù)次迭代必達(dá)到二次函數(shù)f(x)的極小點(diǎn)。的極小點(diǎn)。 假設(shè)假設(shè) 都不是都不是0，下證，下證 12(),(),.,()nf xf xf x1()0.nf x 利用利用(1)的結(jié)果，的結(jié)果， 與與A共軛向量組共軛向量組P1, P2 , Pn 都都正交，由正交，由性質(zhì)性質(zhì)1可知，可知，1()nf x1()0.nf x證明：證明： 在在n維空間中與維空間中與n個(gè)線性無關(guān)的

33、向量都正交的一定是零向量。個(gè)線性無關(guān)的向量都正交的一定是零向量。 設(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)正交；正交； (2) 最多最多n次迭代必達(dá)到二次函數(shù)次迭代必達(dá)到二次函數(shù)f(x)的極小點(diǎn)。的極小點(diǎn)。 一個(gè)算法若能在有限步內(nèi)求得正定二次函數(shù)的極小點(diǎn)，一個(gè)算法若能在有限步內(nèi)求得

34、正定二次函數(shù)的極小點(diǎn)， 則稱該算法具有二次收斂性則稱該算法具有二次收斂性(又稱二次終止性又稱二次終止性)。 由由性質(zhì)性質(zhì)4可知，若能找到一組可知，若能找到一組A共軛向量，共軛向量， 則前面提到的結(jié)合最速下降法和則前面提到的結(jié)合最速下降法和Newton法優(yōu)點(diǎn)的算法就找到了，法優(yōu)點(diǎn)的算法就找到了，就是就是共軛方向法共軛方向法， 這個(gè)算法具有二次收斂性。這個(gè)算法具有二次收斂性。 在下降迭代法中，若取下降方向是共軛方向，所得到的方法在下降迭代法中，若取下降方向是共軛方向，所得到的方法我們稱為我們稱為。怎么選取共軛方向？怎么選取共軛方向？ 共軛方向的選取有很大任意性，而一組不同的共軛方向共軛方向的選取有

35、很大任意性，而一組不同的共軛方向就對(duì)應(yīng)著不同的共軛方向法。就對(duì)應(yīng)著不同的共軛方向法。 作為一種迭代算法，我們自然希望共軛方向能在迭代過作為一種迭代算法，我們自然希望共軛方向能在迭代過程中逐次生成。程中逐次生成。 下面先以下面先以正定二次函數(shù)為例，介紹一種生成共軛方向的方正定二次函數(shù)為例，介紹一種生成共軛方向的方法法，再將這種方法推廣到非二次函數(shù)上。，再將這種方法推廣到非二次函數(shù)上。 這種方法這種方法中每一個(gè)共軛向量都是依賴于迭代點(diǎn)處的負(fù)梯度而中每一個(gè)共軛向量都是依賴于迭代點(diǎn)處的負(fù)梯度而構(gòu)造出來構(gòu)造出來，所以稱為，所以稱為共軛梯度法共軛梯度法，它，它是共軛方向法中的一種。是共軛方向法中的一種。令

36、令1( ),2TTf xx Axb xcAA正定T (2) 若若 ，停止，停止，成的正交錐中找一個(gè)向量成的正交錐中找一個(gè)向量 ，即令，即令 使得使得 與與 共軛，即共軛，即由由21()0.TpAp(1) 從任取初始點(diǎn)從任取初始點(diǎn)x1 出發(fā)，沿出發(fā)，沿負(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è)向量

37、 ，即令，即令 使得使得 與與 共軛，即共軛，即由由1()0.kTkpAp(3) 在在x2 處沿處沿 p2 方向進(jìn)行精確一維搜索，方向進(jìn)行精確一維搜索，3222,xxp1()0kf x1()kf xkp1kp11()kkkkpf xp kp1kp11()0() kTkkkTkkpApf xpAp可得可得1()()kTkkkTkf xAppAp(4) 以此類推，以此類推，45,.x x否則在否則在 和和 張張?k這樣便構(gòu)造了一組向量這樣便構(gòu)造了一組向量11(),1,2,.,1, kkkkpf xpkn12,.,np pp 實(shí)際上，這組向量實(shí)際上，這組向量 是一個(gè)是一個(gè)A共軛向量組。共軛向量組。1

38、2,.,np pp相鄰兩個(gè)向量是共軛的相鄰兩個(gè)向量是共軛的11(), pf x1()(),kTkkkTkf xAppAp設(shè)向量組設(shè)向量組 是由上述方法產(chǎn)生的向量組，向量是由上述方法產(chǎn)生的向量組，向量 組組 是由各點(diǎn)的梯度生成的向量組，是由各點(diǎn)的梯度生成的向量組， ( ) 則則 (1) 是正交向量組；是正交向量組； (2) 是是A共軛向量組。共軛向量組。12,.,np pp() kkgf x12,.,np pp12,.,ng gg12,.,ng gg設(shè)向量組設(shè)向量組 是由上述方法產(chǎn)生的向量組，向量組是由上述方法產(chǎn)生的向量組，向量組 是由各點(diǎn)的梯度生成的向量組，是由各點(diǎn)的梯度生成的向量組， ( )

39、 則則 (1) 是正交向量組；是正交向量組； (2) 是是A共軛向量組。共軛向量組。12,.,np pp( )kkgf x12,.,np pp12,.,ng gg12,.,ng gg 2=i n由由 的構(gòu)造過程知，的構(gòu)造過程知，ip12,p p是是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é)論成立，只

40、需證明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,.,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)行精

41、確一維搜索，則 (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,., ,+=TikTkiTiikigpigggppik0= ,(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共軛的共軛的;

42、1+= TikgAp121=0= , ,., -TkipApik，11()+iiiiiiiiiiggAxbgA xpbgAp11+=TTkiikpApgAp11+=Tiikiggg 111+=/Tikiiggg0=112+=0= , ,.,Tkiggik，1+=TkikkgpAp設(shè)向量組設(shè)向量組 是由上述方法產(chǎn)生的向量組，向量是由上述方法產(chǎn)生的向量組，向量 組組 是由各點(diǎn)的梯度生成的向量組，是由各點(diǎn)的梯度生成的向量組， ( ) 則則 (1) 是正交向量組；是正交向量組； (2) 是是A共軛向量組。共軛向量組。12,.,np pp() kkgf x12,.,np pp12,.,ng gg注：為保

43、證方向的共軛性，初始方向取負(fù)梯度方向。注：為保證方向的共軛性，初始方向取負(fù)梯度方向。12,.,ng gg 設(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)正交；正交； (2) 最多最多n次迭代必達(dá)到正定二次函數(shù)次迭代必達(dá)到正定二次函數(shù)f(x)的極小點(diǎn)。的極小點(diǎn)。 11111(),(),1

44、,2,.,1,(*)().()kkkkkTkkkTkpf xpf xpknf xAppAp 是一個(gè)是一個(gè)A共軛向量組共軛向量組12,.,np pp每一個(gè)搜索方向都依賴迭代點(diǎn)處的每一個(gè)搜索方向都依賴迭代點(diǎn)處的負(fù)梯度構(gòu)造出來負(fù)梯度構(gòu)造出來，對(duì)應(yīng)的算法稱為，對(duì)應(yīng)的算法稱為共軛梯度法共軛梯度法。存在問題：計(jì)算量、存儲(chǔ)量都很大存在問題：計(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)找到

45、了一組共軛方向：針對(duì)一般的函數(shù)，將這組方向進(jìn)行推廣：針對(duì)一般的函數(shù)，將這組方向進(jìn)行推廣：2 kAfx直接對(duì)直接對(duì)(*)式推廣：式推廣：在正定二次函數(shù)在正定二次函數(shù)的前提下，將的前提下，將 變形變形怎么解決呢？怎么解決呢？能否將能否將 中的中的A去掉？去掉？kk設(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)TkkTkkkTkkTk

46、kgApf xApDanielpAppAp +1+1+1() ()(2)(,1972)() ()kkkkkTkkTgggSorensonWolfepgg +1+1()(3)(,1972)()kkkTkkTggDixonMyerspg 1+1()kkkkkkkkkkggAxbgA xpbgAp 利用定理利用定理1，可知，可知 是正交向量組，因此是正交向量組，因此(2)中中 ; 并且并且 .+1+1+1() ()(2)(,1972)() ()kkkkkTkkTgggSorensonWolfepgg +1+1()(3)(,1972)()kkkTkkTggDixonMyerspg 12,.,ng gg

47、10+=Tkkgg10+=Tkkgp+122(4)(Re,1964)kkkgFlecherevesg +1+1()(3)(,1972)()kkkTkkTggDixonMyerspg +1+1() ()(5)(,1969)()kkkkkTkTgggPolyakPolakRibieregg -1-12-1-1)()kkkkkTkTkkkkkpgppggpgg在(3)中，由,得到( +122(4)(Re,1964)kkkgFlecherevesg +1+1+1() ()(2)(,1972)() ()kkkkkTkk TgggSorenson Wolfepgg 1+11() ()=()()()(2)k

48、TkTkTTkkkkkkkkpggpggpggg中 +1+1() ()(5)(,1969)()kkkkkTkTgggPolyakPolakRibieregg 對(duì)于正定二次函數(shù)，上面得到的對(duì)于正定二次函數(shù)，上面得到的5個(gè)計(jì)算公式是等價(jià)的；個(gè)計(jì)算公式是等價(jià)的； 這這5種共軛梯度法也是完全等價(jià)的；種共軛梯度法也是完全等價(jià)的；1+1()()(,1967)()()(1)TkkTkkkTkkTkkgApf xApDanielpAppAp +1+1+1() ()(2)(,1972)() ()kkkkkTkkTgggSorensonWolfepgg +1+1()(3)(,1972)()kkkTkkTggDix

49、onMyerspg +1+1() ()(5)(,1969)()kkkkkTkTgggPolyakPolakRibieregg +122(4)(Re,1964)kkkgFlecherevesg SW共軛梯度法共軛梯度法DM共軛梯度法共軛梯度法FR共軛梯度法共軛梯度法PPR共軛梯度法共軛梯度法介紹介紹FR共軛梯度法共軛梯度法Daniel共軛梯度法共軛梯度法簡潔，用的最多簡潔，用的最多更好用更好用 對(duì)于非二次函數(shù)，產(chǎn)生的搜索方向不再相同，對(duì)于非二次函數(shù)，產(chǎn)生的搜索方向不再相同， 利用公式利用公式(2)-(5), (1)中含有中含有Hesse矩陣，通常不用矩陣，通常不用1x+122,kkkgg步驟步驟

50、1. 選定初始點(diǎn)選定初始點(diǎn) 。步驟步驟2. 如果如果 ，算法停止，算法停止， ，否則轉(zhuǎn)步驟，否則轉(zhuǎn)步驟3。步驟步驟4. 精確一維搜索找最佳步長精確一維搜索找最佳步長 ，令，令1g*1xx*+1,kxx步驟步驟3. 取取k1kkkkxxp步驟步驟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)步驟4。11=, =1.pg k1+11+1=,=,kkxxpg+11,1, kkkkpgpkk步驟步驟4. 精確一維搜索找最佳步長精確一維搜索找最佳步長 ，令

51、，令*+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)步驟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：重新開始技術(shù)：重新開始技術(shù)：xn+1作為新的作

52、為新的x1+122,kkkgg+11,1, kkkkpgpkk2212112( )242fxxxx xx，已知初始點(diǎn)，已知初始點(diǎn)(1,1)T解：解： 1）第一次迭代：沿負(fù)梯度方向搜尋）第一次迭代：沿負(fù)梯度方向搜尋計(jì)算初始點(diǎn)處的梯度計(jì)算初始點(diǎn)處的梯度11211212244()422x xxxgf xxx=, 迭代精度迭代精度 。 1142pg ,1114141212xp 0.001精確一維搜索求最佳步長，精確一維搜索求最佳步長，令令10.25211120.5xxp,221()2gf x ,11141 2xp 112()(14 12 ) 40203f xpf =,=, 08020= =, 得得不滿

53、足精度，繼續(xù)迭代：不滿足精度，繼續(xù)迭代：2）第二次迭代：）第二次迭代：2221150.2520gg2121pgp 22xp220.5x,212g,142p,142g,21.5,22220.51.50.5 1.5,精確一維搜索求最佳步長，精確一維搜索求最佳步長， 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 ,1

54、1220.51.5=xp42, 342xx *. 共軛梯度法對(duì)正定二次函數(shù)，具有二次收斂性；共軛梯度法對(duì)正定二次函數(shù)，具有二次收斂性； 對(duì)非二次函數(shù)，由于目標(biāo)函數(shù)的對(duì)非二次函數(shù)，由于目標(biāo)函數(shù)的Hesse矩陣不再是常數(shù)矩矩陣不再是常數(shù)矩陣，因而產(chǎn)生的方向不再是共軛方向；陣，因而產(chǎn)生的方向不再是共軛方向； 共軛梯度法在一定條件下也是收斂的，且收斂速度通常優(yōu)共軛梯度法在一定條件下也是收斂的，且收斂速度通常優(yōu)于最速下降法，具有較高的求解效率。于最速下降法，具有較高的求解效率。 設(shè)設(shè) f (x)存在連續(xù)一階偏導(dǎo)數(shù)，且函數(shù)為凸函數(shù)，且水平集存在連續(xù)一階偏導(dǎo)數(shù)，且函數(shù)為凸函數(shù)，且水平集 有界，則由共軛梯度法

55、得到的點(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*xlim()kkf x 共軛梯度法在無約束優(yōu)化方法中占有重要的地位，是目前最共軛梯度法在無約束優(yōu)化方法中占有重要的地位，是目前最常用的方法之一。常用的方法之一。 (1) 對(duì)凸函數(shù)全局收斂（下降算法）；對(duì)凸函數(shù)全局收斂（下降算法）； (2) 計(jì)算公式簡單，不用求計(jì)算公式簡單，不用求Hesse矩陣或者逆矩陣，計(jì)算量小，矩陣或者逆矩陣，計(jì)算量小

56、， 存儲(chǔ)量小，每步迭代只需存儲(chǔ)若干向量，存儲(chǔ)量小，每步迭代只需存儲(chǔ)若干向量，適用于大規(guī)模問適用于大規(guī)模問 題題； (3) 具有二次收斂性；具有二次收斂性； (對(duì)于正定二次函數(shù)，至多對(duì)于正定二次函數(shù)，至多n次迭代可達(dá)最優(yōu)解）次迭代可達(dá)最優(yōu)解） (4) Crowder和和Wolfe證明，證明，共軛梯度法的收斂速率不壞于最速共軛梯度法的收斂速率不壞于最速 下降法下降法。如果初始方向不用負(fù)梯度方向，則其收斂速率是線。如果初始方向不用負(fù)梯度方向，則其收斂速率是線 性收斂的；性收斂的； (5) 共軛梯度法是目前共軛梯度法是目前求解無約束優(yōu)化問題最常用的方法之一求解無約束優(yōu)化問題最常用的方法之一。注：不同的

57、注：不同的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)，但法具有收斂速度快的優(yōu)點(diǎn)，但需要計(jì)算需要計(jì)算Hesse矩陣的逆，矩陣的逆，計(jì)算量大，存儲(chǔ)量也很大。計(jì)算量大，存儲(chǔ)量也很大。12= kkkpf xf x 為減少計(jì)算量，用一個(gè)為減少計(jì)算量，用一個(gè)n階階對(duì)稱正定矩陣對(duì)稱正定矩陣Hk近似代替近似代替Hesse矩陣的逆矩陣的逆 ，即，即 ，從而搜索方，從而搜索方向是向是 ，由此搜索方向產(chǎn)生的方法稱為變尺度法，由

58、此搜索方向產(chǎn)生的方法稱為變尺度法， Hk稱為尺度矩陣，這是一種稱為尺度矩陣，這是一種擬擬Newton法法，被認(rèn)為是無約束優(yōu)，被認(rèn)為是無約束優(yōu)化問題中最有效的方法之一化問題中最有效的方法之一。12kfx12kkHfx kkkpH g 任取初始點(diǎn)任取初始點(diǎn)x1,初始尺度矩陣初始尺度矩陣H1,令令k=1. 計(jì)算計(jì)算 利用精確一維搜索找最佳步長利用精確一維搜索找最佳步長 ，令，令 令令 ，轉(zhuǎn)步驟，轉(zhuǎn)步驟2。+1=+1kkkHHHkk，kHk+1=+.kkkkxxp. kkkpH gx1, H1對(duì)稱對(duì)稱0, k=1dk=- Hkf(xk)一維搜索得一維搜索得k xk+1=xk+ k dk|xk+1-xk

59、| ?修正修正Hk產(chǎn)生產(chǎn)生Hk+1Stop. xk+1-解解k=k+1yN構(gòu)造構(gòu)造 Hk的原則的原則變尺度法的關(guān)鍵在于如何構(gòu)造變尺度法的關(guān)鍵在于如何構(gòu)造Hk，為了使算法有較快的收斂速為了使算法有較快的收斂速度，需要滿足以下幾個(gè)原則：度，需要滿足以下幾個(gè)原則：擬牛頓性質(zhì)，二次收斂性，穩(wěn)定性。擬牛頓性質(zhì)，二次收斂性，穩(wěn)定性。擬牛頓性質(zhì)擬牛頓性質(zhì)在在 點(diǎn)處對(duì)函數(shù)點(diǎn)處對(duì)函數(shù) 作二階作二階 Tayloy展開：展開：1kx 111212111( )()1()2TkkkTkkkkf xf xf xx xx xf xx xo x x( )f x 略去高階項(xiàng)略去高階項(xiàng) 11112111( )()2TTkkkkk

60、kf xf xf xx xx xf xx x在在xk+1 附近，函數(shù)兩端求導(dǎo)，得附近，函數(shù)兩端求導(dǎo)，得1211( )kkkf xf xf xx x211+1kkkkkggf xxx令令 可得可得記記21(1)kkkgf xxHesse矩陣矩陣 對(duì)稱正定，又有對(duì)稱正定，又有121(2) kkkxf xg = ,=,kkkx x gf x1+1=,=,kkkkkkg ggx xx2+1kf x 11112111( )()2TTkkkkkkf xf xf xx xx xf xx x211+1+kkkkkggf xxx=(3)kkgA x1=(4)kkxAg( )=1/2+TTf xx Ax b x