第3章 無約束最優(yōu)化方法 3-1 最速下降法 3-2 牛頓法課件

第三章無約束最優(yōu)化方法策略表現(xiàn)形式方法線性近似梯度法二次近似Newton法用布魯?shù)ぃ˙royden）族或黃（Huang）族擬Newton法修正公式第三章無約束最優(yōu)化方法第3.1節(jié)最速下降法第3.2節(jié)Newton法及其改進(jìn)第3.3節(jié)共軛方向法第3.4節(jié)擬牛頓法第3.1節(jié)最速下降法（SteepestMethod）下降方向的選取[算法3.1]（最速下降法）（1）給出初始點(diǎn)和精度；（2）計(jì)算。如果，則令停止；否則，轉(zhuǎn)（3）；（3）令，求解，得到；（4）令，轉(zhuǎn)（2）。第3.1節(jié)最速下降法（SteepestMethod）對(duì)于最速下降法的幾點(diǎn)說明（1）第2.6節(jié)中介紹的關(guān)于下降算法的收斂性定理對(duì)最速下降法都是成立的。（2）目標(biāo)函數(shù)在負(fù)梯度方向下降得最快只是局部性質(zhì)。（3）鋸齒現(xiàn)象（4）改進(jìn)策略：在計(jì)算的開始階段使用最速下降法，在迭代數(shù)次后，改用其他算法。第3.1節(jié)最速下降法（SteepestMethod）[引理3.2]（康德洛維奇Kntorovich不等式）設(shè)G為n階實(shí)對(duì)稱正定矩陣，其特征值為，則對(duì)任意的，總成立不等式。第3.1節(jié)最速下降法（SteepestMethod）[定理3.3]（二次函數(shù)情形下最速下降法的收斂速度定理）考慮無約束最優(yōu)化問題其中G是n階對(duì)稱正定矩陣。和分別是G的最大特征值和最小特征值。設(shè)是問題的解點(diǎn)，則最速下降法至少具有線性的收斂速度，并且滿足下面的界：第3.1節(jié)最速下降法（SteepestMethod）[對(duì)于定理的說明]（1）在上面定理中，如果考慮的是如下一般二次目標(biāo)函數(shù)，其中G是n階對(duì)稱正定矩陣，則有類似的證明方法證明定理同樣成立。（2）當(dāng)目標(biāo)函數(shù)是二階連續(xù)可微的一致凸函數(shù)時(shí)，由上章的推導(dǎo)可知，采用精確線性搜索的最速下降法產(chǎn)生的迭代點(diǎn)列至少是線性收斂的。第3.1節(jié)最速下降法（SteepestMethod）[引理3.4]設(shè)由精確線性搜索確定，對(duì)一切均成立，其中M是某個(gè)正常數(shù)，則有：

第3.1節(jié)最速下降法（SteepestMethod）[定理3.5]設(shè)最速下降法產(chǎn)生的點(diǎn)列收斂到，在附近二階連續(xù)可微，且，正定，則線性收斂到，即

其中M和m滿足，和分別是的最小特征值和最大特征值。第3.2節(jié)Newton法及其改進(jìn)本節(jié)的主要內(nèi)容：（1）牛頓法的基本思想（2）阻尼牛頓法（3）帶保護(hù)措施的阻尼牛頓法（4）吉爾-默里穩(wěn)定牛頓法（5）信賴域方法（一）第3.2節(jié)Newton法及其改進(jìn)（1）牛頓法的基本思想：在目標(biāo)函數(shù)的極小點(diǎn)的近似點(diǎn)附近將二階Tayler展開，用展開的二次函數(shù)去逼近，將這個(gè)二次函數(shù)的極小點(diǎn)作為的一個(gè)新的近似點(diǎn)，依次下去，用一系列二次函數(shù)的極小點(diǎn)去逼近的極小點(diǎn)。第3.2節(jié)Newton法及其改進(jìn)設(shè)二次連續(xù)可微，則在處的二次近似為：令即第3.2節(jié)Newton法及其改進(jìn)若正定（對(duì)稱），則存在。Newton迭代公式

