數(shù)學(xué)最優(yōu)化方法第四章課件

第四章

無約束最優(yōu)化方法第四章無約束最優(yōu)化方法1§

4.1最速下降法§4.1最速下降法2問題提出問題：在點處，沿什么方向下降最快?分析：考查：顯然當(dāng)時，取極小值．因此：結(jié)論：負(fù)梯度方向使下降最快，亦即最速下降方向．問題提出問題：在點處，沿什么方向下降最快?分析：考查：顯然當(dāng)3最速下降法算法Step1:給出Step2:計算如果停．Step3:計算下降方向Step4:計算步長因子Step5:令轉(zhuǎn)步２.最速下降法算法Step1:給出Step2:計算如果停．Ste4分析：設(shè)是正定二次函數(shù),由精確的線搜索確定的特別當(dāng)：分析：設(shè)是正定二次函數(shù),由精確的線搜索確定的特別當(dāng)：5例1：用最速下降法求解：解：例1：用最速下降法求解：解：6分析：(1)因此：最速下降法是整體收斂的，且是線性收斂的．(2)兩個相鄰的搜索方向是正交的．分析：(1)因此：最速下降法是整體收斂的，且是線性收斂的．(7[數(shù)學(xué)]最優(yōu)化方法第四章課件8收斂性分析定理1:設(shè)在上存在且一致連續(xù)，則最速下降法產(chǎn)生的序列滿足或者對某個有或者證明：對于最速下降法，由以上定理立得．收斂性分析定理1:設(shè)在上存在且一致連續(xù)，則最速下降法產(chǎn)生的序9收斂性分析定理2:設(shè)二次連續(xù)可微，且其中是個正常數(shù)，對任何給定的初始點最速下降算法或有限終止，或者或者證明：用以上的結(jié)論：收斂性分析定理2:設(shè)二次連續(xù)可微，且其中是個正常數(shù)，對任何給10最速下降法優(yōu)點(1)程序設(shè)計簡單，計算量小，存儲量小，對初始點沒有特別要求．(2)有著很好的整體收斂性，即使對一般的目標(biāo)函數(shù)，它也整體收斂．最速下降法優(yōu)點(1)程序設(shè)計簡單，計算量小，存儲量小，對初始11最速下降法缺點(1)最速下降法是線性收斂的，并且有時是很慢的線性收斂．原因：①僅反映在處的局部性質(zhì)．②相繼兩次迭代中搜索方向是正交的．最速下降法缺點(1)最速下降法是線性收斂的，并且有時是很慢的12小結(jié)(1)最速下降法是基本算法之一，而非有效的實用算法．最速下降法的本質(zhì)是用線性函數(shù)來近似目標(biāo)函數(shù)，要想得到快速算法，需要考慮對目標(biāo)函數(shù)的高階逼近．小結(jié)(1)最速下降法是基本算法之一，而非有效的實用算法．最速13§

4.2牛頓法§4.2牛頓法14基本思想利用目標(biāo)函數(shù)在點處的二階Taylor展開式去近似目標(biāo)函數(shù)，用二次函數(shù)的極小點去逼近目標(biāo)函數(shù)的極小點．基本思想利用目標(biāo)函數(shù)在點處的二階Taylor展開式去近似目標(biāo)15算法構(gòu)造問題：設(shè)二階連續(xù)可微，海色陣正定．如何從因為正定，則有唯一極小點，用這個極小點作為算法構(gòu)造問題：設(shè)二階連續(xù)可微，海色陣正定．如何從因為正定，則16所以要求：即：因此：這就是牛頓法迭代公式．注：這里所以要求：即：因此：這就是牛頓法迭代公式．注：這里17牛頓法算法Step1:給出Step2:計算如果停．Step3:否則計算Step4:令轉(zhuǎn)步２.并且求解方程得出牛頓法算法Step1:給出Step2:計算如果停．Step318例1：用牛頓法求解：解：例1：用牛頓法求解：解：19牛頓法收斂定理定理1:設(shè)二次連續(xù)可微，是的局部極小點，正定．假定的海色陣滿足Lipschitz條件，即存在使得對于所有有：其中是海色陣的元素．則當(dāng)充分靠近時，對于一切牛頓迭代有意義，迭代序列收斂到并且具有二階收斂速度．牛頓法收斂定理定理1:設(shè)二次連續(xù)可微，是的局部極小點，正定．20牛頓法優(yōu)點(1)(2)對正定二次函數(shù)，迭代一次就可以得到極小點．如果正定且初始點選取合適，算法二階收斂．牛頓法優(yōu)點(1)(2)對正定二次函數(shù)，迭代一次就可以得到極小21牛頓法缺點(1)(2)對多數(shù)問題算法不是整體收斂的．每次都需要計算計算量大．(3)每次都需要解方程組有時奇異或病態(tài)的，無法確定或不是下降方向．(4)收斂到鞍點或極大點的可能性并不小．牛頓法缺點(1)(2)對多數(shù)問題算法不是整體收斂的．每次都需22阻尼牛頓法算法Step1:給出Step2:計算如果停．Step3:否則計算Step4:沿并且求解方程得出進(jìn)行線搜索，得出Step5:令轉(zhuǎn)Step2.阻尼牛頓法算法Step1:給出Step2:計算如果停．Ste23阻尼牛頓法收斂定理定理2:設(shè)二階連續(xù)可微，又設(shè)對任意的存在常數(shù)使得在上滿足：則在精確線搜索條件下，阻尼牛頓法產(chǎn)生的點列滿足：(1)當(dāng)是有限點列時，其最后一個點為的唯一極小點．(2)當(dāng)是無限點列時，收斂到的唯一極小點．阻尼牛頓法收斂定理定理2:設(shè)二階連續(xù)可微，又設(shè)對任意的存在常24阻尼牛頓法收斂定理定理3:設(shè)二階連續(xù)可微，又設(shè)對任意的存在常數(shù)使得在上滿足：則在Wolfe不精確線搜索條件下，阻尼牛頓法產(chǎn)生的點列滿足：且收斂到的唯一極小點．阻尼牛頓法收斂定理定理3:設(shè)二階連續(xù)可微，又設(shè)對任意的存在常25例2：用阻尼牛頓法求解：解：顯然不是正定的，但：于是，沿方向進(jìn)行線搜索，得其極小點從而迭代不能繼續(xù)下去．例2：用阻尼牛頓法求解：解：顯然不是正定的，但：于是，沿方向26帶保護(hù)的牛頓法算法給出Step1:若為奇異的，轉(zhuǎn)Step8，否則，Step2:令Step3:若為奇異的，轉(zhuǎn)Step8，否則，則轉(zhuǎn)Step8，否則，Step4:若則轉(zhuǎn)Step9，否則，Step5:沿方向進(jìn)行線搜索，求出并令帶保護(hù)的牛頓法算法給出Step1:若為奇異的，轉(zhuǎn)Step8，27Step6:若停；Step7:令轉(zhuǎn)Step1；Step8:令轉(zhuǎn)Step5；Step9:令轉(zhuǎn)Step5.Step6:若停；Step7:令轉(zhuǎn)Step1；Step8:令28例3：用帶保護(hù)的牛頓法求解：解：顯然不是正定的，但：于是，因為，故令，沿進(jìn)行線搜索得：例3：用帶保護(hù)的牛頓法求解：解：顯然不是正定的，但：于是，因29第二次迭代：而：使故令沿進(jìn)行線搜索，得出于是:此時:第二次迭代：而：使故令沿進(jìn)行線搜索，得出于是:此時:30Gill-Murray穩(wěn)定牛頓法當(dāng)正定時，總有Cholesky分解：當(dāng)不是正定時，Gill-Murray(1974)提出了強(qiáng)迫正定的修改Cholesky分解，使得：其中是對角陣．然后解：Gill-Murray穩(wěn)定牛頓法當(dāng)正定時，總有Cholesk31問題1:如何建立有效的算法？從二次模型到一般模型問題2:什么樣的算法有效呢？二次終止性問題1:如何建立有效的算法？從二次模型到一般模型問題2:什么32§

4.3共軛方向法與共軛梯度法§4.3共軛方向法33算法特點（１）建立在二次模型上，具有二次終止性．（２）有效的算法，克服了最速下降法的慢收斂性，又避免了牛頓法的計算量大和局部收性的缺點．（３）算法簡單，易于編程，需存儲空間小等優(yōu)點，是求解大規(guī)模問題的主要方法．算法特點（１）建立在二次模型上，具有二次終止性．（２）有效的34共軛方向及其性質(zhì)定義1:設(shè)是中任一組非零向量，如果：則稱是關(guān)于共軛的．注：若則是正交的，因此共軛是正交的推廣．共軛方向及其性質(zhì)定義1:設(shè)是中任一組非零向量，如果：則稱是關(guān)35定理1:設(shè)為階正定陣，非零向量組關(guān)于共軛，則必線性無關(guān)．推論1:設(shè)為階正定陣，非零向量組關(guān)于共軛，則向量構(gòu)成的一組基．推論2:設(shè)為階正定陣，非零向量組關(guān)于共軛，若向量與關(guān)于共軛，則定理1:設(shè)為階正定陣，非零向量組關(guān)于共軛，則必線性無關(guān)．推論36共軛方向法算法Step1:給出計算和初始下降方向Step2:如果停止迭代．Step3:計算使得Step4:采用某種共軛方向法計算使得：Step5:令轉(zhuǎn)Step2.共軛方向法算法Step1:給出計算和初始下降方向Step2:37共軛方向法基本定理定義2:設(shè)維向量組線性無關(guān)，向量集合為與生成的維超平面．共軛方向法基本定理定義2:設(shè)維向量組線性無關(guān)，向量集合為與生38引理1:設(shè)是連續(xù)可微的嚴(yán)格凸函數(shù)，維向量組線性無關(guān)，則：是在上唯一極小點的充要條件是：引理1:設(shè)是連續(xù)可微的嚴(yán)格凸函數(shù)，維向量組線性無關(guān)，則：是在39證：構(gòu)造：分析：是(1)維嚴(yán)格凸函數(shù)．(2)是在上的極小點的充要條件是是在上的極小點．證：構(gòu)造：分析：是(1)維嚴(yán)格凸函數(shù)．(2)是在上的極小點的40定理2:設(shè)為階正定陣，向量組關(guān)于共軛，對正定二次函數(shù)由任意開始，依次進(jìn)行次精確線搜索：則：（１）（２）是在上的極小點．推論:當(dāng)時，為正定二次函數(shù)在上的極小點．定理2:設(shè)為階正定陣，向量組關(guān)于共軛，對正定二次函數(shù)由任意開41共軛梯度法記：左乘并使得：（Hestenes-Stiefel公式）?。汗曹椞荻确ㄓ洠鹤蟪瞬⑹沟茫海℉estenes-Stiefel42共軛梯度法基本性質(zhì)定理3:對于正定二次函數(shù)，采用精確線搜索的共軛梯度法在步后終止，且對成立下列關(guān)系式：（共軛性）（正交性）（下降條件）共軛梯度法基本性質(zhì)定理3:對于正定二次函數(shù)，采用精確線搜索的43系數(shù)的其他形式（１）FR公式（1964）（2）PRP公式（1969）系數(shù)的其他形式（１）FR公式（1964）（2）PRP公式（144FR共軛梯度法算法Step1:給出Step2:計算如果停．Step3:Step4:由精確線搜索求Step5:轉(zhuǎn)Step2.FR共軛梯度法算法Step1:給出Step2:計算如果停．S45例4：用FR共軛梯度法求解：解：化成形式(1)例4：用FR共軛梯度法求解：解：化成形式(1)46(2)(2)47[數(shù)學(xué)]最優(yōu)化方法第四章課件48例5：用FR共軛梯度法求解：解：化成形式(1)例5：用FR共軛梯度法求解：解：化成形式(1)49(2)(2)50FR共軛梯度法收斂定理定理4:假定在有界水平集上連續(xù)可微，且有下界，那么采用精確線搜索下的FR共軛梯度法產(chǎn)生的點列至少有一個聚點是駐點，即：(1)當(dāng)是有窮點列時，其最后一個點是的駐點．(2)當(dāng)是無窮點列時，它必有聚點，且任一聚點都是的駐點．FR共軛梯度法收斂定理定理4:假定在有界水平集上連續(xù)可微，且51再開始FR共軛梯度法算法Step1:給出Step2:計算如果停，Step4:否則Step3:由精確線搜索求并令：計算若令轉(zhuǎn)Step2;如果停.再開始FR共軛梯度法算法Step1:給出Step2:計算如果52Step5:若令轉(zhuǎn)step2.Step6:計算Step7:如果令轉(zhuǎn)step2,否則轉(zhuǎn)step3.Step5:若令轉(zhuǎn)step2.Step6:計算Step7:如53作業(yè)：FR共軛梯度法（上機(jī)）上機(jī)實現(xiàn)FR共軛梯度法．并求解Rosenbrock函數(shù)，初始點選線搜索分別采用黃金分割法與強(qiáng)Wolfe線搜索，并對比．作業(yè)：FR共軛梯度法（上機(jī)）上機(jī)實現(xiàn)FR共軛梯度法．并求解R54§

4.4擬牛頓法§4.4擬牛頓法55基本思想本質(zhì)上是基于逼近牛頓法的方法．牛頓法每次都計算1959年,Davidon提出設(shè)想僅用每次迭代中得到的梯度信息來近似海色陣，基于此導(dǎo)致了一類非常成功的擬牛頓法．本節(jié)介紹Broyden族擬牛頓法：DFP算法和BFGS算法．基本思想本質(zhì)上是基于逼近牛頓法的方法．牛頓法每次都計算19556算法原理最速下降法和阻尼牛頓法的迭代公式可統(tǒng)一為：思考：要使上面的算法比最速下降法快，比牛頓法計算簡單，且整體收斂性好，關(guān)鍵在于構(gòu)造矩陣列要求：的選取既能逐步逼近又無需計算二階導(dǎo)數(shù)，且具備以下條件：算法原理最速下降法和阻尼牛頓法的迭代公式可統(tǒng)一為：思考：要使57C1：是對稱正定陣．C2：由經(jīng)簡單修正而得：C3：滿足下面的擬牛頓方程．（推導(dǎo)如下）設(shè)是二次連續(xù)可微的，C1：是對稱正定陣．C2：由經(jīng)簡單修正而得：C3：滿足下面的58令：則：令：因此：（對二次函數(shù)為等式）若非奇異：設(shè)想：（擬牛頓方程）這樣就可很好的近似令：則：令：因此：（對二次函數(shù)為等式）若非奇異：設(shè)想：（擬牛59擬牛頓算法Step1:給出Step2:計算Step3:Step4:精確線搜索求Step5:Step6:計算若停；否則轉(zhuǎn)Step7.Step7:校正使擬牛頓方程成立．Step8:轉(zhuǎn)Step3.擬牛頓算法Step1:給出Step2:計算Step3:Ste60DFP校正公式是維待定向量．要求：所以：令：得：因此：所以：（DFP校正公式）DFP校正公式是維待定向量．要求：所以：令：得：因此：所以：61例6：用DFP算法求解：取解：(1)例6：用DFP算法求解：取解：(1)62(2)(2)63注:（１）DFP算法具有二次終止性．（２）搜索方向是共軛方向：注:（１）DFP算法具有二次終止性．（２）搜索方向是共軛方向64DFP校正公式的正定繼承性引理2:設(shè)為正定陣，且則：為正定陣的充要條件是定理5:在DFP算法中，如果正定，則整個矩陣列都正定．DFP校正公式的正定繼承性引理2:設(shè)為正定陣，且則：為正定65DFP算法的二次終止性推論:在上面定理條件下：（1）DFP算法至多經(jīng)過次迭代就可得到極小點，即存在有：（2）若則DFP算法的二次終止性推論:在上面定理條件下：（1）DFP66BFGS校正公式(稱為關(guān)于的BFGS校正公式或互補(bǔ)DFP公式)由上式可得：BFGS校正公式(稱為關(guān)于的BFGS校正公式或互補(bǔ)DFP公式67對稱秩一校正公式要求：要求Hesse逆近似也是對稱的，即：?。阂虼耍簩ΨQ秩一校正公式要求：要求Hesse逆近似也是對稱的，即：取68注:（1）通常不能保證（2）分母可能取零,修正公式不再有意義．的正定性．（3）逼近程度高，近來用于信賴域算法，取得了很好的效果．注:（1）通常不能保證（2）分母可能取零,修正公式不再有意義69Broyden族取注：得DFP校正．注：得BFGS校正．得對稱秩一校正．其中：Broyden族取注：得DFP校正．注：得BFGS校正．得對70Broyden族算法性質(zhì)定理6:設(shè)在上連續(xù)可微，給定在精確線搜索下，由Broyden族算法產(chǎn)生的點列與參數(shù)無關(guān)．結(jié)論：可將DFP算法的性質(zhì)推廣到整個Broyden族Broyden族算法性質(zhì)定理6:設(shè)在上連續(xù)可微，給定在精確線71作業(yè)(1)用FR共軛梯度法求解：(2)用DFP算法求解：作業(yè)(1)用FR共軛梯度法求解：(2)用DFP算法求解：72第四章

無約束最優(yōu)化方法第四章無約束最優(yōu)化方法73§

4.1最速下降法§4.1最速下降法74問題提出問題：在點處，沿什么方向下降最快?分析：考查：顯然當(dāng)時，取極小值．因此：結(jié)論：負(fù)梯度方向使下降最快，亦即最速下降方向．問題提出問題：在點處，沿什么方向下降最快?分析：考查：顯然當(dāng)75最速下降法算法Step1:給出Step2:計算如果停．Step3:計算下降方向Step4:計算步長因子Step5:令轉(zhuǎn)步２.最速下降法算法Step1:給出Step2:計算如果停．Ste76分析：設(shè)是正定二次函數(shù),由精確的線搜索確定的特別當(dāng)：分析：設(shè)是正定二次函數(shù),由精確的線搜索確定的特別當(dāng)：77例1：用最速下降法求解：解：例1：用最速下降法求解：解：78分析：(1)因此：最速下降法是整體收斂的，且是線性收斂的．(2)兩個相鄰的搜索方向是正交的．分析：(1)因此：最速下降法是整體收斂的，且是線性收斂的．(79[數(shù)學(xué)]最優(yōu)化方法第四章課件80收斂性分析定理1:設(shè)在上存在且一致連續(xù)，則最速下降法產(chǎn)生的序列滿足或者對某個有或者證明：對于最速下降法，由以上定理立得．收斂性分析定理1:設(shè)在上存在且一致連續(xù)，則最速下降法產(chǎn)生的序81收斂性分析定理2:設(shè)二次連續(xù)可微，且其中是個正常數(shù)，對任何給定的初始點最速下降算法或有限終止，或者或者證明：用以上的結(jié)論：收斂性分析定理2:設(shè)二次連續(xù)可微，且其中是個正常數(shù)，對任何給82最速下降法優(yōu)點(1)程序設(shè)計簡單，計算量小，存儲量小，對初始點沒有特別要求．(2)有著很好的整體收斂性，即使對一般的目標(biāo)函數(shù)，它也整體收斂．最速下降法優(yōu)點(1)程序設(shè)計簡單，計算量小，存儲量小，對初始83最速下降法缺點(1)最速下降法是線性收斂的，并且有時是很慢的線性收斂．原因：①僅反映在處的局部性質(zhì)．②相繼兩次迭代中搜索方向是正交的．最速下降法缺點(1)最速下降法是線性收斂的，并且有時是很慢的84小結(jié)(1)最速下降法是基本算法之一，而非有效的實用算法．最速下降法的本質(zhì)是用線性函數(shù)來近似目標(biāo)函數(shù)，要想得到快速算法，需要考慮對目標(biāo)函數(shù)的高階逼近．小結(jié)(1)最速下降法是基本算法之一，而非有效的實用算法．最速85§

4.2牛頓法§4.2牛頓法86基本思想利用目標(biāo)函數(shù)在點處的二階Taylor展開式去近似目標(biāo)函數(shù)，用二次函數(shù)的極小點去逼近目標(biāo)函數(shù)的極小點．基本思想利用目標(biāo)函數(shù)在點處的二階Taylor展開式去近似目標(biāo)87算法構(gòu)造問題：設(shè)二階連續(xù)可微，海色陣正定．如何從因為正定，則有唯一極小點，用這個極小點作為算法構(gòu)造問題：設(shè)二階連續(xù)可微，海色陣正定．如何從因為正定，則88所以要求：即：因此：這就是牛頓法迭代公式．注：這里所以要求：即：因此：這就是牛頓法迭代公式．注：這里89牛頓法算法Step1:給出Step2:計算如果停．Step3:否則計算Step4:令轉(zhuǎn)步２.并且求解方程得出牛頓法算法Step1:給出Step2:計算如果停．Step390例1：用牛頓法求解：解：例1：用牛頓法求解：解：91牛頓法收斂定理定理1:設(shè)二次連續(xù)可微，是的局部極小點，正定．假定的海色陣滿足Lipschitz條件，即存在使得對于所有有：其中是海色陣的元素．則當(dāng)充分靠近時，對于一切牛頓迭代有意義，迭代序列收斂到并且具有二階收斂速度．牛頓法收斂定理定理1:設(shè)二次連續(xù)可微，是的局部極小點，正定．92牛頓法優(yōu)點(1)(2)對正定二次函數(shù)，迭代一次就可以得到極小點．如果正定且初始點選取合適，算法二階收斂．牛頓法優(yōu)點(1)(2)對正定二次函數(shù)，迭代一次就可以得到極小93牛頓法缺點(1)(2)對多數(shù)問題算法不是整體收斂的．每次都需要計算計算量大．(3)每次都需要解方程組有時奇異或病態(tài)的，無法確定或不是下降方向．(4)收斂到鞍點或極大點的可能性并不?。ｎD法缺點(1)(2)對多數(shù)問題算法不是整體收斂的．每次都需94阻尼牛頓法算法Step1:給出Step2:計算如果停．Step3:否則計算Step4:沿并且求解方程得出進(jìn)行線搜索，得出Step5:令轉(zhuǎn)Step2.阻尼牛頓法算法Step1:給出Step2:計算如果停．Ste95阻尼牛頓法收斂定理定理2:設(shè)二階連續(xù)可微，又設(shè)對任意的存在常數(shù)使得在上滿足：則在精確線搜索條件下，阻尼牛頓法產(chǎn)生的點列滿足：(1)當(dāng)是有限點列時，其最后一個點為的唯一極小點．(2)當(dāng)是無限點列時，收斂到的唯一極小點．阻尼牛頓法收斂定理定理2:設(shè)二階連續(xù)可微，又設(shè)對任意的存在常96阻尼牛頓法收斂定理定理3:設(shè)二階連續(xù)可微，又設(shè)對任意的存在常數(shù)使得在上滿足：則在Wolfe不精確線搜索條件下，阻尼牛頓法產(chǎn)生的點列滿足：且收斂到的唯一極小點．阻尼牛頓法收斂定理定理3:設(shè)二階連續(xù)可微，又設(shè)對任意的存在常97例2：用阻尼牛頓法求解：解：顯然不是正定的，但：于是，沿方向進(jìn)行線搜索，得其極小點從而迭代不能繼續(xù)下去．例2：用阻尼牛頓法求解：解：顯然不是正定的，但：于是，沿方向98帶保護(hù)的牛頓法算法給出Step1:若為奇異的，轉(zhuǎn)Step8，否則，Step2:令Step3:若為奇異的，轉(zhuǎn)Step8，否則，則轉(zhuǎn)Step8，否則，Step4:若則轉(zhuǎn)Step9，否則，Step5:沿方向進(jìn)行線搜索，求出并令帶保護(hù)的牛頓法算法給出Step1:若為奇異的，轉(zhuǎn)Step8，99Step6:若停；Step7:令轉(zhuǎn)Step1；Step8:令轉(zhuǎn)Step5；Step9:令轉(zhuǎn)Step5.Step6:若停；Step7:令轉(zhuǎn)Step1；Step8:令100例3：用帶保護(hù)的牛頓法求解：解：顯然不是正定的，但：于是，因為，故令，沿進(jìn)行線搜索得：例3：用帶保護(hù)的牛頓法求解：解：顯然不是正定的，但：于是，因101第二次迭代：而：使故令沿進(jìn)行線搜索，得出于是:此時:第二次迭代：而：使故令沿進(jìn)行線搜索，得出于是:此時:102Gill-Murray穩(wěn)定牛頓法當(dāng)正定時，總有Cholesky分解：當(dāng)不是正定時，Gill-Murray(1974)提出了強(qiáng)迫正定的修改Cholesky分解，使得：其中是對角陣．然后解：Gill-Murray穩(wěn)定牛頓法當(dāng)正定時，總有Cholesk103問題1:如何建立有效的算法？從二次模型到一般模型問題2:什么樣的算法有效呢？二次終止性問題1:如何建立有效的算法？從二次模型到一般模型問題2:什么104§

4.3共軛方向法與共軛梯度法§4.3共軛方向法105算法特點（１）建立在二次模型上，具有二次終止性．（２）有效的算法，克服了最速下降法的慢收斂性，又避免了牛頓法的計算量大和局部收性的缺點．（３）算法簡單，易于編程，需存儲空間小等優(yōu)點，是求解大規(guī)模問題的主要方法．算法特點（１）建立在二次模型上，具有二次終止性．（２）有效的106共軛方向及其性質(zhì)定義1:設(shè)是中任一組非零向量，如果：則稱是關(guān)于共軛的．注：若則是正交的，因此共軛是正交的推廣．共軛方向及其性質(zhì)定義1:設(shè)是中任一組非零向量，如果：則稱是關(guān)107定理1:設(shè)為階正定陣，非零向量組關(guān)于共軛，則必線性無關(guān)．推論1:設(shè)為階正定陣，非零向量組關(guān)于共軛，則向量構(gòu)成的一組基．推論2:設(shè)為階正定陣，非零向量組關(guān)于共軛，若向量與關(guān)于共軛，則定理1:設(shè)為階正定陣，非零向量組關(guān)于共軛，則必線性無關(guān)．推論108共軛方向法算法Step1:給出計算和初始下降方向Step2:如果停止迭代．Step3:計算使得Step4:采用某種共軛方向法計算使得：Step5:令轉(zhuǎn)Step2.共軛方向法算法Step1:給出計算和初始下降方向Step2:109共軛方向法基本定理定義2:設(shè)維向量組線性無關(guān)，向量集合為與生成的維超平面．共軛方向法基本定理定義2:設(shè)維向量組線性無關(guān)，向量集合為與生110引理1:設(shè)是連續(xù)可微的嚴(yán)格凸函數(shù)，維向量組線性無關(guān)，則：是在上唯一極小點的充要條件是：引理1:設(shè)是連續(xù)可微的嚴(yán)格凸函數(shù)，維向量組線性無關(guān)，則：是在111證：構(gòu)造：分析：是(1)維嚴(yán)格凸函數(shù)．(2)是在上的極小點的充要條件是是在上的極小點．證：構(gòu)造：分析：是(1)維嚴(yán)格凸函數(shù)．(2)是在上的極小點的112定理2:設(shè)為階正定陣，向量組關(guān)于共軛，對正定二次函數(shù)由任意開始，依次進(jìn)行次精確線搜索：則：（１）（２）是在上的極小點．推論:當(dāng)時，為正定二次函數(shù)在上的極小點．定理2:設(shè)為階正定陣，向量組關(guān)于共軛，對正定二次函數(shù)由任意開113共軛梯度法記：左乘并使得：（Hestenes-Stiefel公式）?。汗曹椞荻确ㄓ洠鹤蟪瞬⑹沟茫海℉estenes-Stiefel114共軛梯度法基本性質(zhì)定理3:對于正定二次函數(shù)，采用精確線搜索的共軛梯度法在步后終止，且對成立下列關(guān)系式：（共軛性）（正交性）（下降條件）共軛梯度法基本性質(zhì)定理3:對于正定二次函數(shù)，采用精確線搜索的115系數(shù)的其他形式（１）FR公式（1964）（2）PRP公式（1969）系數(shù)的其他形式（１）FR公式（1964）（2）PRP公式（1116FR共軛梯度法算法Step1:給出Step2:計算如果停．Step3:Step4:由精確線搜索求Step5:轉(zhuǎn)Step2.FR共軛梯度法算法Step1:給出Step2:計算如果停．S117例4：用FR共軛梯度法求解：解：化成形式(1)例4：用FR共軛梯度法求解：解：化成形式(1)118(2)(2)119[數(shù)學(xué)]最優(yōu)化方法第四章課件120例5：用FR共軛梯度法求解：解：化成形式(1)例5：用FR共軛梯度法求解：解：化成形式(1)121(2)(2)122FR共軛梯度法收斂定理定理4:假定在有界水平集上連續(xù)可微，且有下界，那么采用精確線搜索下的FR共軛梯度法產(chǎn)生的點列至少有一個聚點是駐點，即：(1)當(dāng)是有窮點列時，其最后一個點是的駐點．(2)當(dāng)是無窮點列時，它必有聚點，且任一聚點都是的駐點．FR共軛梯度法收斂定理定理4:假定在有界水平集上連續(xù)可微，且123再開始FR共軛梯度法算法Step1:給出Step2:計算如果停，Step4:否則Step3:由精確線搜索求并令：計算若令轉(zhuǎn)Step2;如果停.再開始FR共軛梯度法算法Step1:給出Step2:計算如果124Step5:若令轉(zhuǎn)step2.Step6:計算Step7:如果令轉(zhuǎn)step2,否則轉(zhuǎn)step3.Step5:若令轉(zhuǎn)step2.Step6:計算Step7:如125作業(yè)：FR共軛梯度法（上機(jī)）上機(jī)實現(xiàn)FR共軛梯度法．并求解Rosenbrock函數(shù)，初始點選線搜索分別采用黃金分割法與強(qiáng)Wolfe線搜索，并對比．作業(yè)：FR共軛梯度法（上機(jī)）上機(jī)實現(xiàn)FR共軛梯度法．并求解R126§

4.4擬牛頓法§4.4擬牛頓法127基本思想本質(zhì)上是基于逼近牛頓法的方法．牛頓法每次都計算1959年,Davidon提出設(shè)想僅用每次迭代中得到的梯度信息來近似海色陣，基于此導(dǎo)致了一類非常成功的擬牛頓法．本節(jié)介紹Broyden族擬牛頓法：DFP算法和BFGS算法．基本思想本質(zhì)上是基于逼近牛頓法的方法．牛頓法每次都計算195128算法原理最速下降法和阻尼牛頓法的迭代公式可統(tǒng)一為：思考：要使上面的算法比最速下降法快，比牛頓法計算簡單，且整體收斂性好，關(guān)鍵在于構(gòu)造矩陣列要求：的選取既能逐步逼近又無需計算二階導(dǎo)數(shù)，且具備以下條件：算法原理最速下降法和