1、10， 使用導(dǎo)數(shù)的最優(yōu)化方法,最優(yōu)化理論與算法,第十章 使用導(dǎo)數(shù)的最優(yōu)化方法,最速下降法 牛頓法 共軛梯度法 擬牛頓法 信賴域法,10.1最速下降法,10.1最速下降法,考慮無約束問題 min f(x), xRn (10.1.1) 其中 f(x)具有一階連續(xù)偏導(dǎo)數(shù)。,在處理這類問題時(shí)，一般策略是，希望從某一點(diǎn)出發(fā)，選擇 一個(gè)目標(biāo)函數(shù)值下降最快的方向，沿此方向搜索以期盡快達(dá) 到極小點(diǎn)，基于這一思想，Cauchy于1847年提出了最速下降 法。這是無約束最優(yōu)化中最簡單的方法。,10.1最速下降法1,函數(shù)f(x)在點(diǎn)x處沿方向d的變化率可用方向?qū)?shù)表示，當(dāng)函數(shù)可微時(shí)有，方向?qū)?shù),求函數(shù)f(x)在點(diǎn)x

2、處下降最快的方向,歸結(jié)為求,10.1最速下降法2,由上式知.當(dāng),時(shí)等號(hào)成立.故在點(diǎn)x處沿(1.5)所定義的方向變化率最小,即負(fù)梯度方向?yàn)樽钏傧陆捣较?,注意:在不同的尺度下最速下降方向是不同的.,10.1最速下降法3,最速下降算法,最速下降算法的迭代公式為,10.1最速下降法4,算法描述,例1.1 用最速下降法求解下列問題,第一次迭代,目標(biāo)函數(shù)f(x)在點(diǎn)x處的梯度,令搜索方向,令,在直線上的極小點(diǎn),第二次迭代,令,得到,第三次迭代,令,此時(shí),已經(jīng)滿足精度要求,得近似解,問題的最優(yōu)解為x*=(0.0),算法的收斂性,證明:最速下降算法A可表示為合成映射,A=MD,其中D(x)=(x,-f(x)

3、,是En En En的映射.,每給定一點(diǎn)x,經(jīng)算法D作用,得到點(diǎn)x和在x處的 負(fù)梯度(從x出發(fā)的方向d).算法M是En En En,映射.每給定一點(diǎn)x及方向d=-f(x),經(jīng)M作用,即一維搜索,得到一個(gè)新點(diǎn),在這一點(diǎn),與前面的迭代點(diǎn)相比,具有較小的目標(biāo)函數(shù)值,根據(jù)Th1.1,當(dāng) f(x) 0時(shí),M是閉映射.由于f(x)是連續(xù)可微實(shí)函數(shù), 故D連續(xù),據(jù)Th8.1.1推論2,A在x(f(x) 0)處是閉的.,其次,當(dāng)x時(shí), d=-f(x) 0,則f(x) T d0,因此 對(duì)于yA(x),有f(y)f(x),由此知f(x)是關(guān)于A和的下降函數(shù),因此根據(jù)Th8.2.1,算法收斂,最后,按假設(shè),x(k)

4、含于緊集,在上述定理中,若令r=A/a,則,定理表明:條件數(shù)越小,收斂越快;條件數(shù)越大,收斂越慢.,最速下降法存在鋸齒現(xiàn)象,容易證明,用最速下降法極小化目標(biāo)函數(shù)時(shí),相鄰兩個(gè)搜索方向是正交的.令,10.2 牛頓法,10.2.1 迭代格式,即,10.2 牛頓法,注意:牛頓法的迭代格式也可以從最速下降方向的角度來理解.,下求A度量下的最速下降方向,為此,考慮,10.2 牛頓法,下面介紹一下A度量及其意義下的最速下降方向.設(shè)A為對(duì)稱正定矩陣,向量d的A范數(shù)定義為,由A, A-1對(duì)稱正定,故存在對(duì)稱平方根A1/2 , A-1/2,使得,于是,10.2 牛頓法,去掉絕對(duì)值符號(hào),有,根據(jù)Schwartz不等

5、式,得到,10.2 牛頓法,即,10.2 牛頓法,若取,則牛頓法的搜索方向?qū)嶋H上是關(guān)于向量橢球范數(shù),10.2 牛頓法,10.2 牛頓法,例 用牛頓法求解下列問題,第1次迭代,10.2牛頓法,第2次迭代,10.2 牛頓法,第3次迭代,繼續(xù)下去,第4次迭代,得到點(diǎn)列收斂于(1,0),此為 最優(yōu)解.,10.2 牛頓法,10.2.2 局部收斂性,10.2 牛頓法,證明:根據(jù)(10.2.2)，牛頓算法映射定義為,下證(x) 是關(guān)于解集合和算法A的下降函數(shù).,10.2 牛頓法,于是可得,從而(x) 是關(guān)于解集合和算法A的下降函數(shù),10.2 牛頓法,10.2 牛頓法,當(dāng)牛頓法收斂時(shí),有下列關(guān)系,特別的,對(duì)于