Newton方向：第3.2節(jié)Newton法及其改進(jìn)[定理3.6]（Newton法收斂定理）設(shè)二階連續(xù)可微，是的局部最優(yōu)解，，正定，Hesse矩陣滿足Lipschitz條件：即存在，使得對(duì)所有的i，j，有其中是Hesse矩陣的元素。則當(dāng)初始點(diǎn)充分靠近時(shí)，對(duì)于一切的k，牛頓迭代公式有定義，并且所得迭代點(diǎn)列收斂到，并且具有二階收斂速度。第3.2節(jié)Newton法及其改進(jìn)牛頓法面臨的主要困難：（1）很難檢驗(yàn)初始點(diǎn)是否靠近最優(yōu)解，因而不能保證Hesse矩陣是否正定，得到的方向是下降方向，迭代點(diǎn)列的收斂性及收斂速度。（2）牛頓法對(duì)目標(biāo)函數(shù)要求高（二階連續(xù)可微），且需較多的存儲(chǔ)單元，每次迭代均要進(jìn)行矩陣求逆運(yùn)算。第3.2節(jié)Newton法及其改進(jìn)（2）阻尼牛頓法：[定理3.7]設(shè)在開凸集D上二階連續(xù)可微，且對(duì)任意的，存在常數(shù)，使得在水平集上滿足則從任意的初始點(diǎn)出發(fā)，阻尼牛頓法產(chǎn)生的迭代點(diǎn)列滿足：（1）當(dāng)為有窮點(diǎn)列時(shí)，其最后一個(gè)點(diǎn)為的唯一極小點(diǎn)。（2）當(dāng)為無窮點(diǎn)列時(shí)，收斂到的唯一極小點(diǎn)。第3.2節(jié)Newton法及其改進(jìn)[推論3.8]設(shè)在開凸集D上二階連續(xù)可微，且對(duì)任意的，存在常數(shù)，使得在水平集上滿足則從任意的初始點(diǎn)出發(fā)，牛頓法產(chǎn)生的迭代點(diǎn)列滿足，且收斂到的唯一極小點(diǎn)。第3.2節(jié)Newton法及其改進(jìn)阻尼牛頓法的優(yōu)點(diǎn)與缺點(diǎn)：阻尼牛頓法克服了牛頓法要求初始點(diǎn)充分靠近目標(biāo)函數(shù)的極小點(diǎn)的缺點(diǎn)，但只有當(dāng)目標(biāo)函數(shù)的Hesse矩陣處處正定時(shí)，才具有全局收斂性。如果Hesse矩陣不是處處正定，當(dāng)初始點(diǎn)遠(yuǎn)離局部極小點(diǎn)時(shí)，Hesse矩陣可能不正定，這時(shí)Hesse矩陣可能奇異也可能是非奇異。若Hesse矩陣奇異，求解方向的方程組可能無解，或者雖然有解，但求出的方向不能使迭代過程繼續(xù)進(jìn)行下去；若Hesse矩陣非奇異，但不正定，則求得的方向可能不是下降方向。第3.2節(jié)Newton法及其改進(jìn)[例3.9]取，則，，

顯然，是可逆矩陣，但不正定。其逆矩陣為于是，沿此方向進(jìn)行線性搜索，，其極小點(diǎn)為，因此迭代不能繼續(xù)進(jìn)行下去。第3.2節(jié)Newton法及其改進(jìn)（3）帶保護(hù)措施的阻尼牛頓法（Goldstein和Price，1967）

第3.2節(jié)Newton法及其改進(jìn)（4）吉爾-默里穩(wěn)定牛頓法（Gill和Murray，1974）

（4-1）

對(duì)稱矩陣的三角分解定理（4-2）強(qiáng)迫矩陣正定的分解（4-3）吉爾-默里穩(wěn)定牛頓法

