[科普中國(guó)]-信賴域算法

信賴域算法的基本思想

在每次迭代中給出一個(gè)信賴域，這個(gè)信賴域一般是當(dāng)前迭代點(diǎn) 的一個(gè)小鄰域。然后，在這個(gè)鄰域內(nèi)求解一個(gè)子問(wèn)題，得到試探步長(zhǎng)（trial step） ，接著用某一評(píng)價(jià)函數(shù)來(lái)決定是否接受該試探步以及確定下一次迭代的信賴域。

如果試探步長(zhǎng)被接受，則： ，否則， 。

新的信賴域的大小取決于試探步的好壞，粗略地說(shuō)，如果試探步較好，在下一步信賴域擴(kuò)大或者保持不變，否則減小信賴域。

信賴域方法思想設(shè)當(dāng)前點(diǎn) 的鄰域定義為： ，其中， 稱為信賴域半徑。

目標(biāo)函數(shù)在極值點(diǎn)附近近似一個(gè)二次函數(shù)，因此對(duì)于無(wú)約束優(yōu)化問(wèn)題，利用二次逼近，構(gòu)造如下信賴域子問(wèn)題：

其中， ， 是目標(biāo)函數(shù) 在當(dāng)前迭代點(diǎn) 處的梯度， 對(duì)稱，是 在 處Hesse陣 或者其近似。

設(shè) 是信賴域子問(wèn)題的解。目標(biāo)函數(shù) 在第 步的實(shí)際下降量（真實(shí)下降量）：

二次模型函數(shù) 的下降量（預(yù)測(cè)下降量）：

定義比值：

它衡量了二次模型與目標(biāo)函數(shù)的逼近程度， 越接近于1，表明接近程度越好。因此，我們也用這個(gè)量來(lái)確定下次迭代的信賴域半徑1。

信賴域半徑的選擇（1） 越接近與1，表明接近程度越好。這時(shí)可以增大 以擴(kuò)大信賴域；

（2） 但是不接近于1，保持 不變；

（3）如果 接近于0，減小 ，縮小信賴域。

信賴域算法的步驟Step1：給出初始點(diǎn) ，初始信賴域半徑 ，開(kāi)始迭代2。

Step2：到第k步時(shí)，計(jì)算梯度 與Hesse陣 。

Step3：求解信賴域模型，得到試探步長(zhǎng) ，計(jì)算比值 。

Step4：若 ，說(shuō)明步子邁得太大了，應(yīng)縮小信賴域半徑，令 。

Step5：若 且 ，說(shuō)明這一步已經(jīng)邁到了信賴域半徑的邊緣，并且步子有點(diǎn)小，可以嘗試擴(kuò)大信賴域半徑，令 。

Step6：若 ，說(shuō)明這一步邁出去之后，處于“可信賴”和“不可信賴”之間，可以維持當(dāng)前的信賴域半徑，令 。

Step7：若 ，說(shuō)明函數(shù)值是向著上升而非下降的趨勢(shì)變化了（與最優(yōu)化的目標(biāo)相反），說(shuō)明這一步邁得錯(cuò)得“離譜”了，這時(shí)不應(yīng)該走到下一點(diǎn)，而應(yīng)“原地踏步”，即 ，并且和上面 的情況一樣縮小信賴域。反之，在 的情況下，都可以走到下一點(diǎn)，即 。

信賴域算法的收斂性信賴域算法具有整體收斂性2。