無約束最優(yōu)化問題的擬牛頓法畢業(yè)論文(編輯修改稿)
2025-07-21 23:17 本頁面
【文章內(nèi)容簡介】 ,有 . 稱時(shí)的收斂為二次收斂，這時(shí)誤差序列的性能可以用下述不等式表示 .二次收斂是一種更快的收斂，還要考察上式取等式時(shí)的情形，設(shè)初始誤差為1，則誤差序列為 1，，…，可以看到，二次收斂的方法每一次迭代近似解得精度就增加一倍。 一個(gè)理想的算法終止準(zhǔn)則為 .然而由于是未知的，這樣的準(zhǔn)則并不具有任何實(shí)用價(jià)值。但是由于 在序列{}超線性收斂于時(shí)，我們可以得到 .上式表明對于一個(gè)超線性收斂的算法是的一個(gè)估計(jì)。因此對于超線性收斂速度的方法， .是一個(gè)比較合適的終止準(zhǔn)則。Wolfe準(zhǔn)則為 .其中。Armijo準(zhǔn)則為： 給定，，設(shè)是使得下述不等式A： . （） 成立的最小非負(fù)整數(shù)，令。由于是下降方向，當(dāng)m充分大時(shí)，不等式()總是成立的，因此上述總是存在的。由于是使得上述不等式成了的最小非負(fù)整數(shù)，因而不會太小，從而保證了目標(biāo)函數(shù)的充分下降，令。實(shí)際上，不等式( . （） 如果上式滿足，則終止搜索，否則，我們可以縮小，或者在區(qū)間[0,]上用二次插值公式求近似極小點(diǎn) . （） 將其作為一個(gè)新的。第2章 擬牛頓法算法設(shè)計(jì) 擬牛頓法條件 考慮目標(biāo)函數(shù)在當(dāng)前點(diǎn)處的二階模型 . （.）其中，是對稱正定矩陣，是Hesse近似，它將在每次迭代中進(jìn)行校正。極小化這個(gè)二次模型 ， （） 從而新的迭代點(diǎn)為 . （）其中，是線性搜索步長因子，上述迭代（）稱為擬牛頓迭代，他與牛頓迭代的主要區(qū)別在于在（）中我們用Hesse近似代替了牛頓迭代中的Hesse矩陣。 設(shè)：在開集商二次連續(xù)可微，在附近的二次近似為 （）對上式兩邊求導(dǎo)，有 ， （）令 （）（）成為 . （）顯然，如果是正定二次函數(shù)，上述關(guān)系式（）精確成立。現(xiàn)在，我們要求在擬牛頓法中構(gòu)造出來的Hesse近似滿足這種關(guān)系，從而得到 . （）上式稱為擬牛頓條件或擬牛頓方法。 利用擬牛頓條件，我們可以得到 .上述公式成為BFGS校正公式（關(guān)于）如果令，則擬牛頓條件為 ， （）擬牛頓迭代為 （）或 . （） 擬牛頓條件使二次模型具有如下插值性質(zhì)：如果滿足擬牛頓條件（），那么在點(diǎn)的二次模型 （）滿足 . （）上式中的第一、第二等式是顯然的，第三個(gè)等式是利用擬牛頓條件（）得到的。，（或）。，停止。，得搜索方向；（或計(jì)算）。，并令。（或校正產(chǎn)生的），使得擬牛頓條件（）或（）成立。步6.，轉(zhuǎn)步2。 第3章 收斂性證明 設(shè)是任意初始點(diǎn)，是對稱正定矩陣的初始Hesse近似。 （a）在開凸集上二次可微； (b）水平集是凸的，存在正的常數(shù)m和M使得Hesse矩陣滿足 . （） (c）在的領(lǐng)域內(nèi)，是Lipschitz連續(xù)的，即 . （） 上述假設(shè)條件（b）意味著Hesse矩陣式上是正定的，有唯一的極小點(diǎn)。由Taylor定理， ,令 ， （）則 . （）于是，利用（）和()，有 . （）令，則 . （）注意矩陣A的跡trace（A）是A的對角元的和，也是A的特征值的和，即 （）矩陣的行列式det（A）是A的特征值的乘積，即 . ()在下面的證明中，我們利用了這兩個(gè)概念來估計(jì)Hesse近似的最大和最小特征值的大小。 設(shè)是任意初始對稱正定矩陣，是初始點(diǎn)，（a）（b）成立。證明 定義 ， . （）由（）和（)得 ， . （）由BFGS校正，計(jì)算其跡和行列式，得 （）和 . （） 定義 ， （）這里是和之間的夾角，于是 . （）又由（）和（），有 . （）現(xiàn)在我們定義 . （）其中表示自然對數(shù)。不難證明。由（），（）—（），得 . （） 注意到對所有的，上面方括號中的項(xiàng)是非正的，因而由（）,并反復(fù)利用（），得 ， （）其中。下面，我們利用Wolfe不精確線性搜索的總體收斂性定理證明結(jié)果。由于，故，這表明由（）定義的也是最速下降方向和擬牛頓搜索方向之間的夾角。于是，由于Wolfe不精確線性搜索的總體收斂性定理得 . （）為了證明 ，只要證明存在子序列{}，使得。假定。則存在，使得對所有，有 . （）其中是上面定義的常數(shù)。利用（）得到:對所有， （）在（）中，第一項(xiàng)和第三項(xiàng)是正的，但有限，第二項(xiàng)小于零，第四項(xiàng)也小于零，且與k有關(guān)，故當(dāng)k充分大時(shí)，上式右邊是負(fù)的，從而給出矛盾。這矛盾表明存在子序列{}，使得，從而 . （）（b），問題是強(qiáng)凸的，這表明。上述定理證明了：采用Wolfe不精確線性搜索的BFGS擬牛頓算法是總體收斂的。這個(gè)結(jié)果可推廣到所有的Broyden族，即不包括DFP校正。下面，我們研究BFGS方法的局部超線性收斂。首先我們給出擬牛頓法超線性收斂的充分必要條件。 局部超線性收斂 設(shè)：， (a) (b)成立?？紤]迭代。設(shè){}收斂到解點(diǎn)。則當(dāng)且僅當(dāng) . （）時(shí)，序列{}超線性收斂到。證明 設(shè)擬牛頓步為，牛頓步為，由于是正定的，故當(dāng)充分靠近時(shí)，是上有界的。我們先證明（）等價(jià)于 . （）假定（）成立，則 ()最后一個(gè)等式來自（）反之，設(shè)（）成立，則由左乘以（）兩邊，得 . （）注意到，從而（）成為 .此即（）。 下面，借助牛頓發(fā)的二次收斂性結(jié)果來完成證明。 . （）從上式易知 ，代入（），得到 這表明是超線性收斂的。這個(gè)定理告訴我們?nèi)c(diǎn)： (1) 超線性收斂的充要條件使（）成立，即只要沿搜索方向收斂到Hesse矩陣，則擬牛頓法超線性收斂。 (2)（）也是擬牛頓法超線性收斂的充要條件，即當(dāng)且僅當(dāng)擬牛頓步在長度和方向上都趨向于牛頓步，則擬牛頓法超線性收斂。 (3)如果將（）用 代替，定理仍然成立。這個(gè)定理是基本的和一般的，當(dāng)我們討論每個(gè)具體的擬牛頓法的超線性收斂性時(shí)，都要驗(yàn)證充要條件（）。：，滿足，設(shè)是非奇異矩陣序列。假定對某個(gè)，由 , （）產(chǎn)生的序列都在D中且收斂到。如果（）成立，那么{}超線性收斂到且的充要條件是收斂到1.證明 先假定{}超線性收斂到且。必有 ， ()意味著 .由
電大資料相關(guān)推薦
鄂ICP備17016276號-1