6、二次凸函數(shù),用牛頓法求解,經(jīng)一次迭代即達(dá)到極小點(diǎn).設(shè)有二次凸函數(shù),其中A是對(duì)稱正定矩陣,10.2 牛頓法,先用極值條件求解.令,得最優(yōu)解,下用牛頓法解,任取一初始點(diǎn)x(1),定義:若一個(gè)算法用于求解嚴(yán)格二次凸函數(shù)極小值問題時(shí) 從任意初始點(diǎn)出發(fā),算法在有限次迭代后可到達(dá)函數(shù)的極 小值點(diǎn),稱此算法具有二次終止性.,于是牛頓法具有二次終止性,10.2 牛頓法,注意,當(dāng)初始點(diǎn)遠(yuǎn)離極小點(diǎn)時(shí),牛頓法可能不收斂,阻尼牛頓法,基本思想:增加了沿牛頓方向的一維搜索.,迭代公式為,10.2 牛頓法,算法(阻尼牛頓法),10.2 牛頓法,10.2.3 修正牛頓法,例 用阻尼牛頓法求解下列問題,牛頓方向,10.2 牛

7、頓法,顯然,用阻尼牛頓法不能產(chǎn)生新點(diǎn), 而點(diǎn)x(1) =(0,0) T并不是問題極小點(diǎn).可見從x(1)出發(fā),用阻尼牛頓法求不出問題的極小點(diǎn), 原因在于 Hessian 矩陣 2f (x(1)非正定,再令,10.2 牛頓法,考慮 (10.2.2),記搜索方向d(k) = x- x(k),阻尼牛頓法所用搜索方向是上述方程的解,此處假設(shè)逆矩陣 存在,10.2 牛頓法,再沿此方向作一維搜索,10.2 牛頓法,算法 修正牛頓法,10.2 牛頓法,10.3共軛梯度法,1 共軛方向與擴(kuò)張子空間定理,定義10.3.1 設(shè)A是nn對(duì)稱矩陣,若Rn 中的兩個(gè)方向d 1 和d2滿足 (d 1)T Ad 2 =0 （

8、10.3.1） 則稱這兩個(gè)方向關(guān)于A共軛,或稱它們關(guān)于A正交.,10.3 共軛梯度法,幾何意義,f(x)的等值面,由于,10.3共軛梯度法,設(shè) x(1)是在某等值面上一點(diǎn),此面在點(diǎn)x(1)處的法向量,又設(shè)d (1)是在該等值面在點(diǎn)x (1)處的一切向量.,即等值面上一點(diǎn)x(1)處的切向量與由這點(diǎn)指向極小點(diǎn)的向量關(guān)于A共軛.,10.3共軛梯度法,10.3共軛梯度法,10.3共軛梯度法,10.3共軛梯度法,用歸納法證之,為方便,用g j表示函數(shù)f(x)在x(j)處的梯度,即,10.3共軛梯度法,利用上式可以將 gm+2 和d (i) 的內(nèi)積寫成,當(dāng)i=m+1時(shí),由一維搜索定義,知,當(dāng)1im+1時(shí),

9、由歸納假設(shè)知,由二次函數(shù)梯度的表達(dá)式和點(diǎn)x(k+1)的定義,有,10.3共軛梯度法,即,由10.3.8-11,知,10.3共軛梯度法,上述定理表明,對(duì)于二次凸函數(shù),若沿一組共軛方 向(非零向量)搜索,經(jīng)有限步迭代必到達(dá)極小點(diǎn).,2 線性共軛梯度法與二次終止性,Hesteness和Stiefel于1952年為解線性方程組而提出,基本思想:把共軛性與最速下降法相結(jié)合,利用已知點(diǎn)處的梯度構(gòu)造一組共軛方向,并沿著這組方向進(jìn)行搜索,求出目標(biāo)函數(shù)的極小點(diǎn),10.3共軛梯度法,先討論對(duì)于二次凸函數(shù)的共軛梯度法,考慮問題,求解方法,10.3共軛梯度法,10.3共軛梯度法,10.3共軛梯度法,綜上分析,在第一個(gè)

10、搜索方向取負(fù)梯度的前提下,重復(fù)使用公式3.14,3.17-3.19就能伴隨計(jì)算點(diǎn)的增加,構(gòu)造出一組搜索方向.,10.3共軛梯度法,定理10.3.3 對(duì)于正定二次函數(shù)(10.3.12),具有精確一維搜索的Fletcher-Reeves法在mn次一維搜索后即終止,并且對(duì)所有i(1 i m),下列關(guān)系成立:,證明: 顯然m1,下用歸納法(對(duì)i)證之.,10.3共軛梯度法,設(shè)對(duì)某個(gè)im,這些關(guān)系均成立,我們證明對(duì)于i+1 也成立.先證2),由迭代公式兩端左乘A,再加上b,得,其中 由式(10.3.17)確定,即,10.3共軛梯度法,考慮到(10.3.20)和(10.3.18),則,10.3共軛梯度法,

