共軛方向法.ppt

1、, 4.3 共軛方向法 與共軛梯度法,算法特點,（）建立在二次模型上，具有二次終止性,（）有效的算法，克服了最速下降法的慢,收斂性，又避免了牛頓法的計算量大和局部收,性的缺點,（）算法簡單，易于編程，需存儲空間小等,優(yōu)點，是求解大規(guī)模問題的主要方法,共軛方向及其性質(zhì),定義:,設(shè),是,中任一組,非零向量，,如果：,則稱,是關(guān)于,共軛的,注：,若,則是正交的，因此共軛是,正交的推廣,定理:,設(shè),為,階正定陣，,非零向量組,關(guān)于,共軛，,則必線性無關(guān),推論:,設(shè),為,階正定陣，,非零向量組,關(guān)于,共軛，,則向量構(gòu)成,的一組基,推論:,設(shè),為,階正定陣，,非零向量組,關(guān)于,共軛，,若向量,與,關(guān)于,共

2、軛，,則,共軛方向法算法,Step1:,給出,計算,和初始下降方向,Step2:,如果,停止迭代,Step3:,計算,使得,Step4:,采用某種共軛方向法計算,使得：,Step5:,令,轉(zhuǎn)Step2.,具有二次終止性，但是它僅是一個概念性算法，實現(xiàn)它的關(guān)鍵在于如何選取共軛方向，不同的選取會產(chǎn)生不同的共軛方向法.,共軛方向法基本定理,定義2:,設(shè),維向量組,線性無關(guān)，,向量集合,為,與,生成的,維超平面,引理1:,設(shè),是連續(xù)可微的嚴格凸函數(shù)，,維向量組,線性無關(guān)，,則：,是,在,上,唯一極小點的充要條件是：,證：,構(gòu)造：,分析：,是,(1),維嚴格凸函數(shù),(2),是,在,上的極小點的,充要條件

3、是,是,在,上的極小點,定理2:,設(shè),為,階正定陣，,向量組,關(guān)于,共軛，,對正定二次函數(shù),由任意,開始，,依次進行,次精確線搜索：,則：,（）,（）,是,在,上的極小點,推論:,當,時，,為正定二次函數(shù)在,上的極小點,共軛梯度法,記：,左乘,并使,得：,（Hestenes-Stiefel公式）,?。?共軛梯度法基本性質(zhì),定理3:,對于正定二次函數(shù)，,采用精確線搜索,的共軛梯度法在,步后終止，,且對,成立下列關(guān)系式：,（共軛性）,（正交性）,（下降條件）,系數(shù)的其他形式,（）FR公式,（1964）,（2）PRP公式,（1969）,FR共軛梯度法算法,Step1:,給出,Step2:,計算,如果

4、,停,Step3:,Step4:,由精確線搜索求,Step5:,轉(zhuǎn)Step2.,例4：,用FR共軛梯度法求解：,解：,化成,形式,(1),(2),例5：,用FR共軛梯度法求解：,解：,化成,形式,(1),(2),FR共軛梯度法收斂定理,定理4:,假定,在有界水平集,上連續(xù)可微，,且有下界，,那么采用精確線搜索下的,FR共軛梯度法產(chǎn)生的點列,至少有一個聚點,是駐點，即：,(1),當,是有窮點列時，,其最后一個點是,的駐點,(2),當,是無窮點列時，,它必有聚點，,且任一,聚點都是,的駐點,再開始FR共軛梯度法算法,Step1:,給出,Step2:,計算,如果,停，,Step4:,否則,Step3

5、:,由精確線搜索求,并令：,計算,若,令,轉(zhuǎn)Step2;,如果,停.,Step5:,若,令,轉(zhuǎn)step2.,Step6:,計算,Step7:,如果,令,轉(zhuǎn)step2,否則,轉(zhuǎn)step3.,作業(yè)：FR共軛梯度法（上機）,上機實現(xiàn)FR共軛梯度法,并求解Rosenbrock函數(shù)，,初始點選,線搜索分別采用黃金分割法與強Wolfe線,搜索，并對比, 4.4 擬牛頓法,基本思想,本質(zhì)上是基于逼近牛頓法的方法,牛頓法每次都計算,1959年,Davidon提出,設(shè)想僅用每次迭代中得到的梯度信息來近似海,色陣，基于此導(dǎo)致了一類非常成功的擬牛頓法,本節(jié)介紹Broyden族擬牛頓法：,DFP算法和BFGS算法,算

