1、共軛方向法第1頁，共76頁，2022年，5月20日，7點11分，星期一算法特點（）建立在二次模型上，具有二次終止性（）有效的算法，克服了最速下降法的慢收斂性，又避免了牛頓法的計算量大和局部收性的缺點（）算法簡單，易于編程，需存儲空間小等優點，是求解大規模問題的主要方法第2頁，共76頁，2022年，5月20日，7點11分，星期一共軛方向及其性質定義:設是中任一組非零向量，如果：則稱是關于共軛的注：若則是正交的，因此共軛是正交的推廣第3頁，共76頁，2022年，5月20日，7點11分，星期一定理:設為階正定陣，非零向量組關于共軛，則必線性無關推論:設為階正定陣，非零向量組關于共軛，則向量構成的一組

2、基推論:設為階正定陣，非零向量組關于共軛，若向量與關于共軛，則第4頁，共76頁，2022年，5月20日，7點11分，星期一共軛方向法算法Step1:給出計算和初始下降方向Step2:如果停止迭代Step3:計算使得Step4:采用某種共軛方向法計算使得：Step5:令轉Step2.具有二次終止性，但是它僅是一個概念性算法，實現它的關鍵在于如何選取共軛方向，不同的選取會產生不同的共軛方向法.第5頁，共76頁，2022年，5月20日，7點11分，星期一共軛方向法基本定理定義2:設維向量組線性無關，向量集合為與生成的維超平面第6頁，共76頁，2022年，5月20日，7點11分，星期一引理1:設是連續

3、可微的嚴格凸函數，維向量組線性無關，則：是在上唯一極小點的充要條件是：第7頁，共76頁，2022年，5月20日，7點11分，星期一證：構造：分析：是(1)維嚴格凸函數(2)是在上的極小點的充要條件是是在上的極小點第8頁，共76頁，2022年，5月20日，7點11分，星期一定理2:設為階正定陣，向量組關于共軛，對正定二次函數由任意開始，依次進行次精確線搜索：則：（）（）是在上的極小點推論:當時，為正定二次函數在上的極小點第9頁，共76頁，2022年，5月20日，7點11分，星期一共軛梯度法記：左乘并使得：（Hestenes-Stiefel公式）取：第10頁，共76頁，2022年，5月20日，7點

4、11分，星期一共軛梯度法基本性質定理3:對于正定二次函數，采用精確線搜索的共軛梯度法在步后終止，且對成立下列關系式：（共軛性）（正交性）（下降條件）第11頁，共76頁，2022年，5月20日，7點11分，星期一系數的其他形式（）FR公式（1964）（2）PRP公式（1969）第12頁，共76頁，2022年，5月20日，7點11分，星期一FR共軛梯度法算法Step1:給出Step2:計算如果停Step3:Step4:由精確線搜索求Step5:轉Step2.第13頁，共76頁，2022年，5月20日，7點11分，星期一例4：用FR共軛梯度法求解：解：化成形式(1)第14頁，共76頁，2022年，5

5、月20日，7點11分，星期一(2)第15頁，共76頁，2022年，5月20日，7點11分，星期一第16頁，共76頁，2022年，5月20日，7點11分，星期一例5：用FR共軛梯度法求解：解：化成形式(1)第17頁，共76頁，2022年，5月20日，7點11分，星期一(2)第18頁，共76頁，2022年，5月20日，7點11分，星期一FR共軛梯度法收斂定理定理4:假定在有界水平集上連續可微，且有下界，那么采用精確線搜索下的FR共軛梯度法產生的點列至少有一個聚點是駐點，即：(1)當是有窮點列時，其最后一個點是的駐點(2)當是無窮點列時，它必有聚點，且任一聚點都是的駐點第19頁，共76頁，2022年

