第六章 使用導(dǎo)數(shù)的最優(yōu)化方法

第六章

使用導(dǎo)數(shù)的最優(yōu)化方法§

6.1牛頓法基本思想利用目標(biāo)函數(shù)在點(diǎn)處的二階Taylor展開式去近似目標(biāo)函數(shù)，用二次函數(shù)的極小點(diǎn)去逼近目標(biāo)函數(shù)的極小點(diǎn)．算法構(gòu)造問題：設(shè)二階連續(xù)可微，海色陣正定．如何從因?yàn)檎?，則有唯一極小點(diǎn)，用這個(gè)極小點(diǎn)作為所以要求：即：因此：這就是牛頓法迭代公式．注：牛頓法是一種下降法,這里牛頓法算法Step1:給出Step2:計(jì)算如果停．Step3:否則計(jì)算Step4:令轉(zhuǎn)步２.并且求解方程得出例1：用牛頓法求解：解：牛頓法收斂定理定理1:設(shè)二次連續(xù)可微，是的局部極小點(diǎn)，正定．假定的海色陣滿足Lipschitz條件，即存在使得對(duì)于所有有：其中是海色陣的元素．則當(dāng)充分靠近時(shí)，對(duì)于一切牛頓迭代有意義，迭代序列收斂到并且具有二階收斂速度．牛頓法優(yōu)點(diǎn)(1)(2)具有二次終止性.對(duì)正定二次函數(shù)，迭代一次就可以得到極小點(diǎn).如果正定且初始點(diǎn)選取合適，算法二階收斂．牛頓法缺點(diǎn)(1)(3)可能會(huì)出現(xiàn)在某步迭代時(shí)目標(biāo)函數(shù)值每次都需要計(jì)算計(jì)算量大．(4)每次都需要解方程組有時(shí)奇異或病態(tài)，無(wú)法確定(2)可能不收斂，或收斂到鞍點(diǎn)．反而上升的情形，即阻尼牛頓法算法Step1:給出Step2:計(jì)算如果停．Step3:否則計(jì)算Step4:沿并且求解方程得出進(jìn)行一維搜索，得出Step5:令轉(zhuǎn)Step2.阻尼牛頓法收斂定理定理2:設(shè)二階連續(xù)可微，又設(shè)對(duì)任意的存在常數(shù)使得在上滿足：則在精確一維搜索下，阻尼牛頓法產(chǎn)生的點(diǎn)列滿足：(1)當(dāng)是有限點(diǎn)列時(shí)，其最后一個(gè)點(diǎn)為的唯一極小點(diǎn)．(2)當(dāng)是無(wú)限點(diǎn)列時(shí)，收斂到的唯一極小點(diǎn)．阻尼牛頓法收斂定理定理3:設(shè)二階連續(xù)可微，又設(shè)對(duì)任意的存在常數(shù)使得在上滿足：則在Wolfe不精確一維搜索下，阻尼牛頓法產(chǎn)生的點(diǎn)列滿足：且收斂到的唯一極小點(diǎn)．牛頓法的其他修正方法（1）Goldsetin和Price(1967)的修正方案其思想是將牛頓法與最速下降法相結(jié)合，當(dāng)牛頓方向與負(fù)梯度方向的夾角太大時(shí)(如大于90度)，就用負(fù)梯度方向取代牛頓方向牛頓法的其他修正方法（2）Fiacco和McCormick(1968)的修正方案其思想是當(dāng)海賽矩陣非正定時(shí)，采用負(fù)曲率下降方向，作為搜索方向上式的意思是當(dāng)負(fù)曲率方向與負(fù)梯度方向的夾角小于90度時(shí)，采用負(fù)曲率方向；否則采用與負(fù)曲率方向相反的方向.牛頓法的其他修正方法（3）正則化修正方案§

