無(wú)約束最優(yōu)化

無(wú)約束最優(yōu)化第1頁(yè)，共18頁(yè)，2023年，2月20日，星期六二、

局部解的最優(yōu)性條件定理4－1（一階必要條件）設(shè)具有連續(xù)的一階偏導(dǎo)數(shù)，若是無(wú)約束問(wèn)題的局部解，則定理4－2（二階必要條件）設(shè)具有連續(xù)的二階偏導(dǎo)數(shù)，若是無(wú)約束問(wèn)題的局部解，則半正定。第2頁(yè)，共18頁(yè)，2023年，2月20日，星期六定理4－3（二階充分條件）設(shè)具有連續(xù)的二階偏導(dǎo)數(shù)，若在處滿足：

正定，則是無(wú)約束問(wèn)題的嚴(yán)格局部解。定義2設(shè)G是階正定對(duì)稱矩陣，稱函數(shù)

為正定二次函數(shù)。

第3頁(yè)，共18頁(yè)，2023年，2月20日，星期六例1證明：若目標(biāo)函數(shù)為正定二次函數(shù)，則相應(yīng)的無(wú)約束問(wèn)題有嚴(yán)格局部解，且此局部解也是全局解。定理4－4設(shè)是連續(xù)可微的凸函數(shù)，則是無(wú)約束問(wèn)題的全局解的充要條件是第4頁(yè)，共18頁(yè)，2023年，2月20日，星期六三、

最速下降法思路：從某一點(diǎn)出發(fā)，以最快的速度到達(dá)最小點(diǎn)，什么方向是函數(shù)下降最快的方向呢？－－－負(fù)梯度方向。步長(zhǎng)：沿負(fù)梯度方向走多遠(yuǎn)？當(dāng)前點(diǎn)，計(jì)算負(fù)梯度，最優(yōu)步長(zhǎng)第5頁(yè)，共18頁(yè)，2023年，2月20日，星期六算法4.1最速下降法（1）取初始點(diǎn)，令（2）若，停止，否則（3）一維搜索，求解問(wèn)題得令（4）令轉(zhuǎn)（2）.第6頁(yè)，共18頁(yè)，2023年，2月20日，星期六例2用最速下降法求解無(wú)約束問(wèn)題：取初始點(diǎn)數(shù)值實(shí)驗(yàn)（1）a=b=1;(2)a=99,b=1.第7頁(yè)，共18頁(yè)，2023年，2月20日，星期六最速下降算法分析定理4－5若一維搜索是精確的，則最速下降法產(chǎn)生的相鄰兩次搜索方向是相互正交的，即結(jié)論：鋸齒形，收斂慢。停機(jī)條件：不合理。合理停機(jī)條件：第8頁(yè)，共18頁(yè)，2023年，2月20日，星期六解：第9頁(yè)，共18頁(yè)，2023年，2月20日，星期六第10頁(yè)，共18頁(yè)，2023年，2月20日，星期六四、算法的收斂性算法強(qiáng)收斂：迭代點(diǎn)列或子列滿足

弱收斂：的任一個(gè)聚點(diǎn)是穩(wěn)定點(diǎn)，或者局部收斂，全局收斂第11頁(yè)，共18頁(yè)，2023年，2月20日，星期六收斂速度迭代點(diǎn)列滿足若則（1）則稱線性收斂；（2）則稱次線性收斂；（3）則稱超線性收斂。若則稱為階收斂。第12頁(yè)，共18頁(yè)，2023年，2月20日，星期六算法的二次終止性定義3若某個(gè)算法對(duì)于任意的正定二次函數(shù)，從任意的初始點(diǎn)出發(fā)，都能經(jīng)有限步迭代達(dá)到其極小點(diǎn)，則稱該算法具有二次終止性。第13頁(yè)，共18頁(yè)，2023年，2月20日，星期六

算法及相關(guān)概念1.一般迭代算法集合S上的迭代算法A：（1）初始點(diǎn)；（2）按照某種規(guī)則A產(chǎn)生下一個(gè)迭代點(diǎn)。（i）如果點(diǎn)列收斂于最優(yōu)解，則稱算法A收斂。（ii）如果，則稱算法A為下降迭代算法。...第14頁(yè)，共18頁(yè)，2023年，2月20日，星期六

極小點(diǎn)的判定條件（1）必要條件：（2）充分條件：第15頁(yè)，共18頁(yè)，2023年，2月20日，星期六2.下降迭代算法步驟（1）給出初始點(diǎn)，令；（2）按照某種規(guī)則確定下降搜索方向；（3）按照某種規(guī)則確定搜索步長(zhǎng)，使得；（4）令，；（5）判斷是否滿足停止條件。是則停止，否則轉(zhuǎn)第2步。搜索步長(zhǎng)確定方法：稱。為最優(yōu)步長(zhǎng)，且有第16頁(yè)，共18頁(yè)，2023年，2月20日，星期六

終止條件2.4.1.3.5.最可靠法則