11、當(dāng)ji時(shí),根據(jù)歸納假設(shè),式(10.3.22)等號(hào)右端各項(xiàng)均為0,再證1),運(yùn)用(10.3.18)和(10.3.20),則,當(dāng)j=i時(shí),把(10.3.19)代入上式第一個(gè)等號(hào)的右端,立得,10.3共軛梯度法,當(dāng)ji時(shí),由前面已經(jīng)證明的結(jié)論和歸納假設(shè),式中 第2個(gè)等號(hào)右端顯然為0,因此,最后證3),易知,綜上,對(duì)i+1,上述三種關(guān)系成立,10.3共軛梯度法,注意,初始搜索方向選擇最速下降方向十分重要, 如果選擇別的方向作為初始方向,其余方向均按FR方法構(gòu)造,則極小化正定二次函數(shù)時(shí),這樣構(gòu)造出來的一組方向并不能保證共軛性.,例 考慮下列問題,取初始點(diǎn)和初始搜索方向分別為,10.3共軛梯度法,顯然,

12、不是目標(biāo)函數(shù)在 處的最速下降方向.,下面,我們用FR法構(gòu)造兩個(gè)搜索方向.,令,10.3共軛梯度法,根據(jù)公式(10.3.19),有,因此,10.3共軛梯度法,令,根據(jù)公式(10.3.19),有,10.3共軛梯度法,注意,在FR法中,初始搜索方向必須取最速下降方向,因此,10.3共軛梯度法,可以證明,對(duì)于正定二次函數(shù),運(yùn)用FR法時(shí)不作矩陣運(yùn)算就能求出因子i,定理10.3.4 對(duì)于正定二次函數(shù),FR法中因子i具有下述表達(dá)式,證明:,10.3共軛梯度法,10.3共軛梯度法,FR法(對(duì)二次凸函數(shù)),10.3共軛梯度法,例3.2 用FR法求解下列問題,10.3共軛梯度法,令,第一次迭代，,目標(biāo)函數(shù)f(x)