6.2共軛方向法與共軛梯度法算法目標(biāo)和要求（１）產(chǎn)生的搜索方向是下降方向．（２）不必計(jì)算Hesse矩陣，只計(jì)算目標(biāo)函數(shù)值和梯度值.（３）具有二次終止性.正交方向及其性質(zhì)正交方向及其性質(zhì)建沿兩個(gè)相互正交的方向，進(jìn)行精確一維搜索，即可得到最優(yōu)解正交方向及其性質(zhì)定義1:設(shè)是中任一組非零向量，如果：則稱是一組正交方向.性質(zhì)1:定義2:設(shè)維向量組線性無(wú)關(guān)，向量集合稱為與生成的維線性流形．當(dāng)其維數(shù)為n-1時(shí)，又稱為超平面．線性流形可看成線性子空間從原點(diǎn)的一個(gè)移位．定理1:設(shè)向量組是一組正交方向,對(duì)正定二次函數(shù)由任意開始，依次進(jìn)行次精確一維搜索,得到則：（１）（２）是在線性流行上的極小點(diǎn)．推論:當(dāng)時(shí)，為正定二次函數(shù)在上的極小點(diǎn)．共軛方向及其性質(zhì)定義1:設(shè)是中任一組非零向量，如果：則稱是關(guān)于共軛的．注：若則是正交的，因此共軛是正交的推廣．定理2:設(shè)為階正定陣，非零向量組關(guān)于共軛，則必線性無(wú)關(guān)．推論1:設(shè)為階正定陣，非零向量組關(guān)于共軛，則向量構(gòu)成的一組基．推論2:設(shè)為階正定陣，非零向量組關(guān)于共軛，若向量與關(guān)于共軛，則共軛方向法算法Step1:給出計(jì)算和初始下降方向Step2:如果停止迭代．Step3:計(jì)算使得Step4:采用某種共軛方向法計(jì)算使得：Step5:令轉(zhuǎn)Step2.定理3:設(shè)為階正定陣，向量組關(guān)于共軛，對(duì)正定二次函數(shù)由任意開始，依次進(jìn)行次精確線搜索，得到則：（１）（２）是在上的極小點(diǎn)．推論:當(dāng)時(shí)，為正定二次函數(shù)在上的極小點(diǎn)．共軛方向法基本定理共軛梯度法記：左乘并使得：（Hestenes-Stiefel公式）?。汗曹椞荻确ɑ拘再|(zhì)定理4:對(duì)于正定二次函數(shù)，采用精確一維搜索的共軛梯度法在步后終止，且對(duì)成立下列關(guān)系式：（共軛性）（正交性）（下降性）系數(shù)的其他形式（１）FR公式（1964）（2）PRP公式（1969）FR（或FRP）共軛梯度法算法Step1:給出Step2:計(jì)算如果停．Step3:Step4:解一維搜索Step5:轉(zhuǎn)Step2.或例：用FR共軛梯度法求解：解：化成形式(1)(2)共軛梯度法的下降性和二次終止性定理5設(shè)f(x)具有連續(xù)的一階偏導(dǎo)數(shù)，并設(shè)共軛梯度法的一維搜索是精確的，若則搜索方向dk是xk處的下降方向.定理6若一維搜索是精確的，則共軛梯度法具有二次終止性.FR共軛梯度法收斂定理定理7:假定在有界水平集上連續(xù)可微，且有下界，那么采用精確一維搜索的FR共軛梯度法產(chǎn)生的點(diǎn)列至少有一個(gè)聚點(diǎn)是駐點(diǎn)，即：(1)當(dāng)是有窮點(diǎn)列時(shí)，其最后一個(gè)點(diǎn)是的駐點(diǎn)．(2)當(dāng)是無(wú)窮點(diǎn)列時(shí)，它必有聚點(diǎn)，且任一聚點(diǎn)都是的駐點(diǎn)．對(duì)于正定二次函數(shù)，共軛梯度法至多n步終止。如算法沒有n步終止，說明目標(biāo)函數(shù)不是正定二次函數(shù)或目標(biāo)函數(shù)沒有進(jìn)入一個(gè)正定二次函數(shù)的區(qū)域，此時(shí)共軛方向已沒有意義，因此搜索方向應(yīng)重新開始，即令dn=-gn

.這種每n步重新開始新一輪共軛梯度法的策略，稱為n步重新開始策略。實(shí)際計(jì)算表明，n步重新開始的FR算法要優(yōu)于原FR算法。對(duì)于FRP算法,當(dāng)gk≈gk-1

,有k-1=0;因此dk≈-gk

,即算法自動(dòng)重新開始。試驗(yàn)表明，對(duì)于大規(guī)模問題，F(xiàn)RP算法優(yōu)于FR算法。再開始FR共軛梯