6、，5月20日，7點11分，星期一再開始FR共軛梯度法算法Step1:給出Step2:計算如果停，Step4:否則Step3:由精確線搜索求并令：計算若令轉Step2;如果停.第20頁，共76頁，2022年，5月20日，7點11分，星期一Step5:若令轉step2.Step6:計算Step7:如果令轉step2,否則轉step3.第21頁，共76頁，2022年，5月20日，7點11分，星期一作業：FR共軛梯度法（上機）上機實現FR共軛梯度法并求解Rosenbrock函數，初始點選線搜索分別采用黃金分割法與強Wolfe線搜索，并對比第22頁，共76頁，2022年，5月20日，7點11分，星期一

7、4.4 擬牛頓法第23頁，共76頁，2022年，5月20日，7點11分，星期一基本思想本質上是基于逼近牛頓法的方法牛頓法每次都計算1959年,Davidon提出設想僅用每次迭代中得到的梯度信息來近似海色陣，基于此導致了一類非常成功的擬牛頓法本節介紹Broyden族擬牛頓法：DFP算法和BFGS算法第24頁，共76頁，2022年，5月20日，7點11分，星期一算法原理最速下降法和阻尼牛頓法的迭代公式可統一為：思考：要使上面的算法比最速下降法快，比牛頓法計算簡單，且整體收斂性好，關鍵在于構造矩陣列要求：的選取既能逐步逼近又無需計算二階導數，且具備以下條件：第25頁，共76頁，2022年，5月20日

8、，7點11分，星期一C1：是對稱正定陣C2：由經簡單修正而得：C3：滿足下面的擬牛頓方程（推導如下）設是二次連續可微的，第26頁，共76頁，2022年，5月20日，7點11分，星期一令：則：令：因此：（對二次函數為等式）若非奇異：設想：（擬牛頓方程）這樣就可很好的近似第27頁，共76頁，2022年，5月20日，7點11分，星期一擬牛頓算法Step1:給出Step2:計算Step3:Step4:精確線搜索求Step5:Step6:計算若停；否則轉Step7.Step7:校正使擬牛頓方程成立Step8:轉Step3.第28頁，共76頁，2022年，5月20日，7點11分，星期一DFP校正公式是維待

9、定向量要求：所以：令：得：因此：所以：（DFP校正公式）第29頁，共76頁，2022年，5月20日，7點11分，星期一例6：用DFP算法求解：取解：(1)第30頁，共76頁，2022年，5月20日，7點11分，星期一(2)第31頁，共76頁，2022年，5月20日，7點11分，星期一注:（）DFP算法具有二次終止性（）搜索方向是共軛方向：第32頁，共76頁，2022年，5月20日，7點11分，星期一DFP校正公式的正定繼承性引理2:設為正定陣，且則：為正定陣的充要條件是定理5:在DFP算法中，如果正定，則整個矩陣列都正定第33頁，共76頁，2022年，5月20日，7點11分，星期一DFP算法的

10、二次終止性推論:在上面定理條件下：（1）DFP算法至多經過次迭代就可得到極小點，即存在有：（2）若則第34頁，共76頁，2022年，5月20日，7點11分，星期一BFGS校正公式(稱為關于的BFGS校正公式或互補DFP公式)由上式可得：第35頁，共76頁，2022年，5月20日，7點11分，星期一對稱秩一校正公式要求：要求Hesse逆近似也是對稱的，即：取：因此：第36頁，共76頁，2022年，5月20日，7點11分，星期一注:（1）通常不能保證（2）分母可能取零,修正公式不再有意義的正定性（3）逼近程度高，近來用于信賴域算法，取得了很好的效果第37頁，共76頁，2022年，5月20日，7點1

11、1分，星期一Broyden族取注：得DFP校正注：得BFGS校正得對稱秩一校正其中：第38頁，共76頁，2022年，5月20日，7點11分，星期一Broyden族算法性質定理6:設在上連續可微，給定在精確線搜索下，由Broyden族算法產生的點列與參數無關結論：可將DFP算法的性質推廣到整個Broyden族第39頁，共76頁，2022年，5月20日，7點11分，星期一作業(1)用FR共軛梯度法求解：(2)用DFP算法求解：第40頁，共76頁，2022年，5月20日，7點11分，星期一第 五 章無約束最優化方法第41頁，共76頁，2022年，5月20日，7點11分，星期一第五章 無約束最優化 （