13、在點(diǎn)x處的梯度,10.3共軛梯度法,第2次迭代,10.3共軛梯度法,令,10.3共軛梯度法,10.3 共軛梯度法,一般迭代格式,3用于一般函數(shù)的共軛梯度法非線性共軛梯度法,10.3共軛梯度法,-PRP(Polak-Ribiere-Polyar,-SW(Sorenson-Wolfe,-Daniel,-Dixon,10.3共軛梯度法,FR共軛梯度法,10.3共軛梯度法,3,如果j n,轉(zhuǎn)步4,否則,轉(zhuǎn)5,可以證明,對(duì)一般函數(shù),共軛梯度法在一定條件下是收斂的,10.3共軛梯度法,FR算法中使用精確線搜索，我們有如下收斂性結(jié)果,4. 1 擬牛頓條件和算法步驟,10.4 擬牛頓法,基本思想: 牛頓法成功

14、的關(guān)鍵在于利用了Hesse矩陣提供的曲率信息，而計(jì)算Hesse矩陣工作量大，并且有的目標(biāo)函數(shù)的Hesse矩陣很難計(jì)算，甚至不好求出，這就導(dǎo)致僅利用目標(biāo)函數(shù)一階導(dǎo)數(shù)的方法,擬牛頓法就是利用目標(biāo)函數(shù)值f和一階導(dǎo)數(shù)g的信息,構(gòu)造出目標(biāo)函數(shù)的 曲率近似，而不需要明顯形成Hesse矩陣，同時(shí)具有收斂速度快的優(yōu)點(diǎn)。,牛頓法的迭代公式為,10.4 擬牛頓法,10.4擬牛頓法,記,10.4 擬牛頓法,則,(10.4.8)稱為擬牛頓條件(方程)，也稱為割線方程. 怎樣確定滿足這個(gè)條件的H k+1 ?,10.4 擬牛頓法,算法 擬牛頓法,10.4 擬牛頓法,4. 2 對(duì)稱秩1校正,Hk稱為校正矩陣.確定Hk的一個(gè)

15、方法是令,10.4 擬牛頓法,(10.4.10),(10.4.11),利用(10.4.10),(10.4.12-13),(10.4.9)可寫成,10.4 擬牛頓法,(10.4.13),10.4 擬牛頓法,4.3 對(duì)稱秩2校正,10.4 擬牛頓法,1，DFP算法(變尺度法),DFP算法,10.4 擬牛頓法,10.4擬牛頓法,例1用DFP方法求解下列問題,10.4擬牛頓法,初始點(diǎn)及初始矩陣分別為,第1次迭代,10.4擬牛頓法,令搜索方向,得到,令,10.4擬牛頓法,第2次迭代,10.4擬牛頓法,10.4擬牛頓法,令,10.4擬牛頓法,10.4擬牛頓法,得到,令,于是得最優(yōu)解,10.4擬牛頓法,2

16、DFP算法的正定性及二次終止性,10.4擬牛頓法,證明:用歸納法 DFP方法中, H1是給定的對(duì)稱正定矩陣.,設(shè)Hj是對(duì)稱正定矩陣,下證Hj+1也是對(duì)稱正定矩陣.,根據(jù)定義,對(duì)稱性是顯然的,下證正定性,(10.4.19),10.4擬牛頓法,令,10.4擬牛頓法,則,由Schwartz不等式,有,10.4擬牛頓法,(10.4.22),考慮到一維搜索及方向的定義,(10.4.21)右端第一項(xiàng) 的分母,于是,10.4擬牛頓法,下證(10.4.22)和(10.4.24)不同時(shí)為0.,若不然,(10.4.22)為0,則p/q,即p=q(0).,從而,綜上,知,10.4擬牛頓法,證明:對(duì)k歸納. k=1時(shí)

17、有,10.4擬牛頓法,(10.4.27),由于,當(dāng)k=2時(shí),10.4擬牛頓法,由此結(jié)果,易證k=2時(shí)(10.4.26)亦成立,下設(shè)k=m時(shí)(10.4.25-26)成立,下證當(dāng)k=m+1時(shí) 上述關(guān)系式也成立.,先證k=m+1時(shí)(10.4.25)成立.,由歸納假設(shè),只需證:,由對(duì)(10.4.26)的歸納假設(shè),當(dāng)1im時(shí)有,10.4擬牛頓法,由此有,(10.4.29),根據(jù)Th10.3.2的推論,有,由(10.4.29),知,10.4擬牛頓法,再證當(dāng)k=m+1時(shí)(10.4.26)成立,對(duì)于1im+1有,(10.4.30),當(dāng)i=m+1時(shí),由(10.4.28)知,將其代入(10.4.30)得,10.4擬牛頓法,當(dāng)im+1時(shí),根據(jù)關(guān)于(10.4.26)的歸納假設(shè)及當(dāng)k=m+1 時(shí)(10.4.25)成立,考慮到(10.4.28),則有,推論:在Th10.4.2的條件下,必有,10.4擬牛頓法,DFP方