第3.2.4節(jié)吉爾-默里穩(wěn)定牛頓法[定義3.14]設(shè)在開集D上二次連續(xù)可微，（i）如果Hesse矩陣至少有一個(gè)負(fù)特征值，則叫做不定點(diǎn)。（ii）如果x是一個(gè)不定點(diǎn)，若方向d滿足則稱d為在x處的負(fù)曲率方向。第3.2.4節(jié)吉爾-默里穩(wěn)定牛頓法負(fù)曲率方向的性質(zhì)：（1）若方向d為負(fù)曲率方向，則也是負(fù)曲率方向。（2）在鞍點(diǎn)處，負(fù)曲率方向必是下降方向；（3）在一般點(diǎn)處，若負(fù)曲率方向d滿足：，則d與均是下降方向；，則d是下降方向；，則是下降方向。第3.2.4節(jié)吉爾-默里穩(wěn)定牛頓法Gill-Murray穩(wěn)定牛頓法的基本思想：當(dāng)Hesse矩陣在迭代點(diǎn)處為不定矩陣時(shí)，對(duì)其進(jìn)行強(qiáng)迫正定的分解；當(dāng)趨于零時(shí)，采用負(fù)曲率方向使函數(shù)值下降。第3.2.4節(jié)吉爾-默里穩(wěn)定牛頓法[算法3.15]（求負(fù)曲率方向的算法）（1）令；（2）求下標(biāo)t，使得（3）若，表明不能得到負(fù)曲率方向，停止；否則，求解方程組求得處的負(fù)曲率方向。第3.2.4節(jié)吉爾-默里穩(wěn)定牛頓法[定理3.16]設(shè)是對(duì)進(jìn)行吉爾-默里強(qiáng)迫矩陣正定的分解，是方程組的解。則是處的負(fù)曲率方向，并且與中至少有一個(gè)是處的下降方向。第3.2.4節(jié)吉爾-默里穩(wěn)定牛頓法？[算法3.17]（Gill-Murray穩(wěn)定牛頓法）（1）給定初始點(diǎn)，精度，令；（2）計(jì)算梯度和Hesse矩陣；（3）應(yīng)用算法3.13對(duì)進(jìn)行強(qiáng)迫正定的分解，；（4）若，則解方程

求出搜索方向，轉(zhuǎn)步（6）；否則，轉(zhuǎn)步（5）；第3.2.4節(jié)吉爾-默里穩(wěn)定牛頓法？（5）執(zhí)行求負(fù)曲率方向的算法3.15，即計(jì)算。若，表明不能得到搜索方向，則停止；否則，求解方程組得到方向，令。（6）精確線性搜索求，且令（7）若，則停止計(jì)算；否則，令，轉(zhuǎn)步（2）。第3.2.4節(jié)吉爾-默里穩(wěn)定牛頓法[算法3.17]（Gill-Murray穩(wěn)定牛頓法）（1）給定初始點(diǎn)，精度，令；（2）計(jì)算梯度和Hesse矩陣；（3）應(yīng)用算法3.13對(duì)進(jìn)行強(qiáng)迫正定的分解，；（4）若，則解方程

求出搜索方向，轉(zhuǎn)步（6）；否則，轉(zhuǎn)步（5）；第3.2.4節(jié)吉爾-默里穩(wěn)定牛頓法（5）執(zhí)行求負(fù)曲率方向的算法3.15，即計(jì)算。若，表明不能得到搜索方向，則轉(zhuǎn)步（8）；否則，求解方程組得到方向，令。（6）精確線性搜索求，且令（7）若，則進(jìn)行步（8）；否則，令，轉(zhuǎn)步（2）。（8）輸出，停止計(jì)算。第3.2.4節(jié)吉爾-默里穩(wěn)定牛頓法[定理3.18]設(shè)二階連續(xù)可微，且存在，使得為有界閉凸集。假定在吉爾-默里穩(wěn)定牛頓法中取，且初始點(diǎn)，則吉爾-默里穩(wěn)定牛頓法產(chǎn)生的迭代序列滿足：（i）當(dāng)為有窮點(diǎn)列時(shí)，其最后一個(gè)元素必為的穩(wěn)定點(diǎn)；（ii）當(dāng)為無窮點(diǎn)列時(shí)，它必有聚點(diǎn)，且它的所有聚點(diǎn)都是的平穩(wěn)點(diǎn)。第3-2-5節(jié)信賴域方法信賴域方法的基本思想：首先選取一個(gè)信賴域半徑，并由此定義的一個(gè)鄰域使得n維二次模型是目標(biāo)函數(shù)的一個(gè)合適的模擬。然后求解具有信賴域約束的子問題（*）

第3-2-5節(jié)信賴域方法實(shí)際下降量：預(yù)測(cè)下降量：衡量二次模型近似目標(biāo)函數(shù)的指標(biāo)：

第3-2-5節(jié)信賴域方法（1）給定初始點(diǎn)，初始步長(zhǎng)，精度，閾值，滿足放大系數(shù)令。（2）計(jì)算，如果，則，停止；否則，形成矩陣；（3）求解子問題（*），求出；第3-2-5節(jié)信賴域方法（4）計(jì)算