12、f） min f(x) f : RnR 5.1 最優性條件 設 f 連續可微 必要條件：若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) ) 精確一維搜索 最 速 下降法：梯度方向函數值變化最快的方向第42頁，共76頁，2022年，5月20日，7點11分，星期一第五章 無約束最優化5.2 最速下降法（續）x(1), 0, k=1| f(x(k)

13、) |0得 x(k+1)=x(k)+kd(k)k=k+1第43頁，共76頁，2022年，5月20日，7點11分，星期一第五章 無約束最優化5.2 最速下降法（續）特點：全局收斂，線性收斂，易產生扭擺現象而造成早停。 （當x(k)距最優點較遠時，速度快，而接近最優點時，速度下降）原因：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法： 設f(x)二階可微，取f(x)在x(k)點附近的二階

14、Taylor近似函數： qk(x)=f(x(k)+ Tf(x(k)(x-x(k) +12 (x-x(k)T2f(x(k) (x-x(k) 求駐點： qk(x)= f(x(k)+ 2f(x(k) (x-x(k)=0第44頁，共76頁，2022年，5月20日，7點11分，星期一第五章 無約束最優化Newton法： （續） 當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)x(1), 0, k=12f(x(k) S= -f(x(k) 得

15、s(k) , x(k+1)=x(k)+s(k)| s(k) |0 使 2f(x(k) + I 正定， 盡量小。特點：全局二階收斂。第49頁，共76頁，2022年，5月20日，7點11分，星期一第五章 無約束最優化5.4 共軛梯度法一、共軛梯度法的方向： 設f(x)=(1/2)xTGx+bTx+c Gnn對稱正定，b Rn,從最速下降方向開始，構造一組共軛方向：設初始點x(1),取d(1)= -f(x(1) (最速下降方向) 設k1,已得到k個相互共軛的方向d(1),d(2), ,d(k),以及，由x(1)開始依次沿上述方向精確一維搜索得到點x(2), ，x(k),x(k+1).即有下式： x(

16、i+1)=x(i)+id(i) , i=1,2, ,k 精確一維搜索保證方向導數為0： fT(x(i+1)d(i)=0, i=1,2, ,k 在x(i+1)點構造新方向d(k+1)為-f(x(k+1) 與d(1),d(2), ,d(k)的組合：第50頁，共76頁，2022年，5月20日，7點11分，星期一第五章 無約束最優化5.4 共軛梯度法一、共軛梯度法的方向： （續）使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

17、) =G(x(j+1)-x(j)=jGd(j) . 根據式，有 d(i)T y(j) = j d(i)T G d(j)=0 , ij 根據，有 d(k+1) T y(j) = j d(k+1)T G d(j)=0 , j= 1,2, ,k 這里的j應為i第51頁，共76頁，2022年，5月20日，7點11分，星期一第五章 無約束最優化5.4 共軛梯度法一、共軛梯度法的方向： （續） jk, ij 有 f(x(j+1)T d(i)=0 由式 由式 f(x(j+1)T f(x(i)=0 i0d(1)=- f(x(1),k=1k=k+1k=1| f(x(k)|0得 k x(k+1)=x(k)+k d

18、(k) k=n?x(1)=x(n+1)d(1)=- f(x(1),k=1求 kd(k+1)=- f(x(k+1)+ kd(k)yNyN重新開始第55頁，共76頁，2022年，5月20日，7點11分，星期一第五章 無約束最優化5.4 共軛梯度法三、算法特點： 1、全局收斂（下降算法）；線性收斂； 2、每步迭代只需存儲若干向量（適用于大規模問題）； 3、有二次終結性（對于正定二次函數，至多n次迭代可達opt.） 注：對不同的 k公式，對于正定二次函數是相等的，對非正定二次函數，有不同的效果，經驗上PRP效果較好。第56頁，共76頁，2022年，5月20日，7點11分，星期一第五章 無約束最優化5.

19、5 變尺度法一、變尺度法的基本思路： (f)min f(x), f: R n R1、基本思想： 用對稱正定矩陣H(k)近似2f(x(k), 而H(k)的產生從給定H(1)開始逐步修整得到。2、算法框圖：x(1),H(1)對稱0, k=1d(k)=-H(k) f(x(k)一維搜索得kx(k+1)=x(k)+ k d(k)|x(k+1)-x(k)|0那么DFP法產生的 對稱正定。注：下列各情況下有sTy0： 1 f(x)為正定二次函數； 2 精確一維搜索時； 3 前章介紹的不精確一維搜索時。可以證明： DFP法在精確一維搜索前提下，超線性收斂。2、BFGS法 若把前面的推導，平行地用在y=Bs公式

20、上，可得到第64頁，共76頁，2022年，5月20日，7點11分，星期一第五章 5.5 變尺度法二、2、BFGS法（續）用此公式求方向時，需用到矩陣求逆或解方程： d= -B-1 f(x) 或 Bd= - f(x)由于每次只有秩2的變換，這里的計算量仍可以降下來。為了得到H-公式，可對上面 求逆（推導得）：BFGS法有變尺度法的全部優點，并且在一定條件下可以證明在BFGS法中使用前文中介紹的不精確一維搜索有全局收斂性。 第65頁，共76頁，2022年，5月20日，7點11分，星期一第五章 5.5 變尺度法三、Broyden族 當在秩2公式中，、 任意選取時可得到不同的公式，經過理論推導，可得到

21、下列結果：第66頁，共76頁，2022年，5月20日，7點11分，星期一第五章 5.5 變尺度法三、Broyden族（續）第67頁，共76頁，2022年，5月20日，7點11分，星期一第五章 無約束最優化 5.6 直接算法 min f(x)一、單純形法及可變多面體算法1、單純形法基本思路： 設 x(0),x(1), x(n)是R n中n+1個點構成的一個當前的單純形。 比較各點的函數值得到：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點外，其他各

22、點的形心：去掉x max，加入x(n+1)得到新的單純形。重復上述過程。第68頁，共76頁，2022年，5月20日，7點11分，星期一第五章 5.6 直接算法一、1、單純形法基本思路： （續）幾點注意： 當x(n+1)又是新單純形的最大值點時，取次大值點進行反射； 若某一個點x出現在連續m個單純形中的時候，取各點與x連線的中點（n個）與x點構成新的單純形，繼續進行。經驗上取 m 1.65n+0.05n2 例如：n=2時，可取m 1.65 2+0.05 4 =3.5 可取 m=4.12345789106111213第69頁，共76頁，2022年，5月20日，7點11分，星期一第五章 5.6 直接

23、算法一、1、單純形法基本思路： （續） 優點：不需求導數，不需要一維搜索。 缺點：無法加速，收斂慢，效果差。2、改進單純形法： （可變多面體算法） 設第k步迭代得到n+1個點： x(0),x(1), x(n) ，得到x max,x min及 通過下列4步操作選新迭代點： 1 反射： 取反射系數 0,(單純形法中 =1) 2 擴展：給定擴展系數 1,計算。（加速）第70頁，共76頁，2022年，5月20日，7點11分，星期一第五章 5.6 直接算法一、 2、改進單純形法： （續） 若f(y(1) f(y(2), 那么y(2)取代x max; 否則， y(1)取代x max 。若maxf(x(i)

24、| 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 ), 重新取各點，使 x(i)= x min +1 2(x(i) - x min ) 得到新單純形。經驗上：=1,0.40.6, 2.33.0 . 有人建議:=1, =0.5， =2 。算法停機準則取：第71頁，共76頁，2022年，5月20日，7點11分，星期一第五章 5.6 直接算法二、模式搜索法： Hooke & Jeeves 19611、基本思想與主要過程： 利用兩類移動（探測性移動和模式性移動）進行一步迭代： 探測性移動的目的：探求一個沿各坐標方向的新點并得到 一 個“有前途”的方向； 模式性移動的目的：沿上述“有前途”方向加速移動。主要過程：第k步迭代，設已得到x(k) 1探測性移動： 給定步長k ，設通過模式性移動得到y(0), 依次沿各坐標方向e(i)=(0, ,