6、法原理,最速下降法和阻尼牛頓法的迭代公式可統(tǒng)一為：,思考：,要使上面的算法比最速下降法快，比牛頓,法計算簡單，且整體收斂性好，關(guān)鍵在于構(gòu)造,矩陣列,要求：,的選取既能逐步逼近,又無需計算,二階導(dǎo)數(shù)，,且具備以下條件：,C1：,是對稱正定陣,C2：,由,經(jīng)簡單修正而得：,C3：,滿足下面的擬牛頓方程（推導(dǎo)如下）,設(shè),是二次連續(xù)可微的，,令：,則：,令：,因此：,（對二次函數(shù)為等式）,若,非奇異：,設(shè)想：,（擬牛頓方程）,這樣,就可很好的近似,擬牛頓算法,Step1:,給出,Step2:,計算,Step3:,Step4:,精確線搜索求,Step5:,Step6:,計算,若,停；,否則轉(zhuǎn),Step7

7、.,Step7:,校正,使擬牛頓方程成立,Step8:,轉(zhuǎn)Step3.,DFP校正公式,是,維待定向量,要求：,所以：,令：,得：,因此：,所以：,（DFP校正公式）,例6：,用DFP算法求解：,取,解：,(1),(2),注:,（）DFP算法具有二次終止性,（）搜索方向是共軛方向：,DFP校正公式的正定繼承性,引理2:,設(shè),為,正定陣，,且,則：,為正定陣的充要條件是,定理5:,在DFP算法中，,如果,正定，,則整個矩陣列,都正定,DFP算法的二次終止性,推論:,在上面定理條件下：,（1）,DFP算法至多經(jīng)過,次迭代就可得到極,小點，即存在,有：,（2）,若,則,BFGS校正公式,(稱為關(guān)于,

8、的BFGS校正公式或互補DFP公式),由上式可得：,對稱秩一校正公式,要求：,要求Hesse逆近似也是對稱的，,即：,?。?因此：,注:,（1）通常不能保證,（2）分母可能取零,修正公式不再有意義,的正定性,（3）逼近,程度高，,近來用于信賴域算法，,取得了很好的效果,Broyden族,取,注：,得DFP校正,注：,得BFGS校正,得對稱秩一校正,其中：,Broyden族算法性質(zhì),定理6:,設(shè),在,上連續(xù)可微，,給定,在精確線搜索下，,由Broyden族算法產(chǎn)生的點,列,與參數(shù),無關(guān),結(jié)論：,可將DFP算法的性質(zhì)推廣到整個Broyden族,作業(yè),(1)用FR共軛梯度法求解：,(2)用DFP算法

9、求解：,第 五 章,無約束最優(yōu)化方法,第五章 無約束最優(yōu)化,（f） min f(x) f : RnR 5.1 最優(yōu)性條件 設(shè) f 連續(xù)可微 必要條件：若x*l.opt. 則f(x*)=0 (駐點)。 當 f 凸時， x*l.opt. f(x*)=0 注意： f(x) f(x*)+ Tf(x*)(x-x*), x. 故 f(x*) f(x)， x. （ 由于Tf(x*) =0） 5.2 最速下降法 在迭代點 x(k) 取方向 d(k)= f(x(k) ) 精確一維搜索 最 速 下降法：梯度方向函數(shù)值變化最快的方向,第五章 無約束最優(yōu)化,5.2 最速下降法（續(xù)）,第五章 無約束最優(yōu)化,5.2 最速

10、下降法（續(xù)） 特點：全局收斂，線性收斂，易產(chǎn)生扭擺現(xiàn)象而造成早停。 （當x(k)距最優(yōu)點較遠時，速度快，而接近最優(yōu)點時，速度下降） 原因：f(x)=f(x(k)+Tf(x(k)(x-x(k) + o|x-x(k)| 當 x(k)接近 l.opt.時 f(x(k) ) 0，于是高階項 o|x-x(k)|的影響可能超過Tf(x(k)(x-x(k) 。 5.3 Newton法及其修正 一、 Newton法： 設(shè)f(x)二階可微，取f(x)在x(k)點附近的二階Taylor近似函數(shù)： qk(x)=f(x(k)+ Tf(x(k)(x-x(k) +12 (x-x(k)T2f(x(k) (x-x(k) 求駐

11、點： qk(x)= f(x(k)+ 2f(x(k) (x-x(k)=0,第五章 無約束最優(yōu)化,Newton法： （續(xù)） 當2f(x(k) 正定時，有極小點： x(k+1)=x(k)-2f(x(k) -1 f(x(k) Newton迭代公式 實用中常用 2f(x(k) S= -f(x(k) 解得s(k) x(k+1)=x(k)+s(k),第五章 無約束最優(yōu)化,Newton法： （續(xù)） 特點：二階收斂，局部收斂。 （當x(k)充分接近x*時,局部函數(shù)可用正定二次函數(shù)很好地近似，故收斂很快） 二次終結(jié)性：當f(x)為正定二次函數(shù)時，從任意初始點可一步迭代達到最優(yōu)解。 設(shè)f(x)=12xTQx+PTx

12、+r , Qnn對稱正定，P Rn, r R. x(1), f(x(1)=Q x(1) +P 2f(x(1)=Q 迭代： x(2) = x(1) - Q 1(Qx(1) +P) = - Q 1 P (駐點即opt.) 主要缺點： (1)局部收斂 (2)用到二階Hesse陣，且要求正定 (3)需計算Hesse陣逆或解n階線性方程組，計算量大,第五章 無約束最優(yōu)化,5.3 Newton法及其修正 二、 Newton法的改進： (1)為減小工作量，取m（正整數(shù)），使每m次迭代使用同一個Hesse陣，迭代公式變?yōu)椋?x(km+j+1)=x(km+j)-2f(x(km)-1 f(x(km+j) j=0,

13、1,2, ,m-1 , k=0,1,2, 特點：收斂速度隨m的增大而下降 m=1時即Newton法， m 即線性收斂。 (2)帶線性搜索的Newton法： 在Newton迭代中，取d(k)= -2f(x(k) -1 f(x(k) , 加入線性搜索：min f(x(k)+k d(k) 求得k , x(k+1)=x(k)+kd(k) 特點：可改善局部收斂性，當d(k)為函數(shù)上升方向時，可向負方向搜索，但可能出現(xiàn) d(k)均非下降方向的情況。,第五章 無約束最優(yōu)化,5.3 Newton法及其修正 二、 Newton法的改進： （續(xù)） (3)Goldstein-Price方法(G-P法)： 取 d(k

14、)= -2f(x(k) -1 f(x(k) ， 2f(x(k) 正定 - f(x(k) ，否則 采用下列精確一維搜索： 求k，使其中 (0,12) 1 f(x(k)+k d(k) f(x(k)+ f(x(k) Td(k) k 2 f(x(k)+k d(k) f(x(k)+ (1-) f(x(k) Td(k) k 特點：在一定條件下， G-P法全局收斂。 但當2f(x(k) 非正定情況較多時，收斂速度降為接近線性。,第五章 無約束最優(yōu)化,5.3 Newton法及其修正 二、 Newton法的改進： （續(xù)） (4)Levenberg-Marguardt法（L-M法）： 主要思想： 用2f(x(k)

15、 + I 取代2f(x(k) 進行迭代，其中I 為單位矩陣。 0 使 2f(x(k) + I 正定， 盡量小。 特點：全局二階收斂。,第五章 無約束最優(yōu)化,5.4 共軛梯度法 一、共軛梯度法的方向： 設(shè)f(x)=(1/2)xTGx+bTx+c Gnn對稱正定，b Rn,從最速下降方向開始，構(gòu)造一組共軛方向： 設(shè)初始點x(1),取d(1)= -f(x(1) (最速下降方向) 設(shè)k1,已得到k個相互共軛的方向d(1),d(2), ,d(k),以及，由x(1)開始依次沿上述方向精確一維搜索得到點x(2), ，x(k),x(k+1).即有下式： x(i+1)=x(i)+id(i) , i=1,2, ,

16、k 精確一維搜索保證方向?qū)?shù)為0： fT(x(i+1)d(i)=0, i=1,2, ,k 在x(i+1)點構(gòu)造新方向d(k+1)為-f(x(k+1) 與d(1),d(2), ,d(k)的組合：,第五章 無約束最優(yōu)化,5.4 共軛梯度法 一、共軛梯度法的方向： （續(xù)） 使d(k+1)與d(1),d(2), ,d(k)都共軛： d(k+1) TG d(j) =0 , j= 1,2, ,k Gram-Schmidt過程： i, j= 1,2, ,k 記 y(j)= f(x(j+1) -f(x(j) =G(x(j+1)-x(j)=jGd(j) . 根據(jù)式，有 d(i)T y(j) = j d(i)T

17、G d(j)=0 , ij 根據(jù)，有 d(k+1) T y(j) = j d(k+1)T G d(j)=0 , j= 1,2, ,k ,這里的j應(yīng)為i,第五章 無約束最優(yōu)化,5.4 共軛梯度法 一、共軛梯度法的方向： （續(xù)） jk, ij 有 f(x(j+1)T d(i)=0 由式 由式 f(x(j+1)T f(x(i)=0 ijk (由式 ) 根據(jù)及得： j=1,2, ,k-1 - f(x(k+1)T f(x(j+1) - f(x(j)+j(k) d(j)T y(j)=0,第五章 無約束最優(yōu)化,5.4 共軛梯度法 一、共軛梯度法的方向： （續(xù)） 上式中由式有： - f(x(k+1)T f(x

18、(j+1) =0 由式有： j(k) d(j)T y(j)= j(k) jd (j)T Gd(j) 于是 j(k) =0 故式中只有 k(k) 0, 記k = k(k) 可得到公式： d(k+1)= - f(x(k+1)+ k d(k) 當 j=k時，由, 式得：,(11),注意：,第五章 無約束最優(yōu)化,第五章 無約束最優(yōu)化,二、算法流程圖,第五章 無約束最優(yōu)化,5.4 共軛梯度法 三、算法特點： 1、全局收斂（下降算法）；線性收斂； 2、每步迭代只需存儲若干向量（適用于大規(guī)模問題）； 3、有二次終結(jié)性（對于正定二次函數(shù)，至多n次迭代可達opt.） 注：對不同的 k公式，對于正定二次函數(shù)是相等

19、的，對非正定二次函數(shù)，有不同的效果，經(jīng)驗上PRP效果較好。,第五章 無約束最優(yōu)化,5.5 變尺度法 一、變尺度法的基本思路： (f)min f(x), f: R n R 1、基本思想： 用對稱正定矩陣H(k)近似2f(x(k), 而H(k)的產(chǎn)生從給定H(1)開始逐步修整得到。 2、算法框圖：,第五章 無約束最優(yōu)化,5.5 變尺度法 一、變尺度法的基本思路： （續(xù)） 3、擬Newton方程： 記：s(k)=x(k+1)-x(k) , y(k)= f(x(k+1)- f(x(k) 當 f 為二次函數(shù)時：f(x)=1 2xTBx+c T x+b f= B x+c 有 y(k)=Bs(k) 或 s(

20、k)=B-1 y(k) 稱 H y=S 或 y=BS 為擬Newton方程。 顯然 當H 正定時, B-1=H. 4、”近似”： 對于f(x)的二階Taylor展式，舍去高階項， 有 y(k) 2f(x(k)s(k) 或 s(k) ( 2f (x(k)-1 y(k) 用矩陣B(k)或H(K)分別取代 2f(x(k) 或者 ( 2f (x(k)-1 使擬Newton方程成立，可看作是對 2f(x(k) 或( 2f (x(k)-1的一種近似。此種近似H 或 B 不唯一。,第五章 無約束最優(yōu)化,5.5 變尺度法 一、變尺度法的基本思路： （續(xù)） 5、變尺度法的主要特點： 只需用到函數(shù)的一階梯度；（N

21、ewton法用到二階Hesse陣） 下降算法，故全局收斂； 不需求矩陣逆；（計算量小） 一般可達到超線性收斂；（速度快） 有二次終結(jié)性。 二、DFP ( Davidon(1959),Fletcher and Powell(1963) ) 法和 BFGS ( Broyden(1970), Fletcher (1970),Goldfarb(1970),Schanno(1970) ) 法: 1、DFP法： 以下省去各量上標，x, s, y, H 表示第k 步的量， 等表示第k+1步的量。,第五章 無約束最優(yōu)化,5.5 變尺度法 二、DFP 法和BFGS 法: 1、DFP法： （續(xù)）,第五章 5.5

22、變尺度法,二、1、DFP法： （續(xù)） Ex. 用DFP法求解 10 x12+x22 解：取初始點x(1)=(110,1)T, H(1)=I (單位矩陣) 得到如下結(jié)果： （計算過程見下頁）,第五章 5.5 變尺度法,二、1、DFP法： （續(xù)） 計算過程：,第五章 5.5 變尺度法,二、1、DFP法： （續(xù)）,第五章 5.5 變尺度法,二、1、DFP法： （續(xù)） 定理：設(shè)H對稱正定，sTy0那么DFP法產(chǎn)生的 對稱正定。 注：下列各情況下有sTy0： 1 f(x)為正定二次函數(shù)； 2 精確一維搜索時； 3 前章介紹的不精確一維搜索時。 可以證明： DFP法在精確一維搜索前提下，超線性收斂。 2、

23、BFGS法 若把前面的推導(dǎo)，平行地用在y=Bs公式上，可得到,第五章 5.5 變尺度法,二、2、BFGS法（續(xù)） 用此公式求方向時，需用到矩陣求逆或解方程： d= -B-1 f(x) 或 Bd= - f(x) 由于每次只有秩2的變換，這里的計算量仍可以降下來。為了得到H-公式，可對上面 求逆（推導(dǎo)得）： BFGS法有變尺度法的全部優(yōu)點，并且在一定條件下可以證明在BFGS法中使用前文中介紹的不精確一維搜索有全局收斂性。,第五章 5.5 變尺度法,三、Broyden族 當在秩2公式中，、 任意選取時可得到不同的公式，經(jīng)過理論推導(dǎo)，可得到下列結(jié)果：,第五章 5.5 變尺度法,三、Broyden族（續(xù)

24、）,第五章 無約束最優(yōu)化,5.6 直接算法 min f(x) 一、單純形法及可變多面體算法 1、單純形法基本思路： 設(shè) x(0),x(1), x(n)是R n中n+1個點構(gòu)成的一個當前的單純形。 比較各點的函數(shù)值得到：x max,x min使 f( x max)=maxf(x(0),f(x(1), ,f(x(n) f( x min)=minf(x(0),f(x(1), ,f(x(n) 取單純形中除去x max點外，其他各點的形心： 去掉x max，加入x(n+1)得到新的單純形。 重復(fù)上述過程。,第五章 5.6 直接算法,一、1、單純形法基本思路： （續(xù)） 幾點注意： 當x(n+1)又是新單純

25、形的最大值點時，取次大值點進行反射； 若某一個點x出現(xiàn)在連續(xù)m個單純形中的時候，取各點與x連線的中點（n個）與x點構(gòu)成新的單純形，繼續(xù)進行。 經(jīng)驗上取 m 1.65n+0.05n2 例如：n=2時，可取m 1.65 2+0.05 4 =3.5 可取 m=4.,第五章 5.6 直接算法,一、1、單純形法基本思路： （續(xù)） 優(yōu)點：不需求導(dǎo)數(shù)，不需要一維搜索。 缺點：無法加速，收斂慢，效果差。 2、改進單純形法： （可變多面體算法） 設(shè)第k步迭代得到n+1個點： x(0),x(1), x(n) ，得到x max,x min及 通過下列4步操作選新迭代點： 1 反射： 取反射系數(shù) 0,(單純形法中 =1) 2 擴展：給定擴展系數(shù) 1,計算。（加速）,第五章 5.6 直接算法,一、 2、改進單純形法： （續(xù)） 若f(y(1) f(y(2), 那么y(2)取代x max; 否則， y(1)取代x max 。若maxf(x(i)| x(i) x max f(y(1) f(x min), y(1)取代x max 。 3 收縮：若f(x max ) f(y(1) f(x(i), x(i) x max ,計算 ,以y(3)取代x max 。 4 減半：若f(y(1) f(x max ), 重